数据结构第六章-二叉树.ppt

* void Countleaf(BiTree T) {if (T) { if (T-lchild==NULL T-rchild==NULL) N++; /*若T为叶子，则累加 */ Countleaf (T-lchild); /*统计左子树中的叶子*/ Countleaf (T-rchild); /*统计右子树中的叶子*/ } } 调用前N的初值为0 注意：N需要在递归调用的各个子函数中有效，所以N必须是全局变量 * void Countleaf(BiTree T) {if (T) { if (T-lchild==NULL T-rchild==NULL) N++; /*若T为叶子，则累加 */ Countleaf (T-lchild); /*统计左子树中的叶子*/ Countleaf (T-rchild); /*统计右子树中的叶子*/ } } int N=0; main() {BiTree T; …… /*建立二叉链表结构*/ Countleaf(T); printf(“the numbers of leaf: %d \n”, N); } * 2.中序遍历（LDR） 若二叉树为空，遍历结束。否则，（1）中序遍历根结点的左子树（2）访问根结点 （3）中序遍历根结点的右子树 中序遍历序列：D,B,G,E,A,C,F 例：中序遍历右图所示的二叉树： （1）中序遍历A的左子树：即按LDR的顺序遍历A的左子树 （2）访问根结点A （3）中序遍历A的右子树：即按LDR的顺序遍历A的右子树 A B C D E F G 问题：如何确定中序遍历过程中的第一个结点? 从根结点向左子树查找，第一个左子树为空的结点。 * ?void InOrder (BiTree T) { if (T==NULL) return; /*递归遍历结束*/ InOrder(T-lchild); /*中序遍历T的左子树*/ Visit(T-data)； /*访问根结点*/  InOrder(T-rchild); /*中序遍历T的右子树*/} 中序遍历递归算法： * A D B C L D R B L D R L D R A D C L D R 中序遍历序列：B D A C 中序遍历过程示例: * 3.后序遍历（LRD） 若二叉树为空，则遍历结束。否则，（1）后序遍历根结点的左子树（2）后序遍历根结点的右子树 （3）访问根结点 后序遍历序列： G,D,B,E,F,C,A 例：后序遍历右图所示的二叉树 （1）后序遍历A的左子树：即按LRD的顺序遍历A的左子树 （2）后序遍历A的右子树：即按LRD的顺序遍历A的右子树 （3）访问根结点A 问题：如何确定后序遍历过程中的第一个结点? 从根结点向左子树查找，找到第一个左子树为空的结点，接着向右子树找，至一叶子结点。 A B E F D G C * void PostOrder(BiTree T) { if(T==NULL) return; PostOrder(T-lchild); PostOrder(T-rchild); Visit(T-data); } 后序遍历递归算法： * A D B C L R D L R D L R D A D C L R D 后序遍历序列： D B C A 后序遍历过程示例: B * 6.2.2 由遍历序列恢复二叉树 任意一棵二叉树结点的先序序列和中序序列都是惟一的。反过来，若已知结点的先序序列和中序序列，也能惟一地确定这棵二叉树。 ※ 在先序序列中，第一个结点一定是二叉树的根结点 ※ 中序序列必然以根为界分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列 ※ 在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列中的第一个结点是右子树的根结点 ※ 左子树和右子树的根结点又在中序序列中分别把左子序列和右子序列划分成两个子序列 ……，如此递归下去，当取尽先序序列中的结点时，便可以得到一棵二叉树。 先序序列 中序序列 左子树 左子树 右子树 右子树 根 根 * 例：已知一棵二叉树的先序序列和中序序列分别为: 先序序列：