哈工大数据结构6

1、第第6章章 树和二叉树树和二叉树树是一种重要的非线性结构。树是一种重要的非线性结构。树是以分支关系定义的层次结构，其中以二叉树最为常用。树是以分支关系定义的层次结构，其中以二叉树最为常用。树型结构在计算机中有广泛应用：树型结构在计算机中有广泛应用： 在微机操作系统中，文件和文件夹以树形结构存储。在微机操作系统中，文件和文件夹以树形结构存储。 在编译系统中，可以用树来表示源程序的语法结构。在编译系统中，可以用树来表示源程序的语法结构。 在数据库系统中，树型结构是信息的重要组织形式。在数据库系统中，树型结构是信息的重要组织形式。6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二

2、叉树二叉树6.3 6.3 遍历二叉树遍历二叉树6.4 6.4 恢复二叉树恢复二叉树6.7 6.7 树和森林树和森林6.8 6.8 哈夫曼树及其应用哈夫曼树及其应用6.5 6.5 线索二叉树线索二叉树6.6 6.6 二叉树的基本运算及其应用二叉树的基本运算及其应用6.1 6.1 树的定义和基本术语树的定义和基本术语数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D为空集，则称为空树为空集，则称为空树 。 否则否则: (1) 在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root； (2) 当当n1时，其余结点可分为时，其余结点可分为m

3、 (m0)个互不相交的个互不相交的 有限集有限集T1, T2, , Tm， 其中每一棵子集本身又是其中每一棵子集本身又是 一棵符合本定义的树，称为根一棵符合本定义的树，称为根 root 的子树。的子树。 数据关系数据关系 R：1. 1. 树的定义树的定义 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类 Root(T) / 求树的根结点求树的根结点 查找类：查找类：Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最

4、左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历InitTree(&T) / 初始化置空树初始化置空树 插入类：插入类：CreateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的

5、树插入为结点为根的树插入为结点 p 的第的第i 棵子树棵子树 ClearTree(&T) / 将树清空将树清空 删除类：删除类：DestroyTree(&T) / 销毁树的结构销毁树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i 棵子树棵子树ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2树根例例: : 树的特点：树的特点： 在非空树中：在非空树中：树中至少有一个结点树中至少有一个结点根。根。树中各子树是互不相交的集合。树中各子树是互不相交的集合。 树的定义是树的定义是递归的递归的，即在树的定

6、义中又用到树的概念，即在树的定义中又用到树的概念，正好反映了树的固有特性。正好反映了树的固有特性。 A只有根结点的树只有根结点的树ABCDEFGHIJKLM有子树的树有子树的树根根子树子树() 有确定的根；有确定的根；() 树根和子树根之间为有向关系。树根和子树根之间为有向关系。有向树：有向树：有序树：有序树：子树之间存在确定的次序关系。子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。子树之间不存在确定的次序关系。对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结

7、点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )结点结点(node)表示树中的元素，包括数据项及若干指向其子树的表示树中的元素，包括数据项及若干指向其子树的 分支。分支。结点的度结点的度(degree)结点拥有的子树个数。结点拥有的子树个数。叶子叶子(leaf)度为度为0的结点。的结点。孩子孩子(child)结点子树的根称为该结点的孩子。结点子树的根称为该结点的孩

8、子。双亲双亲(parents)孩子结点的上层结点叫该结点的双亲或父结点。孩子结点的上层结点叫该结点的双亲或父结点。兄弟兄弟(sibling)同一双亲的孩子。同一双亲的孩子。树的度树的度 一棵树中各结点的度的最大值称为该树的度。一棵树中各结点的度的最大值称为该树的度。2.2.树的基本术语树的基本术语结点的层次结点的层次(level)根结点的层数为根结点的层数为1，其余结点的层数等于，其余结点的层数等于 它双亲结点的层数加它双亲结点的层数加1。树的深度树的深度(depth)树中结点的最大层次数。树中结点的最大层次数。森林森林(forest)m(m 0)棵互不相交的树的集合棵互不相交的树的集合。(

9、(从根到结点的从根到结点的) )路径路径由从根到该结点所经分支和结点构成。由从根到该结点所经分支和结点构成。ABCDEFGHIJMKL任何一棵非空树是一个二元组：任何一棵非空树是一个二元组： Tree = Tree = （rootroot，F F）其中：其中：root root 被称为根结点。被称为根结点。 F F 被称为子树森林。被称为子树森林。森林：是森林：是m m（m0m0）棵互不相棵互不相 交的树的集合。交的树的集合。ArootBCDEFGHIJMKLF任何一棵树，只要删去根结点就成了森林。如图：任何一棵树，只要删去根结点就成了森林。如图：(a) 树树 (b) 移去根结点后成为森林移去

