内容文本讲义d

1、第 2 页6.1 6.1 树的定义与基本术语树的定义与基本术语 树树(Tree)是是 n 个结点的有限集合，在任意一个结点的有限集合，在任意一棵非空树中：棵非空树中： （1）有且仅有一个称为根）有且仅有一个称为根(Root)的结点。的结点。 （2）其余结点可分为若干个互不相交的集合）其余结点可分为若干个互不相交的集合，且这些集合中的每一集合本身又是一棵树，且这些集合中的每一集合本身又是一棵树，称为根的子树称为根的子树(SubTree)。树是递归结构，树的定义是递归定义。树是递归结构，树的定义是递归定义。J JI IA AC CB BD DH HG GF FE E第 3 页6.1 6.1 树的定

2、义与基本术语树的定义与基本术语例：右面的图是例：右面的图是一棵树一棵树 T。 T = A T = A，B B，C C，D D，E E，F F，G G，H H，I I，J J A A是根，其余结点可以划分为是根，其余结点可以划分为3 3个互不相交的集合：个互不相交的集合： T1= B,E,F T2= C,G T3= D,H,I,J T1= B,E,F T2= C,G T3= D,H,I,J 这些集合中的每一集合本身又都是一棵树，它们是这些集合中的每一集合本身又都是一棵树，它们是根根 A A 的子树。的子树。 对于对于T1T1，B B是根，其余结点可以划分为两个互不相是根，其余结点可以划分为两个互

3、不相交的集合：交的集合： T11= E T12= F T11 T11= E T12= F T11，T12T12是是B B的子树。的子树。J JI IA AC CB BD DH HG GF FE E第 4 页6.1 6.1 树的定义与基本术语树的定义与基本术语 2）除根外，其余结点都有且仅一个前趋；）除根外，其余结点都有且仅一个前趋； 3）树的结点，可以有零个或多个后继；）树的结点，可以有零个或多个后继； 4）除根之外的其它结点，都存在唯一一条）除根之外的其它结点，都存在唯一一条从根到该结点的路径；从根到该结点的路径； 5）树是一种分支结构（除了一个称为根的）树是一种分支结构（除了一个称为根的结

4、点之外）每个元素都有且仅有一个直接前结点之外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。趋，有且仅有零个或多个直接后继。l从逻辑结构看从逻辑结构看:l 1）树中只有根）树中只有根结点没有前趋；结点没有前趋；J JI IA AC CB BD DH HG GF FE E第 5 页6.1 6.1 树的定义与基本术语树的定义与基本术语l树的应用树的应用家族树家族树血统树血统树( 二叉树二叉树 )第 6 页6.1 6.1 树的定义与基本术语树的定义与基本术语l树的应用树的应用l 常用的数据组织形式常用的数据组织形式计算机的文计算机的文件系统。件系统。l 不论是不论是DOSDOS文件系统

5、还是文件系统还是windowwindow文件文件系统，所有的文件都是用树的形式进行组织。系统，所有的文件都是用树的形式进行组织。文件夹文件夹1 1 文件夹文件夹n n 文件文件1 1 文件文件2 2文件夹文件夹2 1 2 1 文件夹文件夹22 22 文件文件21 21 文件文件2222C C第 7 页6.1 6.1 树的定义与基本术语树的定义与基本术语l树的应用树的应用lDNS Name Space.DNS Name Space.“.”.comeducnedubittshuapku cs ee ss中国教育和科研网教育和科研网北理校园网北理校园网第 8 页6.1 6.1 树的定义与基本术语树的

6、定义与基本术语l树的表示树的表示l 1）图示表示）图示表示l 2）二元组表示）二元组表示l 3）文氏图表示）文氏图表示l 4）广义表表示）广义表表示l 5）凹入表示法（类似书的目录）凹入表示法（类似书的目录）J JI IA AC CB BD DH HG GF FE E第 9 页6.1 6.1 树的定义与基本术语树的定义与基本术语D = A，B，C，D，E，F，G，H，I，J R = , , , , , , , , l树的表示树的表示l2）二元组表示）二元组表示J JI IA AC CB BD DH HG GF FE E第 10 页6.1 6.1 树的定义与基本术语树的定义与基本术语l树的表示树

