6.2   二  叉 树 

6.2.1   二叉树的定义

二叉树（Binary Tree）：和树不同的树型结构

（1） 每个结点的度都不大于2；

（2） 有序树：每个结点的孩子结点次序不能任意颠倒     

二叉树的重要特性

性质1: 在二叉树的第i层上至多有2i-1个结点(i≥1) 

性质2: 深度为k的二叉树至多有2k-1个结点（k≥1）

性质3: 对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1

性质4：具有n个结点的完全二叉树的深度为  log2n  +1

性质5:  对于具有n个结点的完全二叉树， 如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号， 则对于任意的序号为i的结点有：

满二叉树： 深度为k且有2k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。 

完全二叉树： 深度为k，结点数为n的二叉树，如果其结点1~n的位置序号分别与满二叉树的结点1~n的位置序号一一对应，则为完全二叉树。 

6.3顺序存储结构 

链式存储结构

 对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。我们可以设计每个结点至少包括三个域：数据域、 左孩子域和右孩子： 

6.3二叉树的遍历

先序遍历（DLR）操作过程：

若二叉树为空， 则空操作， 否则依次执行如下3个操作：

² 访问根结点；

² 按先序遍历左子树；

² 按先序遍历右子树。 

中序遍历（LDR）操作过程：

   若二叉树为空， 则空操作， 否则依次执行如下3个操作： 

² 按中序遍历左子树；

² 访问根结点；

² 按中序遍历右子树。

后序遍历（LRD）操作过程：

   若二叉树为空， 则空操作， 否则依次执行如下3个操作： 

² 按后序遍历左子树；

² 按后序遍历右子树；

² 访问根结点。 

VoidPreorder(BiTreeT, void( *visit)(TElemType& e))

{ // 先序遍历二叉树 

   if (T) {

      visit(T->data);            // 访问结点

      Preorder(T->lchild, visit); // 遍历左子树

      Preorder(T->rchild, visit);// 遍历右子树

   }

}

BiTNode *GoFarLeft(BiTree T, Stack *S){

   if (!T )  return NULL;

   while (T->lchild ){

      Push(S, T);

      T = T->lchild;

   }

   return T;

}

voidInorder_I(BiTreeT,void(*visit)                                  (TelemType& e)){

   Stack *S;

   t = GoFarLeft(T, S);  // 找到最左下的结点

   while(t){

      visit(t->data);

      if (t->rchild)

         t = GoFarLeft(t->rchild, S);

     else if ( !StackEmpty(S ))    // 栈不空时退栈

        t = Pop(S);

              else    t = NULL; // 栈空表明遍历结束

    } // while

}// Inorder_I           

五、遍历算法的应用举例

1、统计二叉树中叶子结点的个数

先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。

由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。

void CountLeaf (BiTree T,  int& count){

   if ( T ) {

      if ((!T->lchild)&& (!T->rchild))

         count++;     // 对叶子结点计数

      CountLeaf( T->lchild, count);  

      CountLeaf( T->rchild, count);

   } // if

} // CountLeaf

2、求二叉树的深度(后序遍历)

从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。

int Depth (BiTree T ){ // 返回二叉树的深度

   if ( !T )    depthval = 0;

   else   {

     depthLeft = Depth( T->lchild );

     depthRight= Depth( T->rchild );

     depthval = 1 + (depthLeft > depthRight  ?

                               depthLeft : depthRight);

   } 

   return depthval;

}

3、复制二叉树

BiTNode *GetTreeNode(TElemType item,

          BiTNode *lptr , BiTNode *rptr ){

    if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))

       exit(1);

    T-> data = item;

    T-> lchild = lptr;    T-> rchild = rptr;

    return T;

}

BiTNode *CopyTree(BiTNode *T) {  

    if (!T )    return NULL;

    if (T->lchild )

         newlptr = CopyTree(T->lchild);//复制左子树

    else  newlptr = NULL;

    if (T->rchild )

        newrptr = CopyTree(T->rchild);//复制右子树

    else  newrptr = NULL;

    newT = GetTreeNode(T->data, newlptr, newrptr);

    return newT;

} // CopyTree