10、根结点后成为森林ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先bacghdefij树型表示树型表示树的表示：树的表示：abdeijfcgh嵌套集合表示嵌套集合表示嵌

11、套括号表示嵌套括号表示ijdfghabcea ( b ( d, e ( i, j ), c ( g, h ) ) )6.2 6.2 二叉树二叉树1. 二叉树的定义二叉树的定义 二叉树是有二叉树是有n（n=0）个结点的有限集合。）个结点的有限集合。 （1）该集合或者为空（）该集合或者为空（n=0）；）； （2）该集合或者只有一个根结点；）该集合或者只有一个根结点； （3）该集合或者由一个根结点及两个不相交的分别称为）该集合或者由一个根结点及两个不相交的分别称为 左子树和右子树组成的非空树；左子树和右子树组成的非空树； （4）左子树和右子树同样又都是二叉树。）左子树和右子树同样又都是二叉树。二叉树

12、的定义是递归的：二叉树的定义是递归的：在一棵非空的二叉树中，每个结点至多只有两棵子树，在一棵非空的二叉树中，每个结点至多只有两棵子树，分别称为左子树和右子树，左子树和右子树同样又都是二分别称为左子树和右子树，左子树和右子树同样又都是二叉树。叉树。二叉树是有序树：二叉树是有序树： 二叉树的左右子树的次序不能交换。二叉树的左右子树的次序不能交换。ABCDEFGHK根结点根结点左子树左子树右子树右子树二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树 二叉树的基本操作：二叉树的基

13、本操作：查查 找找 类类插插 入入 类类删删 除除 类类 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); InitBiTree(

14、&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);二叉树的二叉树的主要主要基本操作：基本操作： （1） CreateBT（）：（）： 创建一棵二叉树。创建一棵二叉树。 （2）ShowTree(BT *T)：按凹入法显示二叉树。：按凹入法显示二叉树。（3） Preorder(BT *T)：按先序（根、左、右）遍历二叉树上：按先序（根、左、右）遍历二叉树上 所有结点。所有结

15、点。（4） Inorder(BT *T)： 按中序（左、根、右）遍历二叉树上按中序（左、根、右）遍历二叉树上 所有结点。所有结点。（5）Postorder(BT *T)：按后序（左、右、根）遍历二叉树上：按后序（左、右、根）遍历二叉树上 所有结点。所有结点。 （6）Levelorder(BT *T)：按层次遍历二叉树上所有结点。：按层次遍历二叉树上所有结点。（7）Leafnum(BT *T)： 求二叉树叶子结点总数。求二叉树叶子结点总数。（8）TreeDepth(BT *T)： 求二叉树的深度。求二叉树的深度。2. 二叉树的性质二叉树的性质 性质性质1：一棵非空二叉树的第：一棵非空二叉树的第

16、i 层上最多有层上最多有 2i1 个结点（个结点（i 1）。）。证明：用归纳法证明之证明：用归纳法证明之 i=1时，只有一个根结点，时，只有一个根结点， 成成立立 假设对所有假设对所有j(1 ji)命题成立，即第命题成立，即第j层上至多有层上至多有 个个结点结点。那么，第那么，第i-1层至多有层至多有 个结点。个结点。须证明须证明 j=i 时命题也成立。时命题也成立。 因为因为二叉树每个结点的度至多为二叉树每个结点的度至多为2 第第i层上最大结点数是第层上最大结点数是第i-1层的层的2倍，即倍，即 故命题得证故命题得证。12201i12j22i12222ii性质性质2： 深度为深度为 k 的二

