数据结构课件：第6章 树和二叉树

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

2、 树的定义与基本术语树的定义与基本术语例：右面的图是例：右面的图是一棵树一棵树 T。 T = T = A 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 4 页6.1 6.1 树的定义与基本术语树的定义与基本术语 2）除）除根根外，其余结点都外，其余结点都有且仅一个有且仅一个前趋；前趋； 3）树的结点，可以）树的结点，可以有零个有零个或或多个多个后继；后继； 4）除根之外的其它结点，都存在唯一一条）除根之外的其它结点，都存在唯一一条从根到该结点的从根到该结点的路径路径； 5）树是一种分支结构（除了一个称为）树是一种分支结构（除了一个称为根

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

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

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

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

8、身又是一棵符合本定义的子集本身又是一棵符合本定义的树树，称为根，称为根root的的子树子树。第 1717 页6.1 6.1 树的定义与基本术语树的定义与基本术语l树的基本操作树的基本操作1) 1) InitTreeInitTree ( &T ); ( &T ); 构造空树构造空树 T T。2) 2) DestroyTreeDestroyTree ( &T ); ( &T ); 销毁树销毁树 T T。3) 3) CreateTreeCreateTree ( &T, definition ); ( &T, definition ); 按按 definition definition 构造树构造树

9、T T。4) 4) ClearTreeClearTree ( &T ); ( &T ); 将树将树 T T 清空。清空。5) 5) TreeEmptyTreeEmpty ( T ); ( T ); 若树若树 T T 为空，返回为空，返回 TURETURE，否则返回，否则返回 FALSEFALSE。6) 6) TreeDepthTreeDepth ( T ); ( T ); 返回树返回树 T T 的深度。的深度。第 1818 页6.1 6.1 树的定义与基本术语树的定义与基本术语l树的基本操作树的基本操作7) 7) RootRoot ( T ); ( T ); 返回返回 T T 的根结点。的根结

10、点。8) 8) ValueValue ( T, &cur_e ); ( T, &cur_e ); 返回返回 T T 树中树中 cur_e cur_e 结点的值。结点的值。9) 9) AssignAssign ( T, cur_e, value ); ( T, cur_e, value ); 将将 T T 树中结点树中结点 cur_e cur_e 的值赋值为的值赋值为valuevalue。10) 10) ParentParent ( T, cur_e ); ( T, cur_e ); 返回返回 T T 树树 cur_e cur_e 结点的双亲。结点的双亲。11) 11) LeftChildLef

11、tChild ( T, cur_e ); ( T, cur_e ); 返回返回 T T 树树 cur_e cur_e 结点的最左孩子。结点的最左孩子。第 1919 页6.1 6.1 树的定义与基本术语树的定义与基本术语l树的基本操作树的基本操作12) 12) RightSiblingRightSibling ( T, cur_e ); ( T, cur_e ); 返回返回 T T 树树 cur_e cur_e 结点的右兄弟。结点的右兄弟。13) 13) InsertChildInsertChild ( &T, &p, i, c ); ( &T, &p, i, c ); 将将 c c 插入到树插

12、入到树 T T 中中 p p 所指向的第所指向的第 i i 棵棵子树中。子树中。14) 14) DeleteChildDeleteChild ( &T, &p, i ); ( &T, &p, i ); 删除树删除树 T T 中中 p p 所指向的第所指向的第 i i 棵子树。棵子树。15) 15) TraverseTreeTraverseTree ( T, ( T, Visit( )Visit( ) ); ); 按某种次序对按某种次序对 T T 树的每个结点调用函数树的每个结点调用函数Visit()Visit()一次且至多一次。也称为按照某种次一次且至多一次。也称为按照某种次序对树进行序对树进

13、行遍历遍历。第 2020 页6.1 6.1 树的定义与基本术语树的定义与基本术语线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )第 2121 页6.2 6.2 二叉树二叉树l定义定义第 2222 页6.2 6.2 二叉树二叉树l定义定义ABCDEFGHK根结点根结点左子树左

14、子树右子树右子树第 2323 页6.2 6.2 二叉树二叉树NLRLRNNNl二叉树的五种基本形态二叉树的五种基本形态空树空树只有根只有根结点结点只有左子树只有左子树只有右子树只有右子树左右子树均非空左右子树均非空第 2424 页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第 2525 页6.2 6.2 二叉树二叉树l性质

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

16、命题成立；命题成立；二叉树上每个结点至多有两棵子树，二叉树上每个结点至多有两棵子树，则第则第 i 层的结点数层的结点数=2i-2 2=2i-1。第 2727 页6.2 6.2 二叉树二叉树l性质性质2：深度为深度为k的二叉树上至多含的二叉树上至多含2k-1个结点个结点(k1)。证明：证明： 基于上一条性质，深度为基于上一条性质，深度为 k 的二叉树上的二叉树上的结点数至多为：的结点数至多为：20+21+ +2k-1 = 2k-1 第 2828 页6.2 6.2 二叉树二叉树l性质性质3： 对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个叶子结个叶子结点、点、n2 个度为个度为 2

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

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

