数据结构与算法系列研究五——树、⼆叉树、三叉树、平衡排序⼆叉树AVL
树、⼆叉树、三叉树、平衡排序⼆叉树AVL
⼀、树的定义
树是计算机算法最重要的⾮线性结构。树中每个数据元素⾄多有⼀个直接前驱，但可以有多个直接后继。树是⼀种以分⽀关系定义的层次结构。
a.树是n(≥0)结点组成的有限集合。{N.沃恩}
(树是n(n≥1)个结点组成的有限集合。{D.E.Knuth})
在任意⼀棵⾮空树中：
⑴有且仅有⼀个没有前驱的结点----根(root)。
⑵当n>1时，其余结点有且仅有⼀个直接前驱。
⑶所有结点都可以有0个或多个后继。
b. 树是n(n≥0)个结点组成的有限集合。
在任意⼀棵⾮空树中：
⑴有⼀个特定的称为根（root）的结点。
⑵当n>1时，其余结点分为ｍ（ｍ≥0）个互不相交的⼦集T1，T2，…，Tm。每个集合本⾝⼜是⼀棵树，并且称为根的⼦树（subtree）
树的固有特性---递归性。即⾮空树是由若⼲棵⼦树组成，⽽⼦树⼜可以由若⼲棵更⼩的⼦树组成。
树的基本操作
1、InitTree(&T)          初始化
2、DestroyTree(&T)    撤消树
3、CreatTree(&T,F)    按F的定义⽣成树
4、ClearTree(&T)      清除
5、TreeEmpty(T)        判树空
6、TreeDepth(T)          求树的深度
7、Root(T)                        返回根结点
8、Parent(T,x)              返回结点 x 的双亲
9、Child(T,x,i)              返回结点 x  的第i 个孩⼦
10、InsertChild(&T,&p,i,x)  把 x 插⼊到 P的第i棵⼦树处
11、DeleteChild(&T,&p,i)    删除结点P的第i棵⼦树
12、traverse(T)            遍历
树的结点：包含⼀个数据元素及若⼲指向⼦树的分⽀。
●结点的度:    结点拥有⼦树的数⽬
●叶结点:    度为零的结点
●分枝结点:    度⾮零的结点
●树的度:    树中各结点度的最⼤值
●孩⼦:    树中某个结点的⼦树的根
●双亲:    结点的直接前驱
●兄弟:    同⼀双亲的孩⼦互称兄弟
●祖先:    从根结点到某结点j 路径上的所有结点（不包括指定结点）。
●⼦孙:  某结点的⼦树中的任⼀结点称为该结点的⼦孙
●结点层次:  从根结点到某结点 j 路径上结点的数⽬（包括结点j）
●树的深度:    树中结点的最⼤层次
●有向树：结点间的连线是有向的。我们所讲的树都是有向的。
●有序树:    若树中结点的各⼦树从左到右是有次序的，称该树为有序树，否则为⽆序树
●森林:    由 m 棵互不相交的树构成    F=(T1,T2,.......Tm)
⼀棵树去掉根结点后就变成了森林。
⼆叉树的性质
⼆叉树的第i层结点数最多为2^(i-1)个(i>0)。
深度为K的⼆叉树⾄多有(2^k)-1个结点(K>0)。
对任何⼀棵⼆叉树，设n0,n1,n2分别是度为0,1,2的结点数，则有：n0＝n2+1
证明:
∵  n= n0+ n1 + n2    (n为结点总数)
b= n1 +2 n2        (b 为分⽀总数)
b=n-1      (除根结点外，任⼀结点都有分⽀连⼊⽗结点)
∴  n=b+1= n1 +2 n2 +1= n0+ n1 + n2
整理得:    n0 = n2 +1
具有n个结点的完全⼆叉树⾼度为
具有n个结点的完全⼆叉树具有如下特征：
① i=1  根结点，⽆双亲
i>1  其双亲结点为 (PARENT(i)= )
② 2i>n  结点i⽆左孩，否则  lchild(i)=2i
③ 2i+1>n 结点i⽆右孩，否则  rchild(i)=2i+1
⼆、⼆叉树三序遍历
2.1．实验内容
1.⽤先序递归遍历法建⼆叉树
2.输出三序递归遍历与层次遍历节点访问次序，三序遍历要求使⽤⾮递归和递归两种
3.⽤先序，中序遍历序列建⼆叉树
4.后序遍历复制⼀棵⼆叉树，计算叶⼦个数和树的深度
5.输出后序递归遍历及层次遍历结果
2.2.输⼊与输出
输⼊：输⼊建⽴⼆叉树的先序序列并且带‘#’，⽤以建树
输出：输出四种遍历的序列和⽤先序中序序列建成的⼆叉树
2.3．关键数据结构与算法描述
关键数据结构：⼆叉树的结构，节点，左孩⼦右孩⼦；栈的数据结构⽤以采⽤⾮递归⽅式遍历⼆叉树，循环队列的数据结构⽤以层次遍历⼆叉树。
具体代码如下：
1 typedef  struct  TreeNode
2 {
3    ElemType elem;
4struct TreeNode  *LChild,*RChild;
5 }BiTree,*BinaryTree;            //⼆叉树数据结构
6 typedef  struct Queue
7 {
8    BinaryTree value[MAXSIZE];
9int front,rear;
10 }LinkQueue;                    //队列数据结构
11 typedef  BinaryTree  ElemType1; //为BinaryTree起别名
12 typedef  struct Stack
13 {
14    ElemType1 StackElem[MAXSIZE];
15int top;
16 }STACK;                      //栈的数据结构
View Code
算法描述：⽤递归⽅法进⾏先序，中序，后序遍历都⼗分⽅便与简单，因为利⽤了树的左右结构。若树空时什么也不做，否则，按照便利的次序依次递归访问即可，如先序遍历：
//先序递归遍历
void  PreOrderTraverse(BinaryTree tree)
{
if(tree!=NULL)
{
visit(tree);
PreOrderTraverse(tree->LChild);
PreOrderTraverse(tree->RChild);
}
}
View Code
⽽对于⾮递归的三序遍历，就需要栈来做数据结构了，对于前序，中序遍历来说，只需要从根节点开始，⼀直往左⾛，直⾄最左边左⼦树为空，并且在这个过程中，若是先序遍历对于路上的节点都要访问并且⼊栈直⾄访问到到最左边的节点，然后退栈访问退栈节点的右⼦树；若是中序遍历则只需不断的向左⾛并且⼊栈但不访问，直⾄最左边，然后访问最左边节点。然后退栈并访问该节点，⽤同样的⽅法访问退栈节点的右⼦树。最后若栈为空，则访问完成。故此设⽴⼀个⼀直向左⾛访问并且⼊栈的函数如下（中序与此类似，暂不赘述）：
/***⼀直向左⾛直⾄获得最左边的指针*************/
BinaryTree  GofarleftVisit(BinaryTree  tree,STACK  *s)
{
if(!tree)
return NULL;      //若⽆树直接返回
BinaryTree  p=tree;
visit(p);              //先访问逻辑根节点
while(p->LChild)
{
push(s,p);        //把访问之后的⼊栈以便访问右⼦树
visit(p->LChild);  //访问左⼦树
p=p->LChild;      //不断向左移动直⾄为空
}
return  p;
}
⾮递归先序遍历的算法为：
//⽤⾮递归法先序访问
void  PreOrder(BinaryTree  tree)
{
if(!tree)
return ;
STACK s;
InitStack(&s);
BinaryTree  p;
p=GofarleftVisit(tree,&s);  //获得最左指针
while(p)
{
if(p->RChild)
p=GofarleftVisit(p->RChild,&s); //右边继续向左⾛
else
if(!IsEmptyStack(&s))
{
pop(&s,p);
}
else
p=NULL;    //栈空时退出
}
}
View Code
对于⾮递归后序遍历，根据其特点，先遍历左⼦树再遍历右⼦树，最后访问根节点。则需⽤两个指针cur和pre来分别标记当前指针和前⼀个指针的位置。注意压栈时先压根节点，再压右⼦树，最后左⼦树。若当前指针cur指向叶⼦节点则需访问，或者pre指针不为空并且pre指向的节点恰是当前指针指向的左或右节点则代表pre⼦树的下⼀层已经⽆树，并且若等于左指针则右边已⽆节点，（右边若有则访问完左边之后必然先访问右边⽽不会跳到头节点）；若等于右节点，则左边已访问完或⽆左边（因右边先压栈）。具体代码如下：
//⾮递归后序遍历
void postOrder(BinaryTree tree)
{
STACK s;
InitStack(&s);
BinaryTree  cur,pre=0;
push(&s,tree);
/*****⽤两个指针来判断，如果为叶⼦节点或者左右⼦树都访问过就访问该节点****/
while(!IsEmptyStack(&s))
{
cur=gettop(&s);
if((cur->LChild==NULL&&cur->RChild==NULL)||
(pre!=NULL&&(pre==cur->RChild||pre==cur->LChild)))
{  //注意pre只要与⼀个相等，若为左⼦树则⽆右⼦树；
//若为右⼦树则必然访问过左⼦树或⽆左⼦树
visit(cur);  //如果当前结点为叶⼦节点或者孩⼦节点都已被访问就访问
pop(&s,cur);
pre=cur;      //标记上次被访问的节点
}
else
{
if(cur->RChild!=NULL)
push(&s,cur->RChild); //注意先把右⼦树⼊栈再⼊左⼦树，才能保持先访问左⼦树后访问右⼦树，后进先出！
if(cur->LChild!=NULL)
push(&s,cur->LChild);
}
先序中序后序遍历二叉树
}
}
View Code
接下来是⽤队列数据结构层次遍历。其实就是迭代的过程，先访问头节点，然后进左⼉⼦，右⼉⼦。每次出队列后都要访问该节点，然后再看该节点是否有左
右⼦树若有则按照先左后右的顺序进队排在队尾等待遍历然后不断地循环迭代直⾄队为空则遍历结束。很容易理解！
具体代码如下：
//队列进⾏的⼆叉树层次遍历
void HierarchyBiTree(BinaryTree tree)
{
LinkQueue Q;  //注意此处不能是指针
InitQueue(&Q);
BinaryTree  p=tree;
if (tree==NULL)
return ;
visit(p);
if (p->LChild)
EnQueue(&Q,&p->LChild);  //若指针不空则⼊队列
if (p->RChild)
EnQueue(&Q, &p->RChild); //若指针不空则⼊队列
while (!IsEmpty(&Q))
{
DeQueue(&Q, &p);      //弹出指针进⾏访问
visit(p);
if (p->LChild)
EnQueue(&Q, &p->LChild);  //对指针所指的结构进⾏判断若左右⼦树不空
if (p->RChild)
EnQueue(&Q, &p->RChild);  //则先进左⼦树，后进右⼦树，以保证从左到右遍历
}
}
View Code
然后关于⼆叉树的复制，先复制左⼦树，然后复制右⼦树，最后复制头节点；在复制左右⼦树的时候同时也是复制树，故可⽤递归实现。同理，关于求叶⼦节点，求树的深度也是如此⽤递归即可实现，复制树的具体代码如下：
/************后序遍历复制⼀棵⼆叉树*************/
void  CopyBiTree(BinaryTree  tree,BinaryTree &newtree)
{
BinaryTree  lchild,rchild;
if(!tree)
{
newtree=NULL;
}
if(tree->LChild)//若左⼦树存在则递归复制
{
CopyBiTree(tree->LChild,lchild);
}
else
{
lchild=NULL; //否则为零
}
if(tree->RChild)
{
CopyBiTree(tree->RChild,rchild);
}
else
{
rchild=NULL;
}
newtree=(BinaryTree)malloc(sizeof(BiTree));
newtree->elem=tree->elem;
newtree->LChild=lchild;
newtree->RChild=rchild;
}
View Code
最后就是根据先序和中序序列建树，有⼀定的难度需要⽤到递归和分治法的⼀些知识。⾸先可以证明⽤先序，中序遍历序列是可以还原⼆叉树的，因为根据先序序列可以很清楚的知道⼆叉树的根节点就是第⼀个元素，然后以这个节点把中序序列分成两半，在这个节点左边的必是左⼦树（因为是中序序列），⽽在其右边的是右⼦树，⽽左⼦树右⼦树有是⼀个树，故可以在更⼩的范围内到左⼦树的根节点，在以该节点为分界点，在更⼩的范围内查下去，右⼦树也是如此。在递归的过程中要注意进⾏⽐较的两个序列长度必然要相等，递归终⽌的条件就是左边分到不能再⽐，右边也向右不能再⽐为⽌。这样也就在递归中建⽴了⼆叉树。具体代码如下：
//⾸先得到中序序列⼆分后左边的长度
int get_left_len(int rootpos,int in_begin,int in_end,char * pre_order,char * in_order )
{
for(int i = in_begin; i <= in_end; i++)
{
if(in_order[i] == pre_order[rootpos])
{
return i-in_begin;  //以双亲节点为分界点划分，返回左边的真实长度
}
}
return -1;                //若没有则返回负值，⽤于判断
}
void creat(BinaryTree *pnode,int pre_begin,int pre_end,int in_begin,int in_end, char * pre_order,char * in_order)
{
*pnode =(BinaryTree)malloc(sizeof(BiTree)); //申请空间
BinaryTree temp = *pnode;                  //创建遍历指针
temp->elem = pre_order[pre_begin];          //开始必为根节点
temp->LChild = NULL;                        //⼀定要初始化为0
temp->RChild = NULL;
if(pre_begin == pre_end)
{
return ;            //只有⼀个节点，则已创建完毕
}
int left_len = get_left_len(pre_begin,in_begin,in_end,pre_order,in_order);
if(left_len > 0)    //若没有会返回-1；若为0，则上⾯已创建；否则创建左⼦树
{
creat(&temp->LChild,pre_begin+1,pre_begin+left_len,
in_begin,in_begin+left_len-1,pre_order,in_order);
}
if(left_len < (in_end - in_begin)) //若left_len+inbegin>in_end-1则已经结束，否则创建右⼦树    {
creat(&temp->RChild,pre_begin+left_len+1,pre_end,
in_begin+left_len+1,in_end,pre_order,in_order);
}
}
View Code
2.4.测试与理论
具体的测试与理论见下图
测试数据⼀：
先序遍历：ABDFCEG
中序遍历：DFBAECG
后序遍历：FDBEGCA
输⼊数据:  ABD#F###CE##G##
对于测试先序和中序序列建树的序列为
char * pre_order = "ABDEGJCFHIK";//先序序列
char * in_order = "DBGJEACFIKH"; //中序序列
输出结果截图：
测试数据⼆：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。