17、叉树中，最多具有的二叉树中，最多具有 2k - 1 个结点。个结点。证明：证明： 根据性质根据性质1，当深度为，当深度为 k 的二叉树每一层都达到最多结点的二叉树每一层都达到最多结点时，它的和最大，即：时，它的和最大，即：122)(111kkikiii层的最大结点数第两类特殊的二叉树：两类特殊的二叉树：满二叉树：满二叉树：定义：一棵深度为定义：一棵深度为 k 且有且有 2k 1个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。特点：满二叉树每一层上的结点都具有最大的结点数。特点：满二叉树每一层上的结点都具有最大的结点数。123114589121367101415深度为深度为 k=4 k=4

18、 的满二叉树的满二叉树完全二叉树：完全二叉树：定义：定义：深度为深度为 k k，有有 n n 个结点的二叉树，当且仅当其每一个结点个结点的二叉树，当且仅当其每一个结点 都与深度为都与深度为 k k 的满二叉树中编号从的满二叉树中编号从 1 1 至至 n n 的结点一一对的结点一一对 应时，称为应时，称为完全二叉树。完全二叉树。特点：特点：叶子结点只可能在层次最大的两层上出现。叶子结点只可能在层次最大的两层上出现。 对任一结点，若其右分支下子孙的最大层次为对任一结点，若其右分支下子孙的最大层次为 L L，则其左分则其左分 支下子孙的最大层次必为支下子孙的最大层次必为 L L 或或 L+1L+1完

19、全二叉树完全二叉树1231145891267101234567123456特点：完全二叉树除最后一层外，其余各层都是满的；特点：完全二叉树除最后一层外，其余各层都是满的； 并且最后一层或者为满，或者仅在右边缺少连续若干并且最后一层或者为满，或者仅在右边缺少连续若干 个结点。个结点。性质性质3：1log2nn深度为个结点的完全二叉树的具有不大于不大于x的的最大整数最大整数证明：证明：设完全二叉树的深度为设完全二叉树的深度为 k k，结点数为结点数为 n n， 由性质由性质2 2和完全二叉树的定义可知：和完全二叉树的定义可知： 2k-1-1n 2k-1 即即 2k-1 n 2k 两边取对数有：两边

20、取对数有： k-1 log2n 1, 1, 则序号为则序号为 i i 的结点的父结点的序号为的结点的父结点的序号为 i/2i/2。(2)(2)若若 2 2i in n， 则序号为则序号为 i i 的结点无左孩子。的结点无左孩子。(3)(3)若若 2 2i+1i+1n n，则序号为则序号为 i i 的结点无右孩子。的结点无右孩子。性质性质5：对任何一棵二叉树对任何一棵二叉树T，如果其终端结点数为如果其终端结点数为 n0，度为度为 2 的的 结点数为结点数为 n2，则则 n0=n2+1 。证明：证明：n1为二叉树为二叉树 T 中度为中度为 1 的结点数的结点数 因为：二叉树中所有结点的度均小于或等

21、于因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一个又二叉树中，除根结点外，其余结点都只有一个 分支进入分支进入 设设B为分支总数，则为分支总数，则 n=B+1 又：分支由度为又：分支由度为1和度为和度为2的结点射出，的结点射出， B=n1+2n2 于是，于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+13. 二叉树的存储结构二叉树的存储结构(1)(1) 顺序存储结构顺序存储结构 一维数组存储法：一维数组存储法：实现：按完全二叉树的结点层次编号，依次存放二叉树中的数据元素。实现：按完全二叉

22、树的结点层次编号，依次存放二叉树中的数据元素。特点：结点间关系蕴含在其存储位置中（特点：结点间关系蕴含在其存储位置中（i 的左子的左子2i，右子，右子2i+1）。）。abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11特点：特点： 浪费空间，适于存满二叉树和完全二叉树。浪费空间，适于存满二叉树和完全二叉树。aceda 0 c 0 0 0 d 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1400e无须无须按完全二叉树的结点层次编号，依次按编号存放二叉树中的数据按完全二叉树的结点层次编号，依次按编号存放二叉树中的数

23、据元素即可。元素即可。结点数据，左子编号，右子编号均要存储。故可采用长度为结点数据，左子编号，右子编号均要存储。故可采用长度为 n 的结构的结构 数组存放。数组存放。n为结点个数。为结点个数。结构数组相当于一个二维构造结构数组相当于一个二维构造, 第一维是结构数组元素第一维是结构数组元素, 每个元素是一每个元素是一 个结构变量个结构变量, 第二维是结构成员。第二维是结构成员。 abcdefg0123456Data0Lno1Rno20a121b342c-1-13d-1-14e565f-1-16g-1-1 二维数组存储法：二维数组存储法：顺序存储结构小结：顺序存储结构小结：满二叉树或完全二叉树可采

24、用一维数组；满二叉树或完全二叉树可采用一维数组；结点少，层数高可采用二维数组；结点少，层数高可采用二维数组；查找方便，找孩子结点及父结点均方便；查找方便，找孩子结点及父结点均方便；缺点：空间扩充不便；插入和删除须大量移动数据。缺点：空间扩充不便；插入和删除须大量移动数据。 二叉链表：二叉链表：结点组成：结点组成：lchild data rchild ABCDEFG AB C D E F G其中：其中：data为数据域；为数据域； lchild为左指针域，放左子树的地址；为左指针域，放左子树的地址； rchild为右指针域，放右子树的地址；为右指针域，放右子树的地址；BT：名字，根，入口：名字，

25、根，入口(2)(2) 链式存储结构链式存储结构 二叉链表的定义：二叉链表的定义：typedef struct node datatype data; struct node *lchild, *rchild;BT;三叉链表：三叉链表：三叉链表的定义：三叉链表的定义： typedef struct node datatype data; struct node *lchild, *rchild, *parent;TT;lchild data parent rchildABCDEFG A B C D E F G结点组成：结点组成：三叉链表的静态结构：三叉链表的静态结构：ABCDFErootdata

26、 parent leftChild rightChild012345 6.3 遍历二叉树遍历二叉树1.1.问题的提出问题的提出 顺着某一条搜索路径顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点二叉树中的结点，使得每个结点均被访问一次均被访问一次，而且而且仅被访问一次仅被访问一次。 访问的含义可以很广，如：输出结点的信息等。访问的含义可以很广，如：输出结点的信息等。 遍历是任何类型均有的操作。遍历是任何类型均有的操作。 对线性结构而言，只有一条搜索路径对线性结构而言，只有一条搜索路径( (因为每个结点均只有因为每个结点均只有一个后继一个后继) )，故不需要另加讨论。，故不需要另加讨论。

27、而二叉树是非线性结构，每个结点有两个后继，则存在如何而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。遍历即按什么样的搜索路径遍历的问题。 对二叉树而言，可以有三条搜索路径：对二叉树而言，可以有三条搜索路径： 1先上后下的按层次遍历；先上后下的按层次遍历； 2先左（子树）后右（子树）的遍历；先左（子树）后右（子树）的遍历； 3先右（子树）后左（子树）的遍历。先右（子树）后左（子树）的遍历。先先序（根）的遍历算法序（根）的遍历算法中中序（根）的遍历算法序（根）的遍历算法后后序（根）的遍历算法序（根）的遍历算法2. 先左后右遍历二叉树的算法先左后右遍历二叉树的

28、算法(1) 先序（根）遍历先序（根）遍历 （DLR）先序遍历也称为先根遍历。其递归过程为：先序遍历也称为先根遍历。其递归过程为：若二叉树为空，则遍历结束，返回。若二叉树为空，则遍历结束，返回。否则：否则： （1）访问根结点；）访问根结点； （2）先序遍历根结点的左子树；）先序遍历根结点的左子树； （3）先序遍历根结点的右子树。）先序遍历根结点的右子树。3. 遍历二叉树的递归算法遍历二叉树的递归算法void Preorder(BT *T) / 先序遍历先序遍历 T 所指向的二叉树所指向的二叉树 if (T= =NULL) return; / 本函数调用结束本函数调用结束 printf(T-dat

29、a); / 输出结点的数据域输出结点的数据域 Preorder(T-lchild); / 先序递归遍历左子树先序递归遍历左子树 Preorder(T-rchild); / 先序递归遍历右子树先序递归遍历右子树 / 本函数调用结束本函数调用结束typedef struct node datatype data; struct node *lchild, *rchild;BT;算法描述：算法描述：ADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D C 先序遍历先序遍历:void preorder(BT *T) if(T=NULL) return; pri

30、ntf(%dt,T-data); preorder(T-lchild); preorder(T-rchild); 主程序主程序Pre( T )返回返回返回返回pre(T R);返回返回返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D C(2) 中序（根）

31、遍历中序（根）遍历 （LDR）中序遍历也称为中根遍历。其递归过程为：中序遍历也称为中根遍历。其递归过程为：若二叉树为空，则遍历结束，返回。若二叉树为空，则遍历结束，返回。否则：否则： （1）中序遍历根结点的左子树；）中序遍历根结点的左子树； （2）访问根结点；）访问根结点； （3）中序遍历根结点的右子树。）中序遍历根结点的右子树。算法描述：算法描述：typedef struct node datatype data; struct node *lchild, *rchild;BT;void Inorder(BT *T) / 中序遍历中序遍历 T 所指向的二叉树所指向的二叉树 if (T = =

32、NULL) return; / 本函数调用结束本函数调用结束 Inorder(T-lchild); / 中序递归遍历左子树中序递归遍历左子树 printf(T-data); / 输出结点的数据域输出结点的数据域 Inorder(T-rchild); / 中序递归遍历右子树中序递归遍历右子树 / 本函数调用结束本函数调用结束 ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A C 中序遍历中序遍历:(3) 后序（根）遍历后序（根）遍历 （LRD）后序遍历也称为后根遍历。其递归过程为：后序遍历也称为后根遍历。其递归过程为：若二叉树为空，则遍历结束，返回。

33、若二叉树为空，则遍历结束，返回。否则：否则： （1）后序遍历根结点的左子树；）后序遍历根结点的左子树； （2）后序遍历根结点的右子树。）后序遍历根结点的右子树。 （3）访问根结点；）访问根结点；算法描述：算法描述：typedef struct node datatype data; struct node *lchild, *rchild;BT;void Postorder(BT *T) / 后序遍历后序遍历 T 所指向的二叉树所指向的二叉树 if (T = =NULL) return; / 本函数调用结束本函数调用结束 Postorder(T-lchild); / 后序递归遍历左子树后序递归

34、遍历左子树 Postorder(T-rchild); / 后序递归遍历右子树后序递归遍历右子树 printf(T-data); / 输出结点的数据域输出结点的数据域 / 本函数调用结束本函数调用结束ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列： D B C A 后序遍历后序遍历:B（1 1）先序遍历的非递归算法）先序遍历的非递归算法* * 提高运算效率提高运算效率基于栈先序遍历的非递归算法：基于栈先序遍历的非递归算法：引入栈保存每个结点的右指针引入栈保存每个结点的右指针算法：算法：1 1）访问结点。）访问结点。2 2）结点的右指针入栈。）结点的右指针入栈。

35、3 3）若结点的左指针不空，遍历左子树。）若结点的左指针不空，遍历左子树。4 4）右指针出栈。）右指针出栈。5 5）若结点的右指针不空，遍历右子树。）若结点的右指针不空，遍历右子树。4. 遍历二叉树的非递归算法遍历二叉树的非递归算法（2 2）中序遍历的非递归算法）中序遍历的非递归算法基于栈中序遍历的非递归算法：基于栈中序遍历的非递归算法： 引入栈保存每个结点及右指针，由于知道结点的指针便引入栈保存每个结点及右指针，由于知道结点的指针便可知结点和其右指针，故只须结点的指针入栈。可知结点和其右指针，故只须结点的指针入栈。算法：算法：1 1）结点右指针入栈。）结点右指针入栈。2 2）若结点的左指针不

36、空，遍历左子树。）若结点的左指针不空，遍历左子树。3 3）指针出栈。）指针出栈。4 4）访问结点，若结点的右指针不空，遍历右子树。）访问结点，若结点的右指针不空，遍历右子树。算法实现：算法实现：void inorderse(BT *bt) int i=0; /栈的初始化栈的初始化 BT *p, *sM; /保存每个结点的指针的栈保存每个结点的指针的栈 p=bt; do while ( p!=NULL ) si+=p; /结点的指针入栈结点的指针入栈 p=p-lchild; /进入左子树进入左子树 /左子树为空，退出左子树为空，退出 if ( i0 ) /如果栈不空如果栈不空 p=s-i; /结

37、点的指针结点的指针出栈出栈 printf(“%dt”,p-data); /访问出栈的结点访问出栈的结点 p=p-rchild; while(i0|p!=NULL); /右子树为空同时栈右子树为空同时栈空，结束循环空，结束循环非递归算法栈操作图非递归算法栈操作图ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)P=nullABCDEFGiP-AP-B访问：访问：C(4)pABCDEFGiP-A访问：访问：C B(5)ABCDEFGiP-AP-D访问：访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：访问：C Bp(7)ABCDE