7、的表示l3）文氏图表示）文氏图表示ABCDEFGHIJMKLABCDEFGHIJMKL第 11 页6.1 6.1 树的定义与基本术语树的定义与基本术语 假设树的根为假设树的根为rootroot，子树为，子树为T1,T2,TnT1,T2,Tn，与该树对应的广义表为与该树对应的广义表为L L，则：，则：L=(L=(原子原子( (子表子表1,1,子表子表2, , 2, , 子表子表n)n)，其中原子对应，其中原子对应rootroot，子，子表表 i(1i=n) i(1i1时，其余结点可分为时，其余结点可分为 m(m0) 个个互不相交的有限集互不相交的有限集T1, T2, , Tm，其中每一，其中每一

8、棵子集本身又是一棵符合本定义的树，称为棵子集本身又是一棵符合本定义的树，称为根根root的子树。的子树。第 17 页6.1 6.1 树的定义与基本术语树的定义与基本术语l树的基本操作树的基本操作l1) InitTree ( &T );1) InitTree ( &T );l 构造空树构造空树 T T。l2) DestroyTree ( &T );2) DestroyTree ( &T );l 销毁树销毁树 T T。l3) CreateTree ( &T, definition );3) CreateTree ( &T, definition );

9、l 按按 definition definition 构造树构造树 T T。l4) ClearTree ( &T );4) ClearTree ( &T );l 将树将树 T T 清空。清空。l5) TreeEmpty ( T );5) TreeEmpty ( T );l 若树若树 T T 为空，返回为空，返回 TURE TURE，否则返回，否则返回 FALSEFALSE。l6) TreeDepth ( T );6) TreeDepth ( T );l 返回树返回树 T T 的深度。的深度。第 18 页6.1 6.1 树的定义与基本术语树的定义与基本术语l树的基本操作树的基本操

10、作l7) Root ( T );7) Root ( T );l 返回返回 T T 的根结点。的根结点。l8) Value ( T, &cur_e );8) Value ( T, &cur_e );l 返回返回 T T 树中树中 cur_e cur_e 结点的值。结点的值。l9) Assign ( T, cur_e, value );9) Assign ( T, cur_e, value );l 将将 T T 树中结点树中结点 cur_e cur_e 的值赋值的值赋值为为valuevalue。l10) Parent ( T, cur_e );10) Parent ( T, cur

11、_e );l 返回返回 T T 树树 cur_e cur_e 结点的双亲。结点的双亲。l11) LeftChild ( T, cur_e );11) LeftChild ( T, cur_e );l 返回返回 T T 树树 cur_e cur_e 结点的最左孩结点的最左孩子。子。第 19 页6.1 6.1 树的定义与基本术语树的定义与基本术语l树的基本操作树的基本操作l12) RightSibling ( T, cur_e );12) RightSibling ( T, cur_e );l 返回返回 T T 树树 cur_e cur_e 结点的右兄弟。结点的右兄弟。l13) InsertChi

12、ld ( &T, &p, i, c );13) InsertChild ( &T, &p, i, c );l 将将 c c 插入到树插入到树 T T 中中 p p 所指向的第所指向的第 i i 棵子树中。棵子树中。l14) DeleteChild ( &T, &p, i );14) DeleteChild ( &T, &p, i );l 删除树删除树 T T 中中 p p 所指向的第所指向的第 i i 棵子树。棵子树。l15) TraverseTree ( T, Visit( ) );15) TraverseTree ( T, V

13、isit( ) );l 按某种次序对按某种次序对 T T 树的每个结点调用函树的每个结点调用函数数Visit()Visit()一次且至多一次。也称为按照某种一次且至多一次。也称为按照某种次序对树进行遍历。次序对树进行遍历。第 20 页6.1 6.1 树的定义与基本术语树的定义与基本术语线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其

14、它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )第 21 页6.2 6.2 二叉树二叉树l定义定义l一棵二叉树是结点的一个有限集合，该集一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。左子树和右子树的、互不相交的二叉树组成。l形式定义形式定义l数据关系数据关系 R R 满足：满足：l 若若 D D，则，则R R，称为是空二叉树。，称为是空二叉树。l 若若 D D，则，则R R H H ，H H是如下二元关系：是如下二元关系：l(1) (1) 在在D D中存在惟一的

15、称为根的数据元素中存在惟一的称为根的数据元素rootroot，它在，它在关系关系H H下无前驱；下无前驱；l(2) (2) 若若 D-root D-root，则存在，则存在 D-root D-root Dl,Dr Dl,Dr，且且DlDr=DlDr=。第 22 页6.2 6.2 二叉树二叉树l定义定义l一棵二叉树是结点的一个有限集合，该集一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。左子树和右子树的、互不相交的二叉树组成。ABCDEFGHK根结点根结点左子树左子树右子树右子

