《数据结构树》PPT课件.ppt

《《数据结构树》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构树》PPT课件.ppt（168页珍藏版）》请在三一办公上搜索。

1、引言,在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。而现实中的许多事物的关系并非如此简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。所谓非线性结构，是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树结构和图结构是非常重要的非线性结构。,第六章 树和二叉树,本章内容6.1 树的定义和基本术语6.2 二叉树6.2.1 二叉树的定义及基本运算6.2.2 二叉树的性质6.

2、2.3 二叉树的存储结构6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树6.3.2 线索二叉树6.4 树和森林6.4.1 树的存储结构6.4.2 森林与二叉树的转换及遍历6.6 赫夫曼树及应用6.6.1 赫夫曼树（最优二叉树）6.6.2 赫夫曼编码,6.1 树,树是n个结点的有限集合(可以是空集)，在任一棵非空树中：（1）有且仅有一个称为根的结点。（2）其余结点可分为互不相交的子集，而且这些子集本身又是一棵树，称为根的子树。,从逻辑结构看：1）树中只有树根没有父结点；2）除根外，其余结点都有且仅一个父结点；3）树中的结点，可以有零个或多个孩子结点；4)没有孩子的结点称为叶子结点，或终端结点

3、；5）除根外的其他结点，都存在唯一一条从根到该结点的路径；,树的基本术语,树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；父结点：B 是A的孩子，则A是B的父亲；兄弟结点：同一双亲的孩子结点；堂兄弟结点：其父结点在同一层上的结点；祖先结点:从根到该结点所经分支上的所有结点；子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；结点的度:结点的孩子数目,树的基本运算,找树的根结点求树的高度找指定结点的父结点找指定结点的孩子结点在树中插入、删除一个结点遍历树.,树的表示,(a),(A(B(E(k,L),F),C(G),D(H(M),I(),J(),(b

4、),6.2 二叉树,二叉树的定义：二叉树要么为空，要么由根结点、左子树和右子树组成。左、右子树本身也是二叉树。,注意：二叉树的子树有严格的左右之分，而树没有。,二叉树的子树要区分左子树和右子树，即使只有一棵子树也要进行区分。这是二叉树与树的最主要的差别。下面列出了二叉树的5种基本形态，(c)和（d）是不同的两棵二叉树。,(a)空二叉树,A,A,B,A,B,A,C,B,(b)只有根的二叉树,(c)根和左子树,(d)根和右子树,(e)根和左右子树,二叉树的5种基本形式,6.2.2 二叉树的性质,性质1 在二叉树的第i层上至多有2i-1个结点性质2 深度为k的二叉树至多有2k-1个结点性质3任何一个

5、二叉树中度为2的结点数目(n2)比度为0的结点数目(n0)少1，即n2 n0-1。,6.2.2 二叉树的性质,性质3 任何一个二叉树中度为2的结点数目(n2)比度为0的结点数目(n0)少1，即n2 n0-1。证明：设二叉树上叶结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数=n0+n1+n2。在一棵二叉树中，所有结点的分支数(即度数)应等于单分支结点数加上双分支结点数的2倍，即总的分支数=n1+2n2。由于二叉树中除根结点以外，每个结点都有惟一的一个分支指向它，因此二叉树中：总的分支数=总结点数-1。由上述三个等式可得：n1+2n2=n0+n1+n2-1 即：n0=n2+1,满

6、二叉树和完全二叉树,高度为3的满二叉树,高度为3的一个完全二叉树,高度为3的一个完全二叉树,完全二叉树,高度为3的完全二叉树,满二叉树和完全二叉树,高度为3的满二叉树,高度为3的一个完全二叉树,1,2,3,4,5,6,7,1,2,3,4,5,二叉树的性质(续),性质4一个有n个结点的完全二叉树的高度Hlog(n)+1。,证明：设具有n个结点的完全二叉树的深度为h，则根据性质3：深度为h的二叉树至多有2h-1个结点，因此，n=2h-1综上，2h-1=n 2h，或 h-1=log2n h即 h=log2n+1 或log2n+1 证毕。,二叉树的性质(续),性质5完全二叉树中的某结点编号为i，则1)

7、若有左孩子，则左孩编号为2i2）若有右孩子，则右孩子结点编号为2i+13）若有双亲，则双亲结点编号为i/2,6.2.3 二叉树的顺序存储,二叉树的顺序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系.完全二叉树的顺序存储,#define MAX_TREE_SIZE 100typedef TelemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;,二叉树的顺序存储,非完全二叉树的顺序存储,非完全二叉树不适合进行顺序存储,二叉树的链式存储,一般用二叉链表存储二叉树(每个结点有两个指针域),typedef struct BiTNode TElemType

8、 data;struct BiTNode*Lchild,*Rchild;BiTNode,*BiTree;,二叉树的链式存储,三叉链表存储(每个节点有三个指针域),Lchild,data,Rchild,Parent,6.3 遍历二叉树和线索二叉树,任何一个非空的二叉树都由三部分构成,D,L,R,根结点,根的左子树,根的右子树,树的遍历是访问树中每个结点仅一次的过程。遍历可以被认为是把所有的结点放在一条线上，或者将一棵树进行线性化的处理。,6.3.1 二叉树的遍历,先左后右：DLR，LDR，LRD,D,L,R,根结点,根的左子树,根的右子树,先右后左：DRL，RDL，RLD,先序遍历,DLR：访问

9、根结点、先序遍历左子树、先序遍历右子树,D,L,R,1,2,3,先序遍历,DLR：访问根结点、先序遍历左子树、先序遍历右子树,若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；,若二叉树为空，结束 基本项（也叫终止项）若二叉树非空 递归项（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；,void preorder(BiTNode*root)/先序遍历root指向根的二叉树 if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右

10、子树/if/preorder,先序遍历,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,先序遍历序列：,root:A,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild)

11、;/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,先序遍历序列：,A,root:A,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root:B,root:A,先序遍历序列：,A,B,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder

12、(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,

13、A,B,root:D,D,root:NULL,D,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的

14、左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,root:NULL,D,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:

15、D,D,E,E,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,root:E,E,G,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(ro

16、ot-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,root:E,E,G,root:G,E,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,root:E,E,G,B,void

17、 preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,E,G,A,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍

18、历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,C,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,void preorder(BiTNode*root)if(root!=NULL)coutda

19、ta；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,root:NULL,C,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,

20、F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,F,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,root:F,F,C,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 p

21、reorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,F,A,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序

22、列：,A,B,D,E,G,C,F,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,先序遍历序列：,A,B,D,E,G,C,F,先序遍历过程,B,A,C,E,D,G,F,先序遍历序列：,A,B,D,E,G,C,F,A,B,D,E,G,C,F,void preorder(BiTNode*root)if(root!=NULL)coutdata；

23、/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,root:A,root:B,root:E,root:G,栈在先序遍历中的作用,B,A,C,E,D,G,F,root,先序遍历序列：,A,B,D,E,G,栈用于保存当前结点的祖先结点,中序遍历,LDR：中序遍历左子树、访问根结点、中序遍历右子树,D,L,R,2,1,3,中序遍历,LDR：中序遍历左子树、访问根结点、中序遍历右子树,若二叉树非空（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；,若二叉树为空，结束 基本

24、项（也叫终止项）若二叉树非空 递归项（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；,void inorder(BiTNode*root)/中序遍历root指向根的二叉树 if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,中序遍历,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(r

25、oot-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild)

26、;/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,ro

27、ot:NULL,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,D,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中

28、序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,D,root:NULL,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,D,void inorder(BiTNode*root)if(root!=NULL

29、)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:

30、A,root:B,D,B,root:E,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,root:G,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 in

31、order(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,root:G,root:NULL,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,root:G,

32、G,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,G,E,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中

33、序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,G,E,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lch

34、ild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A

35、,root:C,root:NULL,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(ro

36、ot-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,root:F,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,root:F,root:NULL,void i

37、norder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,root:F,F,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍

38、历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,F,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,C,F,void inorder(BiTNode*root)if(root!=NULL)inorder(

39、root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,D,B,G,E,A,C,F,B,A,C,E,D,G,F,root,root:A,root:B,root:E,root:G,栈在中序遍历中的作用,中序遍历序列：,D,B,G,栈用于保存当前结点的祖先结点,后序遍历,LRD：后序遍历左子树、后序遍历右子树、访问根结点,D,L,R,3,1,2,后序遍历序列:BDFGECA,void inorder(BiTNode*root)if(ro

40、ot!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,void preorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点 preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preorder,void postorder(BiTNode*root)if(root!=NULL)postorder(root-Lchild);

41、/后序遍历根的左子树 postorder(root-Rchild);/后序遍历根的右子树 coutdata；/访问根结点/if/postorder,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,root:A,root:B,root:E,E,中序遍历序列：,D,B,G,void InOrder(BiTNode*root)InitStack(S);

42、Push(S,root);/根指针进栈 while(!StackEmpty(S)while(GetTop(S,p)/向右/if/while/InOrder,void inorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,root:A,root:B,root:E,E,中序遍历序列：,D,B,G,void InOrder(BiTNode*root)InitStack

43、(S);p=root;/根指针进栈 while(p|!StackEmpty(S)if(p)Push(S,p);p=p-Lchild;else/根指针退栈，访问根结点，遍历右子树 Pop(S,p);cout data;p=p-Rchild;/if-else/while/InOrder,用二叉树表示表达式,a+b*(c d)e/f,先序遍历序列:+a*b c d/e f,中序遍历序列:a+b*c d e/f,后序遍历序列:a b c d*+e f/,表达式的前缀、中缀和后缀表示,用栈对后缀表达式求值,表达式的后缀表示:a b c d*+e f/,t1=c d,t2=b*t1,t3=a+t2,t4=

44、e/f,t5=t3 t4,层序遍历,先根，后子树；先左子树，后右子树,队列,队头,层序遍历序列:,层序遍历,队列,队头,A,层序遍历序列:,先根，后子树；先左子树，后右子树,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,层序遍历序列:A,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,B,C,层序遍历序列:A,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,C,层序遍历序列:AB,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,C,层序遍历序列:AB

45、,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,层序遍历序列:ABC,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,D,E,层序遍历序列:ABC,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,E,层序遍历序列:ABCD,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,E,层序遍历序列:ABCD,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,层序遍历序列:ABCDE,层序遍历,先根，后子树；先左子树，后右子树,

46、E,G,F,C,D,A,B,队列,队头,F,G,层序遍历序列:ABCDE,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,G,层序遍历序列:ABCDEF,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,G,层序遍历序列:ABCDEF,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,层序遍历序列:ABCDEFG,利用队列实现二叉树的层序遍历：构造一个空队列；树根结点入队列；while（队列不空）队头元素出队列；访问结点；刚出队的结点的左孩子、右孩子结点先后入队列；,6.3.2 线索二叉树,Ltag=,

47、Lchild,data,Rchild,Lchild,data,Rchild,Rtag,Ltag,0 Lchild指向左子树根结点,1 Lchild指向前驱结点,Rtag=,0 Rchild指向右子树根结点,1 Rchild指向后继结点,typedef enum PointerTag Link=0,Thread=1;typedef struct BiThrNode ElemType data;struct BiThrNode*Lchild,*Rchild;PointerTag Ltag,Rtag;*BiThrTree;,B,A,C,E,D,G,F,root,中序线索二叉树,NULL,中序序列：D

48、BGEACF,NULL,B,A,C,E,D,G,F,root,中序线索二叉树,NULL,中序序列：DBGEACF,NULL,在中序线索化二叉树上查找给定结点的前驱和后继结点,中序线索二叉树,在中序线索二叉树上，查找p所指结点的后继分为两种情况：,(1)若p-Rtag=1，则p-Rchild指向其后继结点；,(2)若p-Rtag=0，则p所指结点的中序后继必为其右子树中序遍历得到的第一个结点，即从p所指结点的右子树根出发，沿左指针链向下找，直到找到一个没有左孩子的结点为止，这个结点称为p的右子树中“最左下”的结点。,B,A,C,E,D,G,F,root,中序线索二叉树,NULL,NULL,I,H

49、,中序线索二叉树,中序线索二叉树上找指定结点的后继：BiThrTree inordernext(BiThrTree p)if（p-rtag=1）return(p-Rchild);else q=p-Rchild;while(q-ltag=0)q=q-Lchild;return(q);,typedef struct BiThrNode ElemType data;struct BiThrNode*Lchild,*Rchild;PointerTag Ltag,Rtag;*BiThrTree;,建立中序线索二叉树,线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历

50、时才能得到，因此线索化的过程就是在遍历过程中修改空指针的过程。,void InOrderThreading(BiThrTree/InOrderThreading,Lchild,data,Rchild,Rtag,Ltag,void InThreading(BiThrTree p)if(p)InThreading(p-Lchild);/左子树线索化 if(!p-Lchild)/前驱线索 p-Ltag=Thread;p-Lchild=pre;if(!pre-Rchild)/后继线索 pre-Rtag=Thread;pre-Rchild=p;pre=p;InThreading(p-Rchild);/右