38、FGiP-AP-D访问：访问：C B Ep(8)ABCDEFGiP-AP-DP-G访问：访问：C B EP=NULL(9)ABCDEFGiP-A访问：访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：访问：C B E Gp(10)ABCDEFGiP-A访问：访问：C B E G D Fp=NULL(13)ABCDEFGi访问：访问：C B E G D F Ap(14)i访问：访问：C B E G D F Ap=NULLABCDEFG(15)5. 层次遍历二叉树的算法层次遍历二叉树的算法 按照自上而下（从根结点

39、开始），从左到右的顺序逐层访问按照自上而下（从根结点开始），从左到右的顺序逐层访问二叉树上的所有结点，称为按层次遍历。二叉树上的所有结点，称为按层次遍历。 按层次遍历时，当一层结点访问完后，接着访问下一层的结按层次遍历时，当一层结点访问完后，接着访问下一层的结点，先遇到的结点先访问，这与点，先遇到的结点先访问，这与队列队列的操作原则是一致的。在层的操作原则是一致的。在层次遍历时，可设置一个数组来模拟队列，用于保存次遍历时，可设置一个数组来模拟队列，用于保存被访问结点被访问结点的的子结点的地址子结点的地址。 遍历从二叉树的根结点开始，首先将遍历从二叉树的根结点开始，首先将根结点指针入队列根结点指

