二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施

     操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就  

     是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比

     较、更新、查看元素内容等等各种操作。

     二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按

     层次访问。下面我们将分别进行讨论。

    1、 按根、左子树和右子树三部分进行遍历

遍历二叉树的顺序存在下面6种可能：

    TLR（根左右）, TRL（根右左）

    LTR（左根右）, RTL（右根左）

    LRT（左右根）, RLT（右左根）

     其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右

的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别

被称为先序遍历、中序遍历和后序遍历。

（1）先序遍历

若二叉树为空，则结束遍历操作；否则

访问根结点；

先序遍历左子树；

先序遍历右子树。

（2）中序遍历若二叉树为空，则结束遍历操作；否则

中序遍历左子树；

访问根结点；

中序遍历右子树。

（3）后序遍历

若二叉树为空，则结束遍历操作；否则

后序遍历左子树；

后序遍历右子树；

访问根结点。

例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列

二叉树的两种遍历方法：

（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左

侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的

水平线上，由此得到的顺序就是该二叉树的中序遍历序列

（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，

这条包线对于理解二叉树的遍历过程很有用。

     由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，

并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的

过程，因此，这三种遍历操作的算法可以用递归函数实现。

（1）先序遍历递归算法
void PreOrder(BTree BT) {
      if (BT) { Visit(BT);
      PreOrder(BT->Lchild);
      PreOrder(BT->Rchild);
}

（2）中序遍历递归算法
void InOrder(BTree BT) {
      if (BT) {
         InOrder(BT->Lchild);
         Visit(BT);
         InOrder(BT->Rchild);
       }
    }

（3）后序遍历递归算法
void PostOrder(BTree BT) {
     if (BT) {
        PostOrder(BT->Lchild);
        PostOrder(BT->Rchild);
        Visit(BT);
       }
    }

   2 、按层次遍历二叉树

     实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵

二叉树及其按层次顺序访问其中每个结点的遍历序列。

void LevelOreder(QBTree BT) {
     for (i=1;i<=BT.n;i++)
     if (BT.elem[i]!='#') Visite(BT.elem[i]);
}

二叉树用链式存储结构表示时，按层遍历的算法实现

访问过程描述如下：

访问根结点，并将该结点记录下来；

若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。

取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；

若它有右孩子，则访问右孩子，并记录下来。

     在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；

     而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：

（1）访问根结点，并将根结点入队；

（2）当队列不空时，重复下列操作：

从队列退出一个结点；

若其有左孩子，则访问左孩子，并将其左孩子入队；

若其有右孩子，则访问右孩子，并将其右孩子入队；

void LevelOrder(BTree *BT) {
      if (!BT) exit;
      InitQueue(Q); p=BT; //初始化
      Visite(p); EnQueue(&Q,p); //访问根结点，并将根结点入队
      while (!QueueEmpty(Q)) { //当队非空时重复执行下列操作
      DeQueue(&Q,&p); //出队
      if (!p->Lchild) {Visite(p->Lchild);EnQueue(&Q,p->Lchild); //处理左孩子
      if (!p->Rchild) {Visite(p->Rchild);EnQueue(&Q,p->Rchild); //处理右孩子
   }
}

   五、典型二叉树的操作算法

     1、 输入一个二叉树的先序序列，构造这棵二叉树

     为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉

    树的位置上填补一个特殊的字符，比如，'#'。在算法中，需要对每个输入的字符进行判

    断，如果对应的字符是'#'，则在相应的位置上构造一棵空二叉树；否则，创建一个新结

    点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针

    参数在递归调用返回时完成。

算法：

BTree Pre_Create_BT( ) {
      getch(ch);
      if (ch=='#') return NULL;                     //构造空树
      else { BT=(BTree)malloc(sizeof(BTLinklist)); //构造新结点
      BT->data=ch;
      BT->lchild =Pre_Create_BT( );                 //构造左子树
      BT->rchild =Pre_Create_BT( );                 //构造右子树
      return BT;
    }
}

   2、 计算一棵二叉树的叶子结点数目

     这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否

     为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。

算法：

void Leaf(BTree BT,int *count) {
      if (BT) {
      Leaf(BT->child,&count); //计算左子树的叶子结点个数
      if (BT->lchild==NULL&&BT->rchild==NULL) (*count)++;
      Leaf(BT->rchild,&count); //计算右子树的叶子结点个数
    }
}

   3、 交换二叉树的左右子树

     许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一  

些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右

子树进行交换这个操作就属于这类情况。

算法：

void change_left_right(BTree BT) {
      if (BT) {
         change_left_right(BT->lchild);
         change_left_right(BT->rchild);
         BT->lchild<->BT->rchild;
       }
   }

   4 、求二叉树的高度

     这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树

的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。

算法：

int hight(BTree BT) {     //h1和h2分别是以BT为根的左右子树的高度
     if (BT==NULL) return 0;
     else {
         h1=hight(BT->lchild);
         h2=hight(BT->right);
         return max{h1,h2}+1;
        }
   }

   六、树、森林与二叉树的转换

   1、 树、森林转换成二叉树

     将一棵树转换成二叉树的方法：

     将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每

个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将

这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。

     特点：一棵树转换成二叉树后，根结点没有右孩子。

     将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根

      结点看作兄弟关系，并对其中的每棵树依依地进行转换。

    2 、二叉树还原成树或森林

     这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子

兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下

走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这

个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到

为空，途经的结点个数就是这个结点的孩子数目。