16、树第 23 页6.2 6.2 二叉树二叉树NLRLRNNNl二叉树的五种基本形态二叉树的五种基本形态空树空树只有根只有根结点结点只有左子树只有左子树只有右子树只有右子树左右子树均非空左右子树均非空第 24 页6.2 6.2 二叉树二叉树 (a) (a)、(b)(b)是不同的二叉树是不同的二叉树(a)(a)的左子树有四个结点，的左子树有四个结点，(b)(b)的左子树有两个结点的左子树有两个结点(a)(a) A A G G E E D D B B C C F F(b)(b) A A F F G G E E D D C C B B第 25 页6.2 6.2 二叉树二叉树l性质性质1：l在二叉树的第在

17、二叉树的第 i 层上至多有层上至多有2i-1 个结点个结点(i1)。i=1 i=1 ：最多：最多1 1个结点个结点i=2 i=2 ：最多：最多2 2个结点个结点i=3 i=3 ：最多：最多4 4个结点个结点GAFEDCB第 26 页6.2 6.2 二叉树二叉树l性质性质1：l在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结点个结点(i1)。用归纳法证明：用归纳法证明： 归纳基：归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点，层时，只有一个根结点， 2 i-1 = 2 0 = 1；假设对所有的假设对所有的 j, 1j i，命题成立；，命题成立

18、；二叉树上每个结点至多有两棵子树，二叉树上每个结点至多有两棵子树，则第则第 i 层的结点数层的结点数=2i-22=2i-1。第 27 页6.2 6.2 二叉树二叉树l性质性质2：l深度为深度为k的二叉树上至多含的二叉树上至多含2k-1个结点个结点(k1)。证明：证明： 基于上一条性质，深度为基于上一条性质，深度为 k 的二叉树上的二叉树上的结点数至多为：的结点数至多为：20+21+ +2k-1 = 2k-1 第 28 页6.2 6.2 二叉树二叉树l性质性质3：l 对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个叶个叶子结点、子结点、n2 个度为个度为 2 的结点，则必存在关系的结

19、点，则必存在关系式：式：n0 = n2+1证明：证明：设设 二叉树上结点总数：二叉树上结点总数：n = n0 + n1 + n2又又 二叉树上分支总数：二叉树上分支总数：b = n1 + 2n2而而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1第 29 页6.2 6.2 二叉树二叉树l两类特殊的二叉树两类特殊的二叉树满二叉树：指的是深满二叉树：指的是深度为度为 k 且含有且含有 2k-1 个个结点的二叉树。结点的二叉树。完全二叉树：树中所完全二叉树：树中所含的含的 n 个结点和满二个结点和满二叉树中编号为叉树中编号为 1 至至 n 的结点一一对应。的

20、结点一一对应。123456789101112131415abcdefghij第 30 页6.2 6.2 二叉树二叉树l性质性质4：l具有具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。证明：证明：设设 完全二叉树的深度为完全二叉树的深度为 k 则根据第二条性质得则根据第二条性质得 2k-1 n 2k 即即 k-1 log2 n n，则该结点无左孩子；否，则该结点无左孩子；否则，编号为则，编号为 2i 的结点为其左孩子结点；的结点为其左孩子结点；l(3) 若若 2i+1n，则该结点无右孩子结，则该结点无右孩子结点；否则，编号为点；否则，编号为2i+1 的结点为其

21、右孩子结的结点为其右孩子结点。点。第 32 页6.2 6.2 二叉树二叉树l性质性质5： i/2 ii+12i2i+12i+22i+3(a) i 和和 i+1 结点在同一层结点在同一层 i+12i+22i+3i2i2i+1(b) i 和和 i+1 结点不在同一层结点不在同一层i -1i -2第 33 页6.2 6.2 二叉树二叉树l二叉树的存储结构二叉树的存储结构l1. 二叉树的顺序结构二叉树的顺序结构l对于完全二叉树，采用一组连续的内存单对于完全二叉树，采用一组连续的内存单元，按编号顺序依次存储完全二叉树的结点。元，按编号顺序依次存储完全二叉树的结点。 1 2 3 4 5 6 7 m-1 1

22、 2 3 4 5 6 7 m-1 A B C D E F A B C D E FAFEDCB1 12 23 34 45 56 6第 34 页6.2 6.2 二叉树二叉树 对于一棵一般的二叉树，如果补齐构成完全对于一棵一般的二叉树，如果补齐构成完全二叉树所缺少的那些结点，便可以对二叉树的二叉树所缺少的那些结点，便可以对二叉树的结点进行编号。结点进行编号。 A A F F G G E E D D C C B B1 16 67 72 24 45 53 38 89 91010第 35 页6.2 6.2 二叉树二叉树 将二叉树原有的结点按编号存储到内存单将二叉树原有的结点按编号存储到内存单元元“相应相应