40、针入队列，然，然后从队头取出一个元素，每取一个元素，执行下面两个操作：后从队头取出一个元素，每取一个元素，执行下面两个操作：（1）访问该元素所指结点；）访问该元素所指结点；（2）若该元素所指结点的）若该元素所指结点的左、右孩子结点非空左、右孩子结点非空，则将该元素所，则将该元素所 指结点的左孩子指针和右孩子指针依次入队。指结点的左孩子指针和右孩子指针依次入队。 此过程不断进行，直到队空为止。此过程不断进行，直到队空为止。 在层次遍历算法中，以二叉链表方式存储，在层次遍历算法中，以二叉链表方式存储，lchild和和rchild分别是被访问结点的左、右指针。一维数组分别是被访问结点的左、右指针。一

41、维数组 qMAXLEN 用用以实现队列。以实现队列。算法描述：算法描述： void Levelorder(BT *T) / 按层次遍历二叉树按层次遍历二叉树BT, T 为指向根结点的指针为指向根结点的指针 int i,j; BT *qMAXLEN,*p; / q为指针数组用以模拟队列为指针数组用以模拟队列,每个元素均为指向每个元素均为指向BT类型的类型的 指针指针, 用来存放结点地址用来存放结点地址 p=T; if (p!=NULL) / 若二叉树非空，则根结点地址入队若二叉树非空，则根结点地址入队 i=1;qi=p;j=2; / i 指向对头，指向对头，j 指向对尾指向对尾 while (i

42、!=j) / 当队列不为空时执行循环当队列不为空时执行循环 p=qi; printf(p-data); / 访问队首结点的数据域访问队首结点的数据域 if( p-lchild!=NULL) qj=p-lchild; j+; / 将出队结点的左孩子的地址入队将出队结点的左孩子的地址入队 if(p-rchild!=NULL) qj=p-rchild; j+; / 将出队结点的右孩子的地址入队将出队结点的右孩子的地址入队 i+; 层次遍历层次遍历:ABCDEHIFGK层次遍历的序列层次遍历的序列: A B C D E F G H I K例：例： 有二叉树如图所示，求它的先根遍历、中根遍历、后根遍历和

