数据结构与算法系列研究五——树、二叉树、三叉树、平衡排序二叉树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;
 4     struct TreeNode  *LChild,*RChild;
 5 }BiTree,*BinaryTree;            //二叉树数据结构
 6 typedef  struct Queue
 7 {
 8     BinaryTree value[MAXSIZE];
 9     int front,rear;
10 }LinkQueue;                     //队列数据结构
11 typedef  BinaryTree  ElemType1; //为BinaryTree起别名
12 typedef  struct Stack
13 {
14     ElemType1 StackElem[MAXSIZE];
15     int 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);  //则先进左子树，后进右子树，以保证从左到右遍历
        }
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-121392-1.html