23、”的位置上。的位置上。 1 2 3 4 5 6 7 8 9 10 m-1 1 2 3 4 5 6 7 8 9 10 m-1 A B C D E 0 F 0 0 G A B C D E 0 F 0 0 G A A F F G G E E D D C C B B1 16 67 72 24 45 53 38 89 91010第 36 页6.2 6.2 二叉树二叉树 对于一些对于一些“退化二叉树退化二叉树”，顺序存储，顺序存储结构存在突出缺点：比较浪费空间。结构存在突出缺点：比较浪费空间。DACBACBDA BCDBT8ABCDBT15第 37 页6.2 6.2 二叉树二叉树2. 二叉链表二叉链表 二

24、叉链表中每个结点包含三个域：数据域、二叉链表中每个结点包含三个域：数据域、左指针域、右指针域。左指针域、右指针域。typedef struct BiTNodetypedef struct BiTNode ElemType data; ElemType data; struct BiTNode struct BiTNode * * lchild, lchild, * * rchild; rchild; BiTNode, BiTNode, * * BiTree; BiTree;数据域数据域指针域指针域指针域指针域结点结点存储数据元素存储数据元素指向右孩子指向右孩子指向左孩子指向左孩子第 38 页6

25、.2 6.2 二叉树二叉树二叉树的二叉链表表示二叉树的二叉链表表示AFEDCB二叉链表图示二叉链表图示DABC E E F F T T第 39 页6.2 6.2 二叉树二叉树3. 三叉链表三叉链表 三叉链表中每个结点包含四个域：数据域、三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域。双亲指针域、左指针域、右指针域。结点结构：结点结构：parent lchild data rchildtypedef struct BiTNodetypedef struct BiTNode ElemType data; ElemType data; struct BiTNode struct

26、 BiTNode * * lchild, lchild, * * rchild; rchild; struct BiTNode struct BiTNode * * parent; parent; BiTNode, BiTNode,* *BiTree;BiTree;第 40 页6.2 6.2 二叉树二叉树二叉树的三叉链表表示二叉树的三叉链表表示rootADEBCF CEFDAB第 41 页6.2 6.2 二叉树二叉树4. 静态二叉链表静态二叉链表 采用数组区间存贮的链表。采用数组区间存贮的链表。孩子结点在数组中孩子结点在数组中的位置。用的位置。用-1-1表示表示无左孩子或右孩子无左孩子或右孩子

27、0 01 12 23 34 45 56 6Lchild data rchildLchild data rchildroot = 0AFEDCB2 2 A 1 A 13 33 C -3 C -1 14 45 B -5 B -1 15 5-1 E -1 E -1 16 6-1 F -1 F -1 17 7-1 D -1 D 4 4第 42 页6.2 6.2 二叉树二叉树4. 静态二叉链表静态二叉链表 typedef struct BPTNode / 结点结构结点结构 TElemType data; int lchild, rchild ; BNode typedef struct BTree /

28、树结构树结构 BNode nodes MAX_TREE_SIZE ; int num_node; / 结点数目结点数目 int root; / 根结点的位置根结点的位置 BTree;第 43 页6.2 6.2 二叉树二叉树5. 双亲链表双亲链表结点结点LRTag data parentGAFEDCB B 2 B 2 C 2 C 2 A -1 A -1 D 0 D 0 E 0 E 0 F 1 F 1 G 4 G 4 0 01 12 23 34 45 56 6 data parentLRLRLL第 44 页6.2 6.2 二叉树二叉树5. 双亲链表双亲链表 typedef struct BPTNo

29、de / 结点结构结点结构 TElemType data; int parent; / 指向双亲的指针指向双亲的指针 char LRTag; / 左、右孩子标志域左、右孩子标志域 BPTNode typedef struct BPTree / 树结构树结构 BPTNode nodes MAX_TREE_SIZE ; int num_node; / 结点数目结点数目 int root; / 根结点的位置根结点的位置 BPTree;第 45 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l遍历的基本概念遍历的基本概念l 遍历：按某种搜索路径访问二叉树遍历：按某种搜索路径访问二叉树中