43、有二叉树如图所示，求它的先根遍历、中根遍历、后根遍历和层次遍历的输出序列。层次遍历的输出序列。ABCIKFEDHG先根遍历的序列：先根遍历的序列： A B D G E H C F I K中根遍历的序列：中根遍历的序列： D G B H E A F K I C后根遍历的序列：后根遍历的序列： G D H E B K I F C A层次遍历的序列：层次遍历的序列： A B C D E F G H I K例：设表达式例：设表达式AB*（C+D）+E/（F+G）的二叉树表示如图所示。）的二叉树表示如图所示。试写出它的先根遍历、中根遍历和后根遍历输出序列。试写出它的先根遍历、中根遍历和后根遍历输出序列。

44、A*/EF+BDC-+G先根遍历结果（即前缀表达式）：先根遍历结果（即前缀表达式）： + A * B + C D / E + F G中根遍历结果：中根遍历结果： A B * C + D + E / F + G后根遍历结果（即后缀表达式）：后根遍历结果（即后缀表达式）： A B C D + * E F G + / +6.4 6.4 恢复二叉树恢复二叉树 根据已知的先根序列、中根序列、后根序列得到一棵二根据已知的先根序列、中根序列、后根序列得到一棵二叉树称为叉树称为恢复二叉树恢复二叉树。问题的由来：问题的由来： 在数据量很大的结构中，如在绘图软件中，如何存储一在数据量很大的结构中，如在绘图软件中，

