Ⅰ 求四叉树完整建立和遍历的运行代码(c或c++)
一个四叉树的实现代码
class QuadTreeCode
{
public:
vector<int> m_Numbers;
/*判断两个四叉树码是否相等*/
bool operator ==( QuadTreeCode& tempTree )
{
if ( m_Numbers.size()!=tempTree.m_Numbers.size() )
{
return false;
}
else
{
for ( int i=0; i<m_Numbers.size(); i++ )
{
if ( m_Numbers[i]!=tempTree.m_Numbers[i])
{
return false;
}
}
}
return true;
}
/*返回四叉树码的长度*/
int GetLength()
{
return m_Numbers.size();
}
int operator[](int Index)
{
return m_Numbers[Index];
}
};
enum ChildType
{
UL = 0,
UR = 3,
LL = 1,
LR = 2
};
template<class T>
class QuadTreeNode
{
public:
T *m_pData;
QuadTreeNode *m_pUpperLeft,*m_pUpperRight,*m_pLowerLeft,*m_pLowerRight;
QuadTreeCode m_Code; //节点在树中位置的编码
QuadTreeNode ()
{
m_pData = NULL;
m_pUpperLeft = m_pUpperRight = m_pLowerLeft = m_pLowerRight = NULL;
}
~QuadTreeNode ()
{
delete m_pData;
}
/*返回子成员的地址*/
QuadTreeNode ** GetChild( ChildType ctype )
{
switch( ctype )
{
case ChildType::UL:
return &m_pUpperLeft;
break;
case ChildType::UR:
return &m_pUpperRight;
break;
case ChildType::LL:
return &m_pLowerLeft;
break;
case ChildType::LR:
return &m_pLowerRight;
break;
}
}
};
template<class T>
class QuadTree
{
public:
int m_nTreeDepth; //树的深度
QuadTreeNode<T> *m_pHeadNode; //树的头部
QuadTree()
{
m_nTreeDepth = 0;
m_pHeadNode = NULL;
}
~QuadTree()
{
void (QuadTree::*func)(QuadTreeNode<T> *) ;
func = &QuadTree::DestroyNode;
PostOrderOperation( m_pHeadNode, func );
}
/*
后序遍历方式操作四叉树
*/
void PostOrderOperation( QuadTreeNode<T> * ptempNode, void (QuadTree<T>::*NodeOp)( QuadTreeNode<T> * ) )
{
if( ptempNode!=NULL )
{
PostOrderOperation( ptempNode->m_pLowerLeft, NodeOp );
PostOrderOperation( ptempNode->m_pLowerRight, NodeOp );
PostOrderOperation( ptempNode->m_pUpperLeft, NodeOp );
PostOrderOperation( ptempNode->m_pUpperRight, NodeOp );
(this->*NodeOp) ( ptempNode );
}
}
void DestroyNode( QuadTreeNode<T> * ptempNode )
{
delete ptempNode;
}
/*创建树枝*/
void CreateBranch( QuadTreeNode<T>**ppNode , int TreeDepth, int CurrentDepth )
{
if( CurrentDepth>TreeDepth )
{
return;
}
else
{
QuadTreeNode<T> *pNewNode = new QuadTreeNode<T>;
*ppNode = pNewNode;
QuadTreeNode<T> **pTempNode;
CreateBranch( pNewNode->GetChild(ChildType::UL), TreeDepth, CurrentDepth+1 );
CreateBranch( pNewNode->GetChild(ChildType::UR), TreeDepth, CurrentDepth+1 );
CreateBranch( pNewNode->GetChild(ChildType::LL), TreeDepth, CurrentDepth+1 );
CreateBranch( pNewNode->GetChild(ChildType::LR), TreeDepth, CurrentDepth+1 );
}
}
/*按照四叉树码进行操作*/
bool OperateNodeByCode( QuadTreeCode code, void (*Op)( QuadTreeNode<T> *) )
{
QuadTreeNode* ptempNode = m_pHeadNode;
for( int i=0; i<code.GetLength(); i++ )
{
ptempNode = ptempNode->GetChild( code[i] );
if( ptempNode==NULL )
return false;
}
Op( ptempNode );
return true;
}
/*近创建内存结构,数据内容并未赋值*/
void CreateTree( int TreeDepth )
{
m_nTreeDepth = TreeDepth;
CreateBranch( &m_pHeadNode, TreeDepth, 0);
}
//virtual void CreateNode( QuadTreeNode<T> * ptempNode ) const = 0;
};
Ⅱ 决策树(Decision Tree)
决策树(Decision Tree)是一种基本的分类与回归方法,其模型呈树状结构,在分类问题中,表示基于特征对实例进行分类的过程。本质上,决策树模型就是一个定义在特征空间与类空间上的条件概率分布。决策树学习通常包括三个步骤: 特征选择 、 决策树的生成 和 决策树的修剪 。
分类决策树模型是一种描述对实例进行分类的树形结构,决策树由节点(node)和有向边(directed edge)组成。节点有两种类型:内部节点(internal node)和叶节点(leaf node)。内部节点表示一个特征或属性,叶节点表示一个类。
利用决策树进行分类,从根节点开始,对实例的某一特征进行测试,根据测试结果将实例分配到其子节点;这时,每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶节点。最后将实例分到叶节点的类中。
决策树是给定特征条件下类的条件概率分布,这一条件概率分布定义在特征区间的一个划分(partiton)上。将特征空间划分为互不相交的单元(cell)或区域(region),并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应划分中的一个单元,决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量,Y为表示类的随机变量,那么这个条件概率分布可以表示成P(Y|X)。X取值于给定划分下单元的集合,Y取值于类的集合,各叶节点(单元)上的条件概率往往偏向于某一个类,即属于某一类的概率较大,决策树分类时将该节点的实例分到条件概率大的那一类去。也就以为着决策树学习的过程其实也就是由数据集估计条件概率模型的过程,这些基于特征区间划分的类的条件概率模型由无穷多个,在进行选择时,不仅要考虑模型的拟合能力还要考虑其泛化能力。
为了使模型兼顾模型的拟合和泛化能力,决策树学习使用正则化的极大似然函数来作为损失函数,以最小化损失函数为目标,寻找最优的模型。显然从所有可能的决策树中选取最优决策树是NP完全问题,所以在实际中通常采用启发式的方法,近似求解这一最优化问题: 通过递归的选择最优特征,根据该特征对训练数据进行划分直到使得各个子数据集有一个最好的分类,最终生成特征树 。当然,这样得到的决策树实际上是次最优(sub-optimal)的。进一步的,由于决策树的算法特性,为了防止模型过拟合,需要对已生成的决策树自下而上进行剪枝,将树变得更简单,提升模型的泛化能力。具体来说,就是去掉过于细分的叶节点,使其退回到父节点,甚至更高的节点,然后将父节点或更高的节点改为新的叶节点。如果数据集的特征较多,也可以在进行决策树学习之前,对数据集进行特征筛选。
由于决策树是一个条件概率分布,所以深浅不同的决策树对应着不同复杂度的概率模型,决策树的生成对应模型的局部选择,决策树的剪枝对应着模型的全局选择。
熵(Entropy) 的概念最早起源于物理学,最初物理学家用这个概念度量一个热力学系统的无序程度。在1948年, 克劳德·艾尔伍德·香农 将热力学的熵,引入到 信息论 ,因此它又被称为 香农熵 。在信息论中,熵是对不确定性的量度,在一条信息的熵越高则能传输越多的信息,反之,则意味着传输的信息越少。
如果有一枚理想的硬币,其出现正面和反面的机会相等,则抛硬币事件的熵等于其能够达到的最大值。我们无法知道下一个硬币抛掷的结果是什么,因此每一次抛硬币都是不可预测的。因此,使用一枚正常硬币进行若干次抛掷,这个事件的熵是一 比特 ,因为结果不外乎两个——正面或者反面,可以表示为 0, 1 编码,而且两个结果彼此之间相互独立。若进行 n 次 独立实验 ,则熵为 n ,因为可以用长度为 n 的比特流表示。但是如果一枚硬币的两面完全相同,那个这个系列抛硬币事件的熵等于零,因为 结果能被准确预测 。现实世界里,我们收集到的数据的熵介于上面两种情况之间。
另一个稍微复杂的例子是假设一个 随机变量 X ,取三种可能值 ,概率分别为 ,那么编码平均比特长度是: 。其熵为 。因此<u>熵实际是对随机变量的比特量和顺次发生概率相乘再总和的</u> 数学期望 。
依据玻尔兹曼H定理,香农把随机变量X的熵 定义为:
其中 是随机变量X的信息量,当随机变量取自有限样本时,熵可以表示为:
若 ,则定义 。
同理可以定义条件熵 :
很容易看出,条件熵(conditional entropy) 就是X给定条件下Y的条件概率分布的熵对X的数学期望。当熵和条件熵中的概率有极大似然估计得到时,所对应的熵和条件熵分别称为检验熵(empirical entropy)和经验条件熵(empirical conditional entropy).
熵越大,随机变量的不确定性就越大,从定义可以验证:
当底数 时,熵的单位是 ;当 时,熵的单位是 ;而当 时,熵的单位是 .
如英语有26个字母,假如每个字母在文章中出现的次数平均的话,每个字母的信息量 为:
同理常用汉字2500有个,假设每个汉字在文章中出现的次数平均的话,每个汉字的信息量 为:
事实上每个字母和汉字在文章中出现的次数并不平均,少见字母和罕见汉字具有相对较高的信息量,显然,由期望的定义,熵是整个消息系统的平均消息量。
熵可以用来表示数据集的不确定性,熵越大,则数据集的不确定性越大。因此使用 划分前后数据集熵的差值 量度使用当前特征对于数据集进行划分的效果(类似于深度学习的代价函数)。对于待划分的数据集 ,其划分前的数据集的熵 是一定的,但是划分之后的熵 是不定的, 越小说明使用此特征划分得到的子集的不确定性越小(也就是纯度越高)。因此 越大,说明使用当前特征划分数据集 时,纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的数据子集,这一点可以参考优化算法中的梯度下降算法,每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理:在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展,因此我们总是选择使得信息增益最大的特征来划分当前数据集 。
显然这种划分方式是存在弊端的,按信息增益准则的划分方式,当数据集的某个特征B取值较多时,依此特征进行划分更容易得到纯度更高的数据子集,使得 偏小,信息增益会偏大,最终导致信息增益偏向取值较多的特征。
设 是 个数据样本的集合,假定类别属性具有 个不同的值: ,设 是类 中的样本数。对于一个给定样本,它的信息熵为:
其中, 是任意样本属于 的概率,一般可以用 估计。
设一个属性A具有 个不同的值 ,利用属性A将集合 划分为 个子集 ,其中 包含了集合 中属性 取 值的样本。若选择属性A为测试属性,则这些子集就是从集合 的节点生长出来的新的叶节点。设 是子集 中类别为 的样本数,则根据属性A划分样本的信息熵为:
其中 , 是子集 中类别为 的样本的概率。最后,用属性A划分样本子集 后所得的 信息增益(Gain) 为:
即,<u>属性A的信息增益=划分前数据的熵-按属性A划分后数据子集的熵</u>。 信息增益(information gain)又称为互信息(matual information)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度 。信息增益显然 越小, 的值越大,说明选择测试属性A对于分类提供的信息越多,选择A之后对分类的不确定程度越小。
经典算法 ID3 使用的信息增益特征选择准则会使得划分更偏相遇取值更多的特征,为了避免这种情况。ID3的提出者 J.Ross Quinlan 提出了 C4.5 ,它在ID3的基础上将特征选择准则由 信息增益 改为了 信息增益率 。在信息增益的基础之上乘上一个惩罚参数。特征个数较多时,惩罚参数较小;特征个数较少时,惩罚参数较大(类似于正则化)。这个惩罚参数就是 分裂信息度量 的倒数 。
不同于 ID3 和 C4.5 , CART 使用基尼不纯度来作为特征选择准则。基尼不纯度也叫基尼指数 , 表示在样本集合中一个随机选中的样本被分错的概率 则<u>基尼指数(基尼不纯度)= 样本被选中的概率 * 样本被分错的概率</u>。Gini指数越小表示集合中被选中的样本被分错的概率越小,也就是说集合的纯度越高,反之,集合越不纯。
样本集合的基尼指数:
样本集合 有m个类别, 表示第 个类别的样本数量,则 的Gini指数为:
基于某个特征划分样本集合S之后的基尼指数:
CART是一个二叉树,也就是当使用某个特征划分样本集合后,得到两个集合:a.等于给定的特征值的样本集合 ;b.不等于给定特征值的样本集合 。实质上是对拥有多个取值的特征的二值处理。
对于上述的每一种划分,都可以计算出基于划分特=某个特征值将样本集合划分为两个子集的纯度:
因而对于一个具有多个取值(超过2个)的特征,需要计算以每个取值为划分点,对样本集合划分后子集的纯度 ( 表示特征 的可能取值)然后从所有的划分可能 中找出Gini指数最小的划分,这个划分的划分点,就是使用特征 对样本集合 进行划分的最佳划分点。
参考文献 :
决策树--信息增益,信息增益比,Geni指数的理解
【机器学习】深入理解--信息熵(Information Entropy)
统计学习方法 (李航)
为了便于理解,利用以下数据集分别使用三种方法进行分类:
在进行具体分析之前,考虑到收入是数值类型,要使用决策树算法,需要先对该属性进行离散化。
在机器学习算法中,一些分类算法(ID3、Apriori等)要求数据是分类属性形式,因此在处理分类问题时经常需要将一些连续属性变换为分类属性。一般来说,连续属性的离散化都是通过在数据集的值域内设定若干个离散的划分点,将值域划分为若干区间,然后用不同的符号或整数数值代表落在每个子区间中的数据值。所以,离散化最核心的两个问题是:如何确定分类数以及如何将连续属性映射到这些分类值。常用的离散化方法有 等宽法 , 等频法 以及 一维聚类法 等。
在实际使用时往往使用Pandas的 cut() 函数实现等宽离散化:
可以看到与手工计算的离散化结果相同,需要注意的是,<u> 等宽法对于离群点比较敏感,倾向于不均匀地把属性值分布到各个区间,导致某些区间数据较多,某些区间数据很少,这显然不利用决策模型的建立。 </u>
使用四个分位数作为边界点,对区间进行划分:
<u> 等频率离散化虽然避免了等宽离散化的数据分布不均匀的问题,却可能将相同的数据值分到不同的区间以满足每个区间具有相同数量的属性取值的要求。 </u>
使用一维聚类的离散化方法后得到数据集为:
在本次实例中选择使用基于聚类的离散化方法后得到的数据集进行指标计算。为了预测客户能否偿还债务,使用A(拥有房产)、B(婚姻情况)、C(年收入)等属性来进行数据集的划分最终构建决策树。
单身 :
离婚 :
已婚 :
显然,由B属性取值'已婚'划分得到的子数据集属于同一个叶节点,无法再进行分类。
接下来,对由B属性取值'单身'划分得到的子数据集 再进行最优特征选择:
1)计算数据集 总的信息熵,其中4个数据中,能否偿还债务为'是'数据有3,'否'数据有1,则总的信息熵:
2)对于A(拥有房产)属性,其属性值有'是'和'否'两种。其中,在A为'是'的前提下,能否偿还债务为'是'的有1、'否'的有0;在A为'否'的前提下,能否偿还债务为'是'的有2、为'否'的有1,则A属性的信息熵为:
3)对于B(婚姻情况)属性,由于已被确定,在这个数据子集信息熵为0
4)对于C(年收入)属性,其属性值有'中等输入'、'低收入'两种。在C为'中等收入'的前提下,能否偿还作为为'是'的有1,为'否'的有0;在C为'低收入'的前提下,能否偿还作为为'是'的有2,为'否'的有1;则C属性的信息熵为:
5)最后分别计算两个属性的信息增益值:
信息增益值相同,说明以两个属性对数据子集进行划分后决策树的纯度上升是相同的,此时任选其一成为叶节点即可。
同理,对数据子集 进行最优特征选择,发现信息熵为0:
整理得到最终的决策树:
Ⅲ 设完成二叉树按层次(同一层自左至右)遍历的算法。
#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
typedef char ElemType;//定义二叉树结点值的类型为字符型
const int MaxLength=10;//结点个数不超过10个
typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;
void CreateBiTree(BiTree &T){//按先序次序输入,构造二叉链表表示的二叉树T,空格表示空树
// if(T) return;
char ch;
ch=getchar(); //不能用cin来输入,在cin中不能识别空格。
if(ch==' ') T=NULL;
else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void PreOrderTraverse(BiTree T){//先序遍历
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){//中序遍历
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){//后序遍历
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}
void LevelOrderTraverse(BiTree T){//层序遍历
BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根结点入队
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //队头元素出队
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩子不为空,入队
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不为空,入队
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}
}
//非递归的先序遍历算法
void NRPreOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
cout<<p->data;
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top]; p=p->rchild; }
}
}
}
//非递归的中序遍历算法
void NRInOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top];cout<<p->data; p=p->rchild; }
}
}
}
//非递归的后序遍历算法
/*bt是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法,结点入栈时,配一个标志tag一同入栈
(1:遍历左子树前的现场保护,2:遍历右子树前的现场保护)。
首先将bt和tag(为1)入栈,遍历左子树;
返回后,修改栈顶tag为2,遍历右子树;最后访问根结点。*/
typedef struct
{
BiTree ptr;
int tag;
}stacknode;
void NRPostOrder(BiTree bt)
{
stacknode s[MaxLength],x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL) //遍历左子树
{
s[top].ptr = p;
s[top].tag = 1; //标记为左子树
top++;
p=p->lchild;
}
while (top>0 && s[top-1].tag==2)
{
x = s[--top];
p = x.ptr;
cout<<p->data; //tag为R,表示右子树访问完毕,故访问根结点
}
if (top>0)
{
s[top-1].tag =2; //遍历右子树
p=s[top-1].ptr->rchild;
}
}while (top>0);}
}//PostOrderUnrec
int BTDepth(BiTree T){//求二叉树的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}
int Leaf(BiTree T){//求二叉树的叶子数
if(!T) return 0;
else if(!T->lchild&&!T->rchild) return 1;
else return(Leaf(T->lchild)+Leaf(T->rchild));
}
int NodeCount(BiTree T){//求二叉树的结点总数
if(!T) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
void main(){
BiTree T;
T=NULL;
int select;
//cout<<"请按先序次序输入各结点的值,以空格表示空树(输入时可连续输入):"<<endl;
// CreateBiTree(T);
while(1){
cout<<"\n\n请选择要执行的操作:\n";
cout<<"1.创建二叉树\n";
cout<<"2.二叉树的递归遍历算法(前、中、后)\n";
cout<<"3.二叉树的层次遍历算法\n";
cout<<"4.求二叉树的深度\n";
cout<<"5.求二叉树的叶子结点\n";
cout<<"6.求二叉树的结点总数\n";
cout<<"7.二叉树的非递归遍历算法(前、中、后)\n"; //此项可选做
cout<<"0.退出\n";
cin>>select;
switch(select){
case 0:return;
case 1:
cout<<"请按先序次序输入各结点的值,以空格表示空树(输入时可连续输入):"<<endl;
CreateBiTree(T);
break;
case 2:
if(!T) cout<<"未建立树,请先建树!";
else{
cout<<"\n先序遍历:\n";
PreOrderTraverse(T);
cout<<"\n中序遍历:\n";
InOrderTraverse(T);
cout<<"\n后序遍历:\n";
PostOrderTraverse(T);
}
break;
case 3:
cout<<"\n层序遍历:\n";
LevelOrderTraverse(T);
break;
case 4:
cout<<"二叉树的深度为:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n叶子节点数:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"总节点数:\n";
cout<<NodeCount(T);
break;
case 7:
if(!T) cout<<"未建立树,请先建树!";
else{
cout<<"\n先序遍历:\n";
NRPreOrder(T);
cout<<"\n中序遍历:\n";
NRInOrder(T);
cout<<"\n后序遍历:\n";
NRPostOrder(T);
}
break;
default:
cout<<"请确认选择项:\n";
}//end switch
}//end while
}
参考资料:找来的,你看看吧!
Ⅳ 划分树、倾斜树、线段树、平衡树哪个不是数据结构
倾斜树不是。
数据结构中提到的树如下所示:
基础类:二叉搜索(排序)树,线索二叉树,哈夫曼树(最优二叉树),二叉堆
平衡树类:AVL,红黑树,2-3树,2-3-4树,B树,B+树,B-树,treap,SBT.
优先队列类:左高树(左偏树,可并堆,斜堆),双端堆,斐波那契堆
集合类:并查集
区间树类:线段树,划分树,归并树,树状数组
字母树类:字典树,后缀树.AC自动机算法
动态树类:伸展树
计算几何类:KD-tree (块状树),4叉树
RMQ转LCA:笛卡尔树
图论相关:最小生成树,无根树
其它:败者树,博弈树
Ⅳ 设二叉树T的度为4,其中度为1,2,3,4的结点的个数分别为4,2,1,1。则T中的叶子结点的个数为
叶子结点个数为8。
假设度为0的结点个数为n0,假设总的结点个数为N。
则依据边来算结点总数为(边的总数加1等于N):
N=1*4+2*2+3*1+4*1+1=4+4+3+4+1=16(1)。
按照结点来算结点总数为(各度数结点的总和等于N):
N=n0+4+2+1+1=n0+8(2)。
(2)-(1)得n0-8=0,因此n0=8即叶子结点个数为8。
除法的法则:
数的整除要记住,除式各项都要是整数。但是除数不等于0,商是整数无余。a÷b时可以说,数b能够整除a,数a能被b整除。a是数b的倍数,b是数a的约数。如果要是求约数就去除以自然数,如果要是求倍数就去乘自然数。
能被2、5、3整除的数个位是0和5,一定能被5整除。个位是2、4、6、8、0,一定能被2整除。各个数位数字和,如果要是3倍数,一定能被3整除。
Ⅵ 一颗二叉树前序遍历和中序遍历分别是ABDEGCFH、DBGEACHF,则此后序遍历是请高手解释怎么得的,说明原理!
后序遍历是DGEBHFCA。
前序遍历的第一个节点为根节点,由前序遍历可知,A为根节点。中序遍历的根节点前面的节点均为左子树的节点,所以左子树上的节点为DBGE。
去掉根节点和左子树节点,右子数节点为CHF。前序遍历的第二个节点为B,由2知B为左子树节点,所以B为左子树的根节点。
在二叉树中,求后序遍历,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。则该二叉树的后序遍历是DGEBHFCA。
(6)四叉树自适应加密扩展阅读:
除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发。
首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
Ⅶ Fluent加密网格具体步骤,看到很多人说Fluent可以自适应加密网格,在adpat中可以实现,哪位高手告诉下具体
1、首先启动FLUENT Meshing软件。
Ⅷ 将一棵有100个结点的完全二叉树从根这一层开始
将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的左孩子编号为98。
如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右。则深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。
(8)四叉树自适应加密扩展阅读:
叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。需要注意的是,满二叉树肯定是完全二叉树,而完全二叉树不一定是满二叉树。
如果遇到一个结点,左孩子不为空,右孩子为空;或者左右孩子都为空;则该节点之后的队列中的结点都为叶子节点;该树才是完全二叉树,否则就不是完全二叉树。
Ⅸ 地理信息系统计算题~跪求解题过程
答:
2,3,0,0,0; 2,2,2,0,0; 4,4,2,0,0; 4,4,4,2,0 。
1)、点:3, 面:4、0;线:2。
2)、假设方向代码分别表示为:东=0,东北=1,北=2,西北=3,西=4,西南=5,南=6,东南=7。写出线状地物的链式编码。 1,1,6,0,0,6,7
3)、行方向写出一种游程编码方案。
(2,1),(3,1),(0,3);(2,3),(0,2);(4,2),(2,1),(0,2);(4,3),(2,1),(0,1)
4)、最多分3层,最大层数是10。
Ⅹ 加密技术有哪几种
采用密码技术对信息加密,是最常用的安全交易手段。在电子商务中获得广泛应用的加密技术有以下两种:
(1)公共密钥和私用密钥(public key and private key)
这一加密方法亦称为RSA编码法,是由Rivest、Shamir和Adlernan三人所研究发明的。它利用两个很大的质数相乘所产生的乘积来加密。这两个质数无论哪一个先与原文件编码相乘,对文件加密,均可由另一个质数再相乘来解密。但要用一个质数来求出另一个质数,则是十分困难的。因此将这一对质数称为密钥对(Key Pair)。在加密应用时,某个用户总是将一个密钥公开,让需发信的人员将信息用其公共密钥加密后发给该用户,而一旦信息加密后,只有用该用户一个人知道的私用密钥才能解密。具有数字凭证身份的人员的公共密钥可在网上查到,亦可在请对方发信息时主动将公共密钥传给对方,这样保证在Internet上传输信息的保密和安全。
(2)数字摘要(digital digest)
这一加密方法亦称安全Hash编码法(SHA:Secure Hash Algorithm)或MD5(MD Standards for Message Digest),由Ron Rivest所设计。该编码法采用单向Hash函数将需加密的明文“摘要”成一串128bit的密文,这一串密文亦称为数字指纹(Finger Print),它有固定的长度,且不同的明文摘要成密文,其结果总是不同的,而同样的明文其摘要必定一致。这样这摘要便可成为验证明文是否是“真身”的“指纹”了。
上述两种方法可结合起来使用,数字签名就是上述两法结合使用的实例。
3.2数字签名(digital signature)
在书面文件上签名是确认文件的一种手段,签名的作用有两点,一是因为自己的签名难以否认,从而确认了文件已签署这一事实;二是因为签名不易仿冒,从而确定了文件是真的这一事实。数字签名与书面文件签名有相同之处,采用数字签名,也能确认以下两点:
a. 信息是由签名者发送的。
b. 信息在传输过程中未曾作过任何修改。
这样数字签名就可用来防止电子信息因易被修改而有人作伪;或冒用别人名义发送信息;或发出(收到)信件后又加以否认等情况发生。
数字签名采用了双重加密的方法来实现防伪、防赖。其原理为:
(1) 被发送文件用SHA编码加密产生128bit的数字摘要(见上节)。
(2) 发送方用自己的私用密钥对摘要再加密,这就形成了数字签名。
(3) 将原文和加密的摘要同时传给对方。
(4) 对方用发送方的公共密钥对摘要解密,同时对收到的文件用SHA编码加密产生又一摘要。
(5) 将解密后的摘要和收到的文件在接收方重新加密产生的摘要相互对比。如两者一致,则说明传送过程中信息没有被破坏或篡改过。否则不然。
3.3数字时间戳(digital time-stamp)
交易文件中,时间是十分重要的信息。在书面合同中,文件签署的日期和签名一样均是十分重要的防止文件被伪造和篡改的关键性内容。
在电子交易中,同样需对交易文件的日期和时间信息采取安全措施,而数字时间戳服务(DTS:digital time-stamp service)就能提供电子文件发表时间的安全保护。
数字时间戳服务(DTS)是网上安全服务项目,由专门的机构提供。时间戳(time-stamp)是一个经加密后形成的凭证文档,它包括三个部分:1)需加时间戳的文件的摘要(digest),2)DTS收到文件的日期和时间,3)DTS的数字签名。
时间戳产生的过程为:用户首先将需要加时间戳的文件用HASH编码加密形成摘要,然后将该摘要发送到DTS,DTS在加入了收到文件摘要的日期和时间信息后再对该文件加密(数字签名),然后送回用户。由Bellcore创造的DTS采用如下的过程:加密时将摘要信息归并到二叉树的数据结构;再将二叉树的根值发表在报纸上,这样更有效地为文件发表时间提供了佐证。注意,书面签署文件的时间是由签署人自己写上的,而数字时间戳则不然,它是由认证单位DTS来加的,以DTS收到文件的时间为依据。因此,时间戳也可作为科学家的科学发明文献的时间认证。
3.4数字凭证(digital certificate, digital ID)
数字凭证又称为数字证书,是用电子手段来证实一个用户的身份和对网络资源的访问的权限。在网上的电子交易中,如双方出示了各自的数字凭证,并用它来进行交易操作,那么双方都可不必为对方身份的真伪担心。数字凭证可用于电子邮件、电子商务、群件、电子基金转移等各种用途。
数字凭证的内部格式是由CCITT X.509国际标准所规定的,它包含了以下几点:
(1) 凭证拥有者的姓名,
(2) 凭证拥有者的公共密钥,
(3) 公共密钥的有效期,
(4) 颁发数字凭证的单位,
(5) 数字凭证的序列号(Serial number),
(6) 颁发数字凭证单位的数字签名。
数字凭证有三种类型:
(1) 个人凭证(Personal Digital ID):它仅仅为某一个用户提供凭证,以帮助其个人在网上进行安全交易操作。个人身份的数字凭证通常是安装在客户端的浏览器内的。并通过安全的电子邮件(S/MIME)来进行交易操作。
(2) 企业(服务器)凭证(Server ID):它通常为网上的某个Web服务器提供凭证,拥有Web服务器的企业就可以用具有凭证的万维网站点(Web Site)来进行安全电子交易。有凭证的Web服务器会自动地将其与客户端Web浏览器通信的信息加密。
(3) 软件(开发者)凭证(Developer ID):它通常为Internet中被下载的软件提供凭证,该凭证用于和微软公司Authenticode技术(合法化软件)结合的软件,以使用户在下载软件时能获得所需的信息。
上述三类凭证中前二类是常用的凭证,第三类则用于较特殊的场合,大部分认证中心提供前两类凭证,能提供各类凭证的认证中心并不普遍