30、的每个结点，且每个结点仅被访问一次。中的每个结点，且每个结点仅被访问一次。l 访问：含义很广，可以是对结点的访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数各种处理，如修改结点数据、输出结点数据等。据等。l 遍历是各种数据结构最基本的操作，遍历是各种数据结构最基本的操作，许多其它的操作可以在遍历的基础上实现。许多其它的操作可以在遍历的基础上实现。l 遍历对线性结构来说很容易解决，遍历对线性结构来说很容易解决，但二叉树每个结点都可能有两棵子树，因但二叉树每个结点都可能有两棵子树，因而需要寻找一种规律，使得二叉树上的结而需要寻找一种规律，使得二叉树上的结点能线性排列。点能线性排列

31、。第 46 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的遍历二叉树的遍历l 二叉树的遍历，就是按某种次序访问二叉树的遍历，就是按某种次序访问二叉树中的全部结点，要求每个结点访问一二叉树中的全部结点，要求每个结点访问一次且仅访问一次。次且仅访问一次。l 二叉树由根、左子树、右子树三部分二叉树由根、左子树、右子树三部分组成。组成。l 二叉树的遍历可以分解为：访问根，二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树。遍历左子树和遍历右子树。第 47 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的遍历二叉树的遍历令：令：L L：遍历左子树：遍

32、历左子树 D D：访问根结点：访问根结点 R R：遍历右子树：遍历右子树有六种遍历方法：有六种遍历方法： 基本：基本：DLRDLR，LDRLDR，LRDLRD 镜象：镜象：DRLDRL，RDLRDL，RLDRLD 约定先左后右，有三种遍历方法：约定先左后右，有三种遍历方法：DLRDLR、LDRLDR、LRDLRD，由分别根据访问根结点的次序称为，由分别根据访问根结点的次序称为：先序遍历、中序遍历和后序遍历。：先序遍历、中序遍历和后序遍历。 A A F F G G E E D D C C B B第 48 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的先序遍历（二叉树的先

33、序遍历（DLR）先序遍历（先序遍历（DLRDLR）若二叉树非空若二叉树非空（1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序遍历右子树。）先序遍历右子树。例：先序遍历二叉树例：先序遍历二叉树 1 1）访问根结点）访问根结点A A 2 2）先序遍历左子树：即按）先序遍历左子树：即按 DLR DLR 的顺序遍历左子树的顺序遍历左子树 3 3）先序遍历右子树：即按）先序遍历右子树：即按 DLR DLR 的顺序遍历右子树的顺序遍历右子树 A A F F G G E E D D C C B B第 49 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二

34、叉树l二叉树的先序遍历（二叉树的先序遍历（DLR）先序遍历（先序遍历（DLRDLR）若二叉树非空若二叉树非空（1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序遍历右子树。）先序遍历右子树。 A A F F G G E E D D C C B B先序遍历序列：先序遍历序列：A,A, B,B,C,C,D,D, E,E, G,G,F F第 50 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的中序遍历（二叉树的中序遍历（LDR）中序遍历（中序遍历（LDRLDR）若二叉树非空若二叉树非空（1 1）中序遍历左子树；）中序遍历左子树；（2

35、 2）访问根结点；）访问根结点；（3 3）中序遍历右子树。）中序遍历右子树。中序遍历序列：中序遍历序列：例：中序遍历二叉树例：中序遍历二叉树 1 1）中序遍历左子树：即按）中序遍历左子树：即按 LDR LDR 的顺序遍历左子树的顺序遍历左子树 2 2）访问根结点）访问根结点A A 3 3）中序遍历右子树：即按）中序遍历右子树：即按 LDR LDR 的顺序遍历右子树的顺序遍历右子树A,A,D,B,G,E,D,B,G,E,C,FC,F A A F F G G E E D D C C B B第 51 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的后序遍历（二叉树的后序遍历（

36、LRD）后序遍历（后序遍历（LRDLRD）若二叉树非空若二叉树非空（1 1）后序遍历左子树；）后序遍历左子树；（2 2）后序遍历右子树。）后序遍历右子树。（3 3）访问根结点；）访问根结点；后序遍历序列：后序遍历序列：例：后序遍历二叉树例：后序遍历二叉树 1 1）后序遍历左子树：即按）后序遍历左子树：即按 LRD LRD 的顺序遍历左子树的顺序遍历左子树 2 2）后序遍历右子树：即按）后序遍历右子树：即按 LRD LRD 的顺序遍历右子树的顺序遍历右子树 3 3）访问根结点）访问根结点A AA AD,G,E,B,D,G,E,B, F,C,F,C, A A F F G G E E D D C C