45、如何存储一个用个用树树表示的图形结构？处理方法：表示的图形结构？处理方法： 对于链表结构的图形结构：对于链表结构的图形结构： （1 1）把每个结点去掉指针项，把每个结点去掉指针项，将结点的数据按将结点的数据按中序中序存存储于数组中得到中序结点表。储于数组中得到中序结点表。 （2 2）把每个结点去掉指针项，把每个结点去掉指针项，将结点的数据按将结点的数据按先序先序或或后序后序存储于数组中得到序表。存储于数组中得到序表。 图形结构调入内存时要恢复二叉树。有二种方法：图形结构调入内存时要恢复二叉树。有二种方法： （1 1）根据根据中序中序数组、数组、先序先序数组恢复二叉树。数组恢复二叉树。 （2 2

46、）根据根据中序中序数组、数组、后序后序数组数组恢复二叉树。恢复二叉树。1. 1. 由先根、中根恢复二叉树由先根、中根恢复二叉树步骤：步骤：（1 1）根据根据先根序列的先根序列的第一个元素第一个元素确定根结点确定根结点； 在在中根序列中根序列中找到该中找到该根结点根结点， 确定该根结点的确定该根结点的左、右左、右 子树的中根序列子树的中根序列； 再在先根序列中确定再在先根序列中确定此左、右子树的先根序列此左、右子树的先根序列；（2 2）根据根据左、右子树的先根序列左、右子树的先根序列分别找出左子树和右子树分别找出左子树和右子树 的的根结点根结点，并把左、右子树的根结点连到父结点上去；，并把左、右

47、子树的根结点连到父结点上去；（3 3）再对左再对左、右子树按此方法找出根结点和左、右子树；右子树按此方法找出根结点和左、右子树； 如此递归下去，当取尽先根序列中的结点时，便恢复了如此递归下去，当取尽先根序列中的结点时，便恢复了一棵二叉树。一棵二叉树。例：由下列先根序列和中根序列恢复二叉树。例：由下列先根序列和中根序列恢复二叉树。 先根序列：先根序列：A C B R S E D F M L KA C B R S E D F M L K 中根序列：中根序列：R B S C E A F D L K MR B S C E A F D L K M例：例：前序：前序：A C B R S E D F M L

48、 KA C B R S E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K M前序：前序： A A C B R S E D F M L KC B R S E D F M L K中序：中序： R B S C ER B S C E A A F D L K MF D L K MA左子树左子树右子树右子树左子树左子树右子树右子树例：例：前序：前序：A C B R S E D F M L KA C B R S E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K M前序：前序：

49、A A C C B R S E D F M L KB R S E D F M L K中序：中序： R B SR B S C E A F D L K MC E A F D L K MA左子树左子树右子树右子树左子树左子树右子树右子树CD例：例：前序：前序：A C B R S E D F M L KA C B R S E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K M前序：前序： A C B R S E D F M L KA C B R S E D F M L K中序：中序： R B S C E A F D L K MR B S

50、C E A F D L K MA左左子子树树左左子子树树右右子子树树右右子子树树CD左左子子树树右右子子树树左左子子树树右右子子树树例：例：前序：前序：A C B R S E D F M L KA C B R S E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K MA左左子子树树左左子子树树右右子子树树右右子子树树CD左左子子树树右右子子树树左左子子树树右右子子树树BEFM前序：前序： A C B R S E D F M L KA C B R S E D F M L K中序：中序： R B S C E A F D L K MR

51、B S C E A F D L K M例：例：前序：前序：A C B R S E D F M L KA C B R S E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K MA左左子子树树左左子子树树右右子子树树CDBEFM左左子子树树右右子子树树左左子子树树前序：前序： A C B R S E D F M L KA C B R S E D F M L K中序：中序： R B S C E A F D L K MR B S C E A F D L K M例：例：前序：前序：A C B R S E D F M L KA C B R S

52、 E D F M L K中序：中序：R B S C E A F D L K MR B S C E A F D L K MA左左子子树树左左子子树树右右子子树树CDBEFMRS左左子子树树右右子子树树左左子子树树LK前序：前序： A A C C B R S E B R S E D D F M L F M L K K中序：中序： R B S C E A F D L K MR B S C E A F D L K M2.2.由后根、中根恢复二叉树由后根、中根恢复二叉树步骤：步骤：（1 1）根据根据后根序列的后根序列的最后一个元素最后一个元素确定根结点确定根结点； 在在中根序列中根序列中找到该中找到该根

