数据结构 树.ppt

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

2、的性质 6.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(

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

5、层上至多有2i-1个结点 性质2 深度为k的二叉树至多有2k-1个结点 性质3 任何一个二叉树中度为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。 由于二叉树中除根结点以外，每个结点都有惟一的一个分支指向它，因此二叉树中：总的分支数

6、=总结点数-1。 由上述三个等式可得：n1+2n2=n0+n1+n2-1 即：n0=n2+1,满二叉树和完全二叉树,高度为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

7、 h 即 h = log2n+1 或log2n+1 证毕。,二叉树的性质(续),性质5 完全二叉树中的某结点编号为i，则 1) 若有左孩子，则左孩编号为2i 2）若有右孩子，则右孩子结点编号为2i+1 3）若有双亲，则双亲结点编号为i/2,6.2.3 二叉树的顺序存储,二叉树的顺序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系. 完全二叉树的顺序存储,#define MAX_TREE_SIZE 100 typedef TelemType SqBiTreeMAX_TREE_SIZE; SqBiTree bt;,二叉树的顺序存储,非完全二叉树的顺序存储,非完全二叉树不适合进行顺序

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

9、 二叉树的遍历,先左后右：DLR，LDR，LRD,D,L,R,根结点,根的 左子树,根的 右子树,先右后左：DRL，RDL，RLD,先序遍历,DLR：访问根结点、先序遍历左子树、先序遍历右子树,D,L,R,1,2,3,先序遍历,DLR：访问根结点、先序遍历左子树、先序遍历右子树,若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；,若二叉树为空，结束 基本项（也叫终止项） 若二叉树非空 递归项 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；,void preorder (BiTNode *root) /先序遍历root指向根的二叉树 if (ro

10、ot!=NULL) coutdata；/访问根结点 preorder(root-Lchild); /先序遍历根的左子树 preorder(root-Rchild); /先序遍历根的右子树 /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 pre

11、order (BiTNode *root) if (root!=NULL) coutdata；/访问根结点 preorder(root-Lchild); /先序遍历根的左子树 preorder(root-Rchild); /先序遍历根的右子树 /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); /先序遍历根的右

12、子树 /if /preorder,B,A,C,E,D,G,F,root: B,root: A,先序遍历序列：,A,B,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!=

13、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,root: NULL,D,void preorder (BiTNode *root) if (root!=NULL) coutdata；/访问根结点 preorder(root-Lchild); /先序遍历根的左子树 preorder(root-Rchild); /先序遍历根的

14、右子树 /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,先序遍历序列：,A,B,root: D,D,root: NULL,D,void preord

15、er (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,E,E,void preorder (BiTNode *root) if (root!=NULL) coutdata；/访问根结点 preorder(root-Lchild); /先序遍历根的左子树 preorder(r

16、oot-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(root-Rchild); /先序遍历根的右子树 /if /preorder,B,A,C,E,D,G,F,root,root: B,root: A,先序遍历序列：,A,B,D,root: E,E,

17、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 preorder (BiTNode *root) if (root!=NULL) coutdata；/访问根结点 preorder(root-Lchil

18、d); /先序遍历根的左子树 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); /先序遍历根的右子树 /if /preorder,B,A,C,E,D,G,F,root,root: A,先序遍历序列：,A,B

19、,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) coutdata；/访问根结点 preorder(root-Lchild); /先序遍历根的

20、左子树 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,F,root,root: A,先序遍历序列：,A

21、,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；/访问根结点 preord

22、er(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,ro

23、ot: A,先序遍历序列：,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)

24、if (root!=NULL) coutdata；/访问根结点 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）中序遍历左子树

25、； （2）访问根结点； （3）中序遍历右子树；,若二叉树为空，结束 基本项（也叫终止项） 若二叉树非空 递归项 （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) ino