37、 B B第 52 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树例：先序遍历、中序遍历、后序遍历二叉树。例：先序遍历、中序遍历、后序遍历二叉树。 e e d d c c b b f f a a + + * * / / - - - -后序遍历序列：后序遍历序列：中序遍历序列：中序遍历序列：先序遍历序列：先序遍历序列：a,b,c,d,-,a,b,c,d,-,* *,+,e,f,/,-,+,e,f,/,-a,+,b,a,+,b,* *,c,-,d,-,e,/,f,c,-,d,-,e,/,f-,+,a,-,+,a,* *,b,-,c,d,/,e,f,b,-,c,d,/,e,f第 53

38、页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l遍历的递归算法遍历的递归算法l 先序遍历（先序遍历（DLR）的定义：）的定义：若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树；）先序遍历左子树； （3 3）先序遍历右子树；）先序遍历右子树；上面先序遍历的定义等价于：上面先序遍历的定义等价于： 若二叉树为空，结束若二叉树为空，结束基本项（也叫终止项）基本项（也叫终止项） 若二叉树非空若二叉树非空递归项递归项 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树；）先序遍历左子树； （3 3）先序遍历右子树。）先序遍历右子树。第 5

39、4 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树1、先序遍历递归算法、先序遍历递归算法 void PreOrderTraverse ( BiTree T, Status ( * Visit ) ( ElemType e ) ) /采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit( )是访问结点的是访问结点的函数函数 /本算法先序遍历以本算法先序遍历以T为根结点指针的二叉树为根结点指针的二叉树 if ( T ) /若二叉树不若二叉树不为空为空 Visit( T-data )； /访问根结点访问根结点 PreOrderTraverse(T-lchild, Visit)

40、; /先序遍历先序遍历T的左子树的左子树 PreOrderTraverse(T-rchild, Visit); /先序遍历先序遍历T的右子树的右子树 /PreOrderTraverse最简单的最简单的 Visit 函数是：函数是：Status PrintElement( TElemType e ) /输出元素输出元素e的值的值output( e ); return OK;DABC E E F F T T第 55 页 D D ABC F G G T TE E 6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树Tra(PA) if (PA!=NULL) V(A); Tra(PA-lc);

41、 Tra(PA-rc); A A B B D D E E G G C C F FTra(PB) if (PB!=NULL) V(B); Tra(PB-lc); Tra(PB-rc); Tra(PD) if (PD!=NULL) V(D); Tra(PD-lc); Tra(PD-rc); Tra(PA) if (PA!=NULL) V(A); Tra(PA-lc); Tra(PA-rc); Tra(PB) if (PB!=NULL) V(B); Tra(PB-lc); Tra(PB-rc); Tra(PB) if (PB!=NULL) V(B); Tra(PB-lc); Tra(PB-rc);

42、Tra(PA) if (PA!=NULL) V(A); Tra(PA-lc); Tra(PA-rc); Tra(PC) if (PC!=NULL) V(C); Tra(PC-lc); Tra(PC-rc); Tra(PC) if (PC!=NULL) V(C); Tra(PC-lc); Tra(PC-rc); Tra(PC) if (PC!=NULL) V(C); Tra(PC-lc); Tra(PC-rc); Tra(PD) if (PD!=NULL) V(D); Tra(PD-lc); Tra(PD-rc); Tra(PE) if (PE!=NULL) V(E); Tra(PE-lc);

43、Tra(PE-rc); Tra(PE) if (PE!=NULL) V(E); Tra(PE-lc); Tra(PE-rc); Tra(PE) if (PE!=NULL) V(E); Tra(PE-lc); Tra(PE-rc); Tra(PF) if (PF!=NULL) V(F); Tra(PF-lc); Tra(PF-rc); Tra(PF) if (PF!=NULL) V(F); Tra(PF-lc); Tra(PF-rc); 第 56 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l先序遍历递归算法（教材先序遍历递归算法（教材P129）lvoid PreOrderTr

44、averse ( BiTree T, lStatus ( * Visit ) ( ElemType e ) )l / 采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit( )是访是访问结点的函数问结点的函数l if ( T ) l if ( Visit( T-data ) ) / 如果访问根结点如果访问根结点成功，则继续成功，则继续l if ( PreOrderTraverse(T-lchild, Visit) ) /左子树左子树l if ( PreOrderTraverse(T-rchild, Visit) ) /右子树右子树l return OK;l return ERROR;l