53、结点根结点， 确定该根结点的确定该根结点的左、右左、右 子树的中根序列子树的中根序列； 再在后根序列中确定再在后根序列中确定此左、右子树的后根序列此左、右子树的后根序列；（2 2）根据根据左、右子树的后根序列左、右子树的后根序列分别找出左子树和右子树分别找出左子树和右子树 的根结点，并把左、右子树的根结点连到父结点上去；的根结点，并把左、右子树的根结点连到父结点上去；（3 3）再对左再对左、右子树按此方法找出根结点和左、右子树；右子树按此方法找出根结点和左、右子树； 如此递归下去，当取尽后根序列中的结点时，便恢复了如此递归下去，当取尽后根序列中的结点时，便恢复了一棵二叉树。一棵二叉树。例：由下

54、列中根序列和后根序列恢复二叉树。例：由下列中根序列和后根序列恢复二叉树。 后根序列：后根序列：C E D B H G J I F AC E D B H G J I F A 中根序列：中根序列：C B E D A G H F J IC B E D A G H F J I例：例：后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J IA左子树左子树右子树右子树左子树左子树右子树右子树后序：后序： C E D B H G J I F AC E D B H G J I F A中序

55、：中序： C B E D A G H F J IC B E D A G H F J I例：例：后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J IA左子树左子树右子树右子树左子树左子树右子树右子树BF后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J I例：例：后序：后序： C E D B H G J I F AC E D B H G J I

56、F A中序：中序： C B E D A G H F J IC B E D A G H F J IABF左左子子树树左左子子树树右右子子树树右右子子树树左左子子树树右右子子树树左左子子树树右右子子树树后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J I例：例：后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J IABF左左子子树树左左子子树树右右

57、子子树树右右子子树树左左子子树树右右子子树树左左子子树树右右子子树树CDGI后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J I例：例：后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序： C B E D A G H F J IC B E D A G H F J IABF左左子子树树左左子子树树右右子子树树CDGIEHJ后序：后序： C E D B H G J I F AC E D B H G J I F A中序：中序

58、： C B E D A G H F J IC B E D A G H F J I6.5 6.5 线索二叉树线索二叉树 对二叉树的遍历可得到三种序列：先序、中序、后序序列。对二叉树的遍历可得到三种序列：先序、中序、后序序列。均为线性序列。结点至多有一个直接前驱和直接后继。均为线性序列。结点至多有一个直接前驱和直接后继。 在二叉链表中找孩子结点容易，但找这样的直接前驱和直接后在二叉链表中找孩子结点容易，但找这样的直接前驱和直接后继不行。继不行。 利用二叉链表中的空指针域，存储直接前驱和直接后继的指针利用二叉链表中的空指针域，存储直接前驱和直接后继的指针（为区别起见此时指针称为线索）。（为区别起见此

59、时指针称为线索）。 带有线索的二叉树称为带有线索的二叉树称为线索二叉树线索二叉树。 对二叉树以某种次序遍历改变空指针域为线索，使其变为线索对二叉树以某种次序遍历改变空指针域为线索，使其变为线索二叉树的过程称为二叉树的过程称为线索化线索化。1. 线索二叉树线索二叉树 A B A 两个结点的二叉链表两个结点的二叉链表 单结点的二叉链表图单结点的二叉链表图 在二叉链表存储的二叉树中：在二叉链表存储的二叉树中： 单个结点的二叉树有单个结点的二叉树有 2 个空指针域，如图所示。个空指针域，如图所示。 两个结点的二叉树有两个结点的二叉树有 3 个空指针域，如图所示。个空指针域，如图所示。可以证明：可以证明

60、： 一个具有一个具有n个结点的二叉树，若采用二叉链表存储结构，个结点的二叉树，若采用二叉链表存储结构，在总共在总共2n个指针域中，只有个指针域中，只有n-1个指针域用来存储结点子树的个指针域用来存储结点子树的地址，另外地址，另外n+1个都是空指针域。个都是空指针域。证明：度为证明：度为 0 的结点数为的结点数为 n0 每个结点有每个结点有 2 个空链域。个空链域。 度为度为 1 的结点数为的结点数为 n1 每个结点有每个结点有 1 个空链域。个空链域。 度为度为 2 的结点数为的结点数为 n2 每个结点没有空链域。每个结点没有空链域。 所以空链域数所以空链域数=2n0+ n1 把性质把性质5（