26、rder(root-Lchild); /中序遍历根的左子树 coutdata；/访问根结点 inorder(root-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:

27、A,root: 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: A,root: B,root: D,void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍历根的左子树 coutdata；/访问根结点 inord

28、er(root-Rchild); /中序遍历根的右子树 /if /inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root: A,root: B,root: 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

29、 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,root: NULL,void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍历根的左子树 coutdata；/访问根结点 inorde

30、r(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); /中序遍历根的右子树 /if /inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root: A,root: B,D,B,void inorder (BiTNod

31、e *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,void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild); /中序遍历根的右子

32、树 /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；/访问根结点 inorder(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 ino

33、rder (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,G,void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍历根的左子树 coutdata；/访问根结点 inorder(r

34、oot-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); /中序遍历根的右子树 /if /inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root: A,root: B,D,B,G,E,void inorder

35、(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-Lchild); /中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild); /中序遍历根的右子树 /

36、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,root: C,root: NULL,void inorder (BiTNode *root) if

37、 (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(root-Rchild); /中序遍历根的右子树 /if /inor

38、der,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 inorder (BiTNo

39、de *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)

40、; /中序遍历根的右子树 /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)

41、 if (root!=NULL) inorder(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,后序遍历序列:BDFGEC

42、A,void inorder (BiTNode *root) if (root!=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

43、 (BiTNode *root) if (root!=NULL) postorder(root-Lchild); /后序遍历根的左子树 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

44、,root: B,root: E,E,中序遍历序列：,D,B,G,void InOrder (BiTNode *root) InitStack(S); 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

45、,B,A,C,E,D,G,F,root,root: A,root: B,root: E,E,中序遍历序列：,D,B,G,void InOrder (BiTNode *root) InitStack(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,先序遍历序

46、列: + 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 = e / f,t5 = t3 t4,层序遍历,先根，后子树；先左子树，后右子树,队列,队头,层序遍历序列:,层序遍历,队列,队头,A,层序遍历序列:,先根，后子树；先左子树，后右子树,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,

47、层序遍历序列: 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,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,层序遍历序列: ABC,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,D,E,层序遍历序列: ABC,层序遍历,先根，后子树；

48、先左子树，后右子树,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,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,F,G,层序遍历序列: ABCDE,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,G,层序遍历序列: ABCDEF,层序遍历,先根，后子树；先左子树，后右子树,E

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

50、ild指向后继结点,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,中序序列：DBGEACF,NULL,B,A,C,E,D,G,F,root,中序线索二叉树,NULL,中序序列：DBGEACF,NULL,在中序线索化二叉树上查找给定结点的前驱和后继结点,中序线索二叉树,在中序线索二叉

51、树上，查找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,中序线索二叉树,中序线索二叉树上找指定结点的后继： BiThrTree inordernext(BiThrTree p) if （p-rtag=1） return(p-Rchild); else q

52、=p-Rchild; while (q-ltag=0) q=q-Lchild; return(q); ,typedef struct BiThrNode ElemType data; struct BiThrNode *Lchild,*Rchild; PointerTag Ltag,Rtag; *BiThrTree;,建立中序线索二叉树,线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程就是在遍历过程中修改空指针的过程。,void InOrderThreading(BiThrTree /InOrderThreading,Lchi

53、ld,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); /右子树线索化 /InThreading,B,A,C,E,D,G,F,root,后序线索二叉树,后序序列：IDGHEBFCA,

54、NULL,在后序线索化二叉树上查找给定结点的前驱和后继结点,H,I,后序线索二叉树,在后序线索二叉树上，查找p所指结点的后继分为两种情况：,(1) 若p所指结点是整棵二叉树的根结点，则无后继结点；,(3) 若p-Rtag=0：/P所指结点有右子树 若p所指结点是其父结点f的右孩子，则其父结点f是其后继； 若p所指结点是其父结点f的左孩子： 若p所指结点没有右兄弟，则其父结点f是其后继； 若P有右兄弟，则其后继结点是其父的右子树上后序遍历得到的第一个结点。,(2) 若p-Rtag=1，则p-Rchild指向其后继结点；,后序线索二叉树,后序线索二叉树上找指定结点的后继 BiThrTree post