45、 l else return ok;l / PreOrderTraverse第 57 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树2、中序遍历递归算法、中序遍历递归算法void InOrderTraverse( BiTree T, Status ( * Visit ) ( ElemType e ) ) / 采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit( )是访问结点的是访问结点的函数函数 / 本算法中序遍历以本算法中序遍历以T为根结点指针的二叉树为根结点指针的二叉树 if ( T ) / 若二叉树若二叉树不为空不为空 InOrderTraverse( T-lc

46、hild, Visit ); / 中序遍历中序遍历T的左子树的左子树 Visit ( T-data )； / 访问根结访问根结点点 InOrderTraverse( T-rchild, Visit ); / 中序遍历中序遍历T的右子树的右子树 / InOrderTraverse第 58 页 D D ABC F G G T TE E 6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树Tra(PA) if (PA!=NULL) Tra(PA-lc); V(A) ; Tra(PA-rc); A AB BD DE EG GC CF FTra(PB) if (PB!=NULL) Tra(PB-

47、lc); V(B) ; Tra(PB-rc); Tra(PD) if (PD!=NULL) Tra(PD-lc); V(D); Tra(PD-rc); 第 59 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树3、后序遍历递归算法、后序遍历递归算法void PostOrderTraverse( BiTree T , Status ( * Visit ) ( ElemType e ) ) / 采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit( )是访问结点的是访问结点的函数函数 / 本算法后序遍历以本算法后序遍历以T为根结点指针的二叉树为根结点指针的二叉树 if ( T

48、 ) / 若二叉若二叉树不为空树不为空 PostOrderTraverse( T-lchild, Visit ); / 后序遍后序遍历左子树历左子树 PostOrderTraverse( T-rchild, Visit ); / 后序遍后序遍历右子树历右子树 Visit ( T-data )； / 访问根访问根结点结点 / PostOrderTraverse第 60 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树例例1：编写求二叉树的叶子结点个数的算法。：编写求二叉树的叶子结点个数的算法。 输入：二叉树的二叉链表输入：二叉树的二叉链表 结果：二叉树的叶子结点个数结果：二叉树的叶

49、子结点个数void leaf ( BiTree T ) / 二叉链表存贮二叉树，计算二叉树的叶子结点个数二叉链表存贮二叉树，计算二叉树的叶子结点个数 / 先序遍历的过程中进行统计，初始全局变量先序遍历的过程中进行统计，初始全局变量 n=0 if ( T ) if ( T-lchild=null & T-rchild=null ) n += 1; /若若T所指结点为叶子结点则计数所指结点为叶子结点则计数 else leaf ( T-lchild ); leaf ( T-rchild ); / if / leaf与先序遍历算与先序遍历算法比较一下！法比较一下！第 61 页6.3 6.3 遍

50、历二叉树与线索二叉树遍历二叉树与线索二叉树例例1：编写求二叉树的叶子结点个数的算法。：编写求二叉树的叶子结点个数的算法。int Countleave( BiTree T ) / 采用二叉链表存贮二叉树，返回叶子结点的个数采用二叉链表存贮二叉树，返回叶子结点的个数 if ( T-lchild=NULL & T-rchild=NULL ) return 1; else if ( !T ) return 0; return ;Countleave( T-lchild ) + Countleave( T-rchild ) D D ABC F G G T TE E 第 62 页6.3 6.3 遍

51、历二叉树与线索二叉树遍历二叉树与线索二叉树例例2：建立二叉链表。：建立二叉链表。 结果：二叉树的二叉链表。结果：二叉树的二叉链表。基本思想：基本思想： 输入（在空子树处添加字符输入（在空子树处添加字符 * * 的二叉树的二叉树的）先序序列（设每个元素是一个字符）。的）先序序列（设每个元素是一个字符）。 按先序遍历的顺序，建立二叉链表的所按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接。有结点并完成相应结点的链接。第 63 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树例例2：建立二叉链表。：建立二叉链表。* C C A A F F E E D D B B*A B D

52、 A B D * * F F * * * * * * C E C E * * * * * * A A F F E E D D C C B B先序序列：先序序列：A B D F C EA B D F C E对原来的二叉树进行扩充，在空子树处添加对原来的二叉树进行扩充，在空子树处添加 * * 。第 64 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树Status CreateBiTree ( BiTree &T ) / 按先序遍历的顺序建立二叉链表按先序遍历的顺序建立二叉链表 scanf ( &ch ); if ( ch = * ) T=NULL; / 若若ch=

