1.先序遍历(DLR) 先序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1)访问根结点： (2)先序遍历根结点的左子树： (3)先序遍历根结点的右子树。 先序骗历二叉树的涕归算法如下： void PreOrder (BiTree bt) /先序遍历二叉树bt/ if(bt=-NULL)return; 序递归调用的结束条件 Visite (bt->data); 访问结点的数据域 PreOrder (bt->Ichild): 先序递归崩历bt的左子树*/ PreOrder (bt->rchild): 严先序递归遍历以的右子树制 算法6.5 对于图6图6.3(6)所示的二叉树，按先序遍历所得到的结点序列为： ABDGCEF 2.中序遍历LDR) 中序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1)中序遍历根结点的左子树： (2)访问根结点： (3)中序遍历根结点的右子树 中序遍历二叉树的递归算法如下： void InOrder (BiTree bt) 体中序遍历二叉树bt/ if(bt-NULL)return. 递归调用的结束条件 InOrder (bt->lchild) 摩中序递归遗历bt的左子树* Visite (bt->data); 访问结点的数据域 InOrder (bt->rchild); 体中序递归遍历的右子树制 } 算法6.6 对于图6.3(6)所示的二叉树，按中序遍历所得到的结点序列为： DGBAECF 113
113 1．先序遍历（DLR） 先序遍历的递归过程为：若二叉树为空，遍历结束。否则， （1）访问根结点； （2）先序遍历根结点的左子树； （3）先序遍历根结点的右子树。 先序遍历二叉树的递归算法如下： void PreOrder（BiTree bt） {/*先序遍历二叉树bt*/ if (bt==NULL) return; /*递归调用的结束条件*/ Visite（bt->data）; /*访问结点的数据域*/ PreOrder（bt->lchild）; /*先序递归遍历 bt 的左子树*/ PreOrder（bt->rchild）; /*先序递归遍历 bt 的右子树*/ } 算法 6.5 对于图 6 图 6.3(b)所示的二叉树，按先序遍历所得到的结点序列为： A B D G C E F 2．中序遍历（LDR） 中序遍历的递归过程为：若二叉树为空，遍历结束。否则， （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 中序遍历二叉树的递归算法如下： void InOrder（BiTree bt） {/*中序遍历二叉树bt*/ if (bt==NULL) return; /*递归调用的结束条件*/ InOrder（bt->lchild）; /*中序递归遍历 bt 的左子树*/ Visite（bt->data）; /*访问结点的数据域*/ InOrder（bt->rchild）; /*中序递归遍历 bt 的右子树*/ } 算法 6.6 对于图 6.3(b)所示的二叉树，按中序遍历所得到的结点序列为： D G B A E C F
3.后序遍历(LRD) 后序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1)后序遍历根结点的左子树： (2)后序遍历根结点的右子树。 (3)访问根结点： 后序遍历二叉树的递归算法如下： void PostOrder (BiTree bt) {俨后序遍历二叉树bt/ if(bt=-NULL)return; 递归调用的结束条件 PostOrder (bt->lchild): 体后序递归海历bt的左子树 PostOrder (bt->rchild); 后序递归遍历t的右子树 Visite (bt->data): 摩访问结点的数据域·/ 算法6.7 对于图图6.3(6)所示的二叉树，按先序遍历所得到的结点序列为： GDBEFCA 4.层次遍历 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历， 在同一层中，则按从左到右的顺序对结点逐个访问。对于图6.3(6)所示的二叉树，按层次 遍历所得到的结果序列为： ABCDEFG 下面讨论层次遍历的算法。 由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后，再按照它们 的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先 访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构， 遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取 一个元素，执行下面两个操作： (1)访问该元素所指结点： (2)若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针 和右孩子指针顺序入队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。 在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组Queue[MAXNODE]用 以实现队列，变量ot和rear分别表示当前对首元素和队尾元素在数组中的位置。 114
114 3．后序遍历（LRD） 后序遍历的递归过程为：若二叉树为空，遍历结束。否则， （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树。 （3）访问根结点； 后序遍历二叉树的递归算法如下： void PostOrder（BiTree bt） {/*后序遍历二叉树bt*/ if (bt==NULL) return; /*递归调用的结束条件*/ PostOrder（bt->lchild）; /*后序递归遍历 bt 的左子树*/ PostOrder（bt->rchild）; /*后序递归遍历 bt 的右子树*/ Visite（bt->data）; /*访问结点的数据域*/ } 算法 6.7 对于图图 6.3(b)所示的二叉树，按先序遍历所得到的结点序列为： G D B E F C A 4．层次遍历 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历， 在同一层中，则按从左到右的顺序对结点逐个访问。对于图 6.3(b)所示的二叉树，按层次 遍历所得到的结果序列为： A B C D E F G 下面讨论层次遍历的算法。 由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后，再按照它们 的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先 访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构， 遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取 一个元素，执行下面两个操作： （1）访问该元素所指结点； （2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针 和右孩子指针顺序入队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。 在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组 Queue[MAXNODE]用 以实现队列，变量 front 和 rear 分别表示当前对首元素和队尾元素在数组中的位置
void LevelOrder (BiTree bt) 层次演历二叉树bt*/ BiTree Queue[MAXNODE]; int frontrear, if (bt==NULL)retum front=-1; rear=0: queue[rear]=bt; while(front!=rear) (front++; Visite(queue[front]>data),访问队首结点的数据域y if(queue[[firont]-childl=-NULL)将队首结点的左孩子结点入队列/ (rear++: queue[rear]=queue[front]->lchild if(queue[font>rchild=NULL)将队首结点的右孩子结点入队列 rear++: queue[rear]=queue[front]->rchild 算法6.8 6.3.2二叉树遍历的非递归实现 前面给出的二叉树先序、中序和后序三种遍历算法都是递归算法。当给出二叉树的链 式存储结构以后，用具有递归功能的程序设计语言很方便就能实现上述算法。然而，并非 所有程序设计语言都允许递归：另一方面，递归程序虽然简洁，但可读性一股不好，执行 效率也不高。因此，就存在如何把一个递归算法转化为非递归算法的问题。解决这个问题 的方法可以通过对三种遍历方法的实质过程的分析得到。 如图6.3(6)所示的二叉树，对其进行先序、中序和后序遍历都是从根结点A开始的， 且在遍历过程中经过结点的路线是一样的，只是访问的时机不同而己。图6.9中所示的从 根结点左外侧开始，由根结点右外侧结束的曲线，为遍历图6.3(6)的路线。沿着该路线按 △标记的结点读得的序列为先序序列，按标记读得的序列为中序序列，按⊕标记读得的序 列为后序序列。 然而，这一路线正是从根结点开始沿左子树深入下去，当深入到最左端，无法再深入 下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回， 115
115 void LevelOrder（BiTree bt） /*层次遍历二叉树 bt*/ { BiTree Queue[MAXNODE]; int front,rear; if (bt==NULL) return; front=-1; rear=0; queue[rear]=bt; while(front!=rear) {front++; Visite(queue[front]->data); /*访问队首结点的数据域*/ if (queue[front]->lchild!=NULL) /*将队首结点的左孩子结点入队列*/ { rear++; queue[rear]=queue[front]->lchild; } if (queue[front]->rchild!=NULL) /*将队首结点的右孩子结点入队列*/ { rear++; queue[rear]=queue[front]->rchild; } } } 算法 6.8 6.3.2 二叉树遍历的非递归实现 前面给出的二叉树先序、中序和后序三种遍历算法都是递归算法。当给出二叉树的链 式存储结构以后，用具有递归功能的程序设计语言很方便就能实现上述算法。然而，并非 所有程序设计语言都允许递归；另一方面，递归程序虽然简洁，但可读性一般不好，执行 效率也不高。因此，就存在如何把一个递归算法转化为非递归算法的问题。解决这个问题 的方法可以通过对三种遍历方法的实质过程的分析得到。 如图6.3(b)所示的二叉树，对其进行先序、中序和后序遍历都是从根结点 A 开始的， 且在遍历过程中经过结点的路线是一样的，只是访问的时机不同而已。图 6.9 中所示的从 根结点左外侧开始，由根结点右外侧结束的曲线，为遍历图 6.3(b)的路线。沿着该路线按 △标记的结点读得的序列为先序序列，按*标记读得的序列为中序序列，按⊕标记读得的序 列为后序序列。 然而，这一路线正是从根结点开始沿左子树深入下去，当深入到最左端，无法再深入 下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回