19、编号为2i+1 的结点为其的结点为其右孩子右孩子结点。结点。第 3232 页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第 3333 页6.2 6.2 二叉树二叉树l二叉树的存储结构二叉树的存储结构1. 二叉树的顺序结构二叉树的顺序结构对于完全二叉树，采用一组连续的内存单元，对于完全二叉树，采用一组连续的内存单元，按编号顺序按编号顺序依次存储完全二叉树的结点。依次存储完全二叉树的结点。 1 2

20、3 4 5 6 7 m-1 1 2 3 4 5 6 7 m-1 A B C D E FA B C D E FAFEDCB1 12 23 34 45 56 6第 3434 页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第 3535 页6.2 6.2 二叉树二叉树 将二叉树原有的结点按编号存储到内存单将二叉树原有的

21、结点按编号存储到内存单元元“相应相应”的位置上。的位置上。 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 A B C C D E D E 0 0 F F 0 00 0 G G A A F F G G E E D D C C B B1 16 67 72 24 45 53 38 89 91010第 3636 页6.2 6.2 二叉树二叉树 对于一些对于一些“退化二叉树退化二叉树”，顺序存储，顺序存储结构存在突出缺点：结构存在突出缺点：比较浪费空间比较浪费空间。DACBACBDA BCDBT8ABCDBT15第 3737 页6.2 6.2

22、 二叉树二叉树2. 二叉链表二叉链表 二叉链表中每个结点包含三个域：数据域、二叉链表中每个结点包含三个域：数据域、左指针域、右指针域。左指针域、右指针域。typedef struct BiTNodetypedef struct BiTNode ElemType data; ElemType data; struct BiTNode struct BiTNode * * lchildlchild, , * * rchildrchild; ; BiTNode, BiTNode, * * BiTree; BiTree;数据域数据域指针域指针域指针域指针域结点结点存储数据元素存储数据元素指向右孩子指向

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

24、a; struct BiTNode struct BiTNode * * lchildlchild, , * * rchildrchild; ; struct BiTNode struct BiTNode * * parentparent; ; BiTNode, BiTNode,* *BiTree;BiTree;第 4040 页6.2 6.2 二叉树二叉树二叉树的三叉链表表示二叉树的三叉链表表示rootADEBCF CEFDAB第 4141 页6.2 6.2 二叉树二叉树4. 静态二叉链表静态二叉链表 采用数组区间存贮的链表。采用数组区间存贮的链表。孩子结点在数组中孩子结点在数组中的位置。用的

25、位置。用-1-1表示表示无左孩子或右孩子无左孩子或右孩子0 01 12 23 34 45 56 6Lchild data rchildLchild data rchildroot = 0AFEDCB2 2 A 1 A 13 C -13 C -15 B -15 B -1-1 E -1-1 E -1-1 F -1-1 F -1-1 D 4-1 D 4第 4242 页6.2 6.2 二叉树二叉树4. 静态二叉链表静态二叉链表 typedef struct BPTNode / 结点结构结点结构 TElemType data; int lchild, rchild ; BNode typedef str

26、uct BTree / 树结构树结构 BNode nodes MAX_TREE_SIZE ; int num_node; / 结点数目结点数目 int root; / 根结点的位置根结点的位置 BTree;第 4343 页6.2 6.2 二叉树二叉树5. 双亲链表双亲链表结点结点LRTag data parentGAFEDCB B 2B 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第 4444 页6.2 6.2 二叉树二叉树5. 双亲链表双亲链表 typed

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

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

29、叉树上的结点能线性排列。第 4646 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的遍历二叉树的遍历 二叉树由二叉树由根根、左子树、左子树、右子树右子树三部分组三部分组成。成。 二叉树的遍历二叉树的遍历可以分解为：访问可以分解为：访问根根，遍，遍历历左子树左子树和遍历和遍历右子树。右子树。第 4747 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的遍历二叉树的遍历令：令：L L：遍历左子树：遍历左子树 D D：访问根结点访问根结点 R R：遍历右子树遍历右子树有六种遍历方法：有六种遍历方法： 基本：基本：D DL LR R，L LD DR R

30、，L LR RD D 镜象：镜象：D DR RL L，R RD DL L，R RL LD D 约定约定先左后右先左后右，有三种遍历方法：，有三种遍历方法：D DL LR R、L LD DR R、L LR RD D，由分别根据，由分别根据访问根结点的次序访问根结点的次序称为称为：先序遍历先序遍历、中序遍历中序遍历和和后序遍历后序遍历。 A A F F G G E E D D C C B B第 4848 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的先序遍历二叉树的先序遍历（DLR）先序遍历（先序遍历（D DL LR R）若二叉树非空若二叉树非空（1 1）访问根结点；）访

31、问根结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序遍历右子树。）先序遍历右子树。例：先序遍历二叉树例：先序遍历二叉树 1 1）访问根结点）访问根结点A A 2 2）先序遍历左子树：即按）先序遍历左子树：即按 D DL LR R 的顺序遍历的顺序遍历左子树左子树 3 3）先序遍历右子树：即按）先序遍历右子树：即按 D DL LR R 的顺序遍历的顺序遍历右子树右子树 A A F F G G E E D D C C B B第 4949 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的先序遍历二叉树的先序遍历（DLR）先序遍历（先序遍历（D DL LR R）