53、* 则表示空子树则表示空子树 else if ( ! (T=( BiTNode * ) malloc( sizeof( BiTNode ) ) exit( OVERFLOW ); T-date = ch; / 建立（根）结点建立（根）结点 CreateBiTree( T-lchild ); / 递归构造左子树链表递归构造左子树链表 CreateBiTree( T-rchild ); / 递归构造右子树链表递归构造右子树链表 return OK; /CreateBiTree第 65 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树例例2：建立二叉链表。：建立二叉链表。A B * C

54、 * * D * * * * * * * * *A BCDATBCD第 66 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树例例3：复制二叉链表。：复制二叉链表。输入：二叉链表输入：二叉链表结果：复制的新二叉链表结果：复制的新二叉链表 D D ABC F G G T TE E 第 67 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树例例3：复制二叉链表。：复制二叉链表。void CopyBiTree( BiTree T, BiTree &newT ) / 采用后序遍历的框架，新二叉链表根为采用后序遍历的框架，新二叉链表根为 newT if ( !T )

55、newT=NULL; else CopyBiTree( T-lchild, plchild ); / 复制左子树复制左子树 CopyBiTree( T-rchild, prchild ); / 复制右子树复制右子树 newT = (BiTree) malloc( sizeof(BiTNode) ); newT-data = T-data; / 复制结点复制结点 newT-lchild = plchild; / 链接新结点的左子树链接新结点的左子树 newT-rchild = prchild; / 链接新结点的右子树链接新结点的右子树 第 68 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树

56、与线索二叉树l遍历算法的应用遍历算法的应用l1.查询二叉树中某个结点查询二叉树中某个结点l2.求二叉树的深度（后序遍历）求二叉树的深度（后序遍历）l3.判断二叉树相等判断二叉树相等l4.建立二叉树的存储结构（给出全部建立二叉树的存储结构（给出全部左右子树）左右子树）l5.由二叉树的先序序列和中序序列建由二叉树的先序序列和中序序列建立二叉树立二叉树第 69 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l遍历的非递归算法遍历的非递归算法 栈是实现递归的最常用的结构。栈是实现递归的最常用的结构。 利用一个栈来记下尚待遍历的结点或子利用一个栈来记下尚待遍历的结点或子树，以备以后访问。

57、树，以备以后访问。第 70 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l中序遍历的非递归算法中序遍历的非递归算法？中序遍历的第一个结点中序遍历的第一个结点？当前结点的后继结点当前结点的后继结点D B G E A F CD B G E A F C 若当前结点有右子树，后继结点为右子树的若当前结点有右子树，后继结点为右子树的最左下结点最左下结点;否则后继结点为否则后继结点为?二叉树的最左下结点。二叉树的最左下结点。 D D ABC F G G T TE E 第 71 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l中序遍历的非递归算法中序遍历的非递归算法？中序遍

58、历的第一个结点中序遍历的第一个结点？当前结点的后继结点当前结点的后继结点 若当前结点有右子树，后继结点为右子树的若当前结点有右子树，后继结点为右子树的最左下结点最左下结点;否则后继结点为栈顶结点。否则后继结点为栈顶结点。二叉树的最左下结点。二叉树的最左下结点。AD B G E A F C B DE GC F D D ABC F G G T TE E 第 72 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树Status InTrav( BiTree T, void(* Visit)(TelemType e) ) InitStack(S); p = T; while ( p | !

59、 StackEmpty(S) ) / 树非空树非空 或或 栈非空栈非空 if ( p ) / 若树非空若树非空 Push(S, p); p = p-lchild; / p有左子树则有左子树则p结点入栈，直到找到最左下结点结点入栈，直到找到最左下结点 else /（最左下结点）退栈，访问之（最左下结点）退栈，访问之 Pop (S, p); Visit( p-data ); p = p-rchild; / p指向右子树指向右子树 / while DesrroyStack(S); return OK; / InTrav P131 算法算法6.3第 73 页6.3 6.3 遍历二叉树与线索二叉树遍历二

60、叉树与线索二叉树l线索二叉树线索二叉树l 遍历二叉树的结果可求得结点的一遍历二叉树的结果可求得结点的一个线性序列。个线性序列。 中序序列：中序序列：D B G E A F C例如： 后序序列：后序序列：D G E B F C A 先序序列：先序序列：A B D E G C F GAFEDCB 指向线性序列中的指向线性序列中的“前趋前趋”和和 “后继后继” 的的指针，称作指针，称作“线索线索”。第 74 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l线索二叉树线索二叉树l如何在二叉链表中保存线索？如何在二叉链表中保存线索？l 借用结点的空链域保借用结点的空链域保存线索存线索 中序序列：中序序列：D B G E A F CD B G E A F CGAFEDCB包含包含 “线索线索” 的存储结构，称作的存储结构，称作 “线索链表线索链表”。 D D