32、若二叉树非空若二叉树非空（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第 5050 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的中序遍历二叉树的中序遍历（LDR）中序遍历（中序遍历（L LD DR R）若二叉树非空若二叉树非空（1 1）中序遍历左子树；）中序遍历左子树；（2 2）访问根结点；）访问根结点；（3 3）中序遍历右子树。）中序遍历右子树。

33、中序遍历序列：中序遍历序列：例：中序遍历二叉树例：中序遍历二叉树 1 1）中序遍历左子树：即按）中序遍历左子树：即按 L LD DR R 的顺序遍历的顺序遍历左子树左子树 2 2）访问根结点）访问根结点A A 3 3）中序遍历右子树：即按）中序遍历右子树：即按 L LD DR R 的顺序遍历的顺序遍历右子树右子树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第 5151 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l二叉树的后序遍历二叉树的后序遍历（LRD）后序遍历（后序遍历（L LR RD D）若二叉树非空若二叉

34、树非空（1 1）后序遍历左子树；）后序遍历左子树；（2 2）后序遍历右子树。）后序遍历右子树。（3 3）访问根结点；）访问根结点；后序遍历序列：后序遍历序列：例：后序遍历二叉树例：后序遍历二叉树 1 1）后序遍历左子树：即按）后序遍历左子树：即按 L LR RD D 的顺序遍历的顺序遍历左子树左子树 2 2）后序遍历右子树：即按）后序遍历右子树：即按 L LR RD D 的顺序遍历的顺序遍历右子树右子树 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 B B第 5252 页6.3 6.3 遍历二叉树与

35、线索二叉树遍历二叉树与线索二叉树例：先序遍历、中序遍历、后序遍历二叉树。例：先序遍历、中序遍历、后序遍历二叉树。 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,c,-,d,- -, ,e,/,fe,/,f- -, ,+,a,+,a,* *,b,-,c,d,b,-,c,d,/,e,f/,e,f第 5353 页6.3 6.3 遍历二叉树与线索二叉

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

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

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

39、 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); Tra(PA) if (PA!=NU

40、LL) 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); Tra(PE-rc); Tra(PE

41、) 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); 第 5656 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l先序遍历递归算法先序遍历递归算法（教材（教材P129）void PreOrderTraverse ( BiTree T

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

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

44、树的左子树 Visit ( T-data )； / 访问根结点访问根结点 InOrderTraverse( T-rchild, Visit ); / 中序遍历中序遍历T的右子树的右子树 / InOrderTraverse第 5858 页 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-lc); V(B) ; Tra(PB-rc); Tra

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

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

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

48、求二叉树的叶子结点个数的算法。：编写求二叉树的叶子结点个数的算法。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 第 6262 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树例例2：建立二叉

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

50、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对原来的二叉树进行扩充，在空子树处添加对原来的二叉树进行扩充，在空子树处添加 * * 。第 6464 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树Status CreateBiTree ( BiTree &T ) / 按先序遍历的顺序建立二叉链表按先序遍历的顺序建立二叉链表 scanf ( &ch ); if ( ch = * ) T=NULL; / 若若ch= * 则表示空子树则表示空子树 else if ( ! (T=( B

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

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

53、iTree( T-lchild, plchild ); / 复制左子树复制左子树 CopyBiTree( T-rchild, prchild ); / 复制右子树复制右子树 newT = (BiTree) malloc( sizeof(BiTNode) ); newT-data = T-data; / 复制结点复制结点 newT-lchild = plchild; / 链接新结点的左子树链接新结点的左子树 newT-rchild = prchild; / 链接新结点的右子树链接新结点的右子树 第 6868 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l遍历算法的应用遍历算法的

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

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

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

57、kEmpty(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第 7373 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与

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

59、中序序列：D B G E A F CD B G E A F CGAFEDCB包含包含 “线索线索” 的存储结构，称作的存储结构，称作 “线索链表线索链表”。 D D ABC F G G T TE E 第 7575 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l线索链表中的结点线索链表中的结点在二叉链表的结点中增加两个标志域在二叉链表的结点中增加两个标志域Ltag, Rtag： lchild ltag data rtag rchild 0 0 表示表示 lchild(p) lchild(p) 为指向左孩子的指针为指向左孩子的指针ltag(p)=ltag(p)= 1 1 表示表示

60、 lchild(p) lchild(p) 为指向直接前驱的线索为指向直接前驱的线索 0 0 表示表示 rchild(p) rchild(p) 为指向右孩子的指针为指向右孩子的指针rtag(p)=rtag(p)= 1 1 表示表示 rchild(p) rchild(p) 为指向直接后继的线索为指向直接后继的线索第 7676 页6.3 6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树l线索链表的类型说明线索链表的类型说明typedef enum link, thread PointerTag; / link=0, thread=1typedef struct BiThrNode TElemTy