第6章树和二叉树ppt课件.ppt

《第6章树和二叉树ppt课件.ppt》由会员分享，可在线阅读，更多相关《第6章树和二叉树ppt课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物主要内容YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物一、树的定义和基本术语1 1、树的定义（教材、树的定义（教材P118P118）树是树是n n（n0n0）个结点的有限集合。）个结点的有限集合。n=0n=0时称为空树。时称为空树。在任意一颗非空树中在任意一颗非空树中：（1 1）有且仅有一个特定的结点被称为根（有且仅有一个特定的结点被称为根（R

2、ootRoot）的结点；）的结点；（2 2）当）当n1n1时，其余结点被分成时，其余结点被分成m m（m0m0）个）个互不相交的有限互不相交的有限集集T1T1，T2T2，.，TmTm，其中，其中每一集合本身又是一棵树每一集合本身又是一棵树，并且，并且成为根的子树（成为根的子树（SubTreeSubTree）。）。树的定义是一个递归树的定义是一个递归YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物ABCDEFGHIJMKL树根树根例如例如: :T1T2T3YL-2011我吓了一跳，蝎子是多么丑恶

3、和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据元素数据元素+ +若干指向子树的分支若干指向子树的分支分支的个数分支的个数树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的结点度大于零的结点度大于零的结点DHIJM2 2、基本术语、基本术语（教材（教材P120P120）YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生

4、物孩子孩子: :结点子树的根结点子树的根双亲结点、兄弟结点、堂兄弟双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点祖先结点、子孙结点结点的层次结点的层次: :树的深度：树的深度：ABCDEFGHIJMKL 假设某结点在第假设某结点在第L L层层, ,则其子树的则其子树的根就在第根就在第L+1L+1层层树中叶子结点所在的最大层次树中叶子结点所在的最大层次第第1 1层层第第2 2层层第第3 3层层第第4 4层层YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物任何一棵非空树是一个二元组任何一棵非空树是一

5、个二元组 Tree = Tree = （rootroot，F F）其中：其中：root root 被称为根结点，被称为根结点，F F 被称为子树森林被称为子树森林森林：是森林：是m m（m0m0）棵互不相交的树的集合）棵互不相交的树的集合ArootBCDEFGHIJMKLF有序树、无序树：有序树、无序树： 如果将树中结点的各如果将树中结点的各子树子树看成从左到右是看成从左到右是有次序有次序的（即的（即不能互换），则称该树为不能互换），则称该树为有序有序树树，否则称为无序树。，否则称为无序树。YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到

6、愉快，证实我的猜测没有错：表里边有一个活的生物线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 ( (无后继无后继) )多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物ABCDEFGHK根结

7、点根结点左子树左子树右子树右子树二、二叉树1 1、二叉树的定义（教材、二叉树的定义（教材P121P121）二叉树是另一种树形结构。它与树形结构的区别是：二叉树是另一种树形结构。它与树形结构的区别是： （1 1）每个结点最多有两棵子树；）每个结点最多有两棵子树； （2 2）子树有左右之分）子树有左右之分YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 二叉树是二叉树是n n（n0n0）个结点的有限）个结点的有限集合。当集合。当n=0n=0时，称为空二叉树；当时，称为空二叉树；当n0n0时，时，有

8、且仅有一个结点为二叉树的根，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树每个子集又是一个二叉树。YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树YL-2011我吓了一跳，蝎子是多么丑恶

9、和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物2 2、特殊二叉树、特殊二叉树（1 1）斜树）斜树 所有的结点都只有左子树的二叉树叫左所有的结点都只有左子树的二叉树叫左斜树；所有的结点都只有右子树的二叉树叫斜树；所有的结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。右斜树。这两者统称为斜树。（2 2）满二叉树（教材）满二叉树（教材P124P124） 在一颗二叉树中，如果所有分支都存在左在一颗二叉树中，如果所有分支都存在左子树和右子树，并且所有叶子都在同一层上，子树和右子树，并且所有叶子都在同一层上，这样的二叉树成为满二叉树。这样

10、的二叉树成为满二叉树。YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物（3 3）完全二叉树完全二叉树 （教材（教材P124P124） 树中所含的树中所含的 n n 个个结点和满二叉树中编号结点和满二叉树中编号为为 1 1 至至 n n 的结点一一的结点一一对应。对应。123456789 10 11 12 13 14 15123456789 10YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物

11、性质性质 1 1：在二叉树的第在二叉树的第 i i 层上至多有层上至多有2 2i i-1 -1 个结点。个结点。(i1)(i1)3 3、二叉树的性质、二叉树的性质 （重点内容，教材（重点内容，教材P123-124P123-124） 性质性质 2 2 ：深度为深度为 k k 的二叉树上至多含的二叉树上至多含 2k-1 2k-1 个结点（个结点（k1k1）。）。注意：性质注意：性质1 1、2 2的区别的区别例如，高度为例如，高度为4 4的二叉树，第的二叉树，第4 4层的最大结点数层的最大结点数为为 ，总结点数最多为，总结点数最多为 。 815YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为

12、什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 性质性质 3 3 ：对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n n0 0 个叶子结点、个叶子结点、n n2 2 个个度为度为 2 2 的结点，则必存在关系式：的结点，则必存在关系式：n n0 0 = n= n2 2+1+1。123456789 10 性质性质 4 4 ：具有具有 n n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglog2 2n n +1 +1 。YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，

13、证实我的猜测没有错：表里边有一个活的生物 性质性质 5 5 ：若对含若对含 n n 个结点的完全二叉树从上到下且从左至右进行个结点的完全二叉树从上到下且从左至右进行 1 1 至至 n n 的编号，则对完全二叉树中任意一个编号为的编号，则对完全二叉树中任意一个编号为 i i 的结点：的结点：(1) (1) 若若 i=1i=1，则该结点是二叉树的根，无双亲，否则，编号为，则该结点是二叉树的根，无双亲，否则，编号为 i/2i/2 的结点为其双亲结点；的结点为其双亲结点；123456789 10(2) (2) 若若 2in2in，则该结点无左孩子，否则，编号为，则该结点无左孩子，否则，编号为 2i 2

14、i 的结点的结点为其左孩子结点；为其左孩子结点；(3) (3) 若若 2i+1n2i+1n，则该结点无右孩子结点，否则，编号为，则该结点无右孩子结点，否则，编号为2i+1 2i+1 的结点为其右孩子结点。的结点为其右孩子结点。YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物（1 1） 顺序存储结构顺序存储结构4 4、二叉树的存储结构、二叉树的存储结构 用一组连续的存储单元按照完全二叉树的每个结点编用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。号的顺序存放结点内容。0 1

15、2 3 4 5 6 7 81 2 3 4 5 6 7 884 5 6 72 31YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例如例如: :ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物ADEBCF rootrootlchild data rchildlchild data r

16、child结点结构结点结构: :-二叉链表二叉链表（2 2）二叉树的链式存储表示）二叉树的链式存储表示YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物typedef struct BiTNode / typedef struct BiTNode / 结点结构结点结构 TElemType data;TElemType data; struct BiTNode struct BiTNode * *lchild, lchild, * *rchild; rchild; / / 左右孩子指针左右孩子指针

17、 BiTNode, BiTNode, * *BiTree;BiTree;lchild data rchildlchild data rchild结点结构结点结构: :C C 语言的类型描述如下语言的类型描述如下: :（教材（教材P127P127）YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物ADEBCF rootroot -三叉链表三叉链表parent lchild data rchildparent lchild data rchild结点结构结点结构: :YL-2011我吓了一跳，蝎子是

18、多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 typedef struct TriTNode / typedef struct TriTNode / 结点结构结点结构 TElemType data;TElemType data; struct TriTNode struct TriTNode * *lchild, lchild, * *rchild; rchild; / / 左右孩子指针左右孩子指针 struct TriTNode struct TriTNode * *parent; /parent; /双亲指针双亲指针

19、 TriTNode, TriTNode, * *TriTree;TriTree;parent lchild data rchildparent lchild data rchild结点结构结点结构: :C C 语言的类型描述如下语言的类型描述如下: :YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物三、二叉树的遍历 所谓遍历二叉树就是所谓遍历二叉树就是按某种顺序访问按某种顺序访问二二叉树中的叉树中的每个结点一次且仅一次每个结点一次且仅一次的过程。这的过程。这里的里的访问可以是输出、比较、更新、

20、查看元访问可以是输出、比较、更新、查看元素内容等等各种操作。素内容等等各种操作。YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物1 1、按层次遍历二叉树、按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。右侧依次访问每个结点。 按层次遍历该二叉树的按层次遍历该二叉树的序列为：序列为：ABCDEFGHKKABE CFDGHYL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，

21、证实我的猜测没有错：表里边有一个活的生物2 2、按根、左子树和右子树三个部分进行遍历、按根、左子树和右子树三个部分进行遍历 二叉树的遍历方式存在六种可能：二叉树的遍历方式存在六种可能： DLRDLR（根左右）、（根左右）、LDRLDR（左根右）、（左根右）、LRDLRD（左右根）（左右根） DRLDRL（根右左）、（根右左）、RDLRDL（右根左）、（右根左）、RLDRLD（右左根）（右左根） 如果限定先左后右，则只有前三种方式，即如果限定先左后右，则只有前三种方式，即DLRDLR（称为先序遍历）、（称为先序遍历）、LDRLDR（称为中序遍历）（称为中序遍历）和和LRDLRD（称为后序遍历）。

22、（称为后序遍历）。YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物ABCDEFGD L RTD L RD L RABED L RD L RDLRDLRCFDG先序遍历结果先序遍历结果: :A BC D E F GT（1 1）DLRDLR先序遍历先序遍历YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物ABCDEFGL D RTL D RL D RABEL D RL D RLDRLDRCFDG中序

23、遍历结果中序遍历结果: :B DC A G F ET（2 2）LDRLDR中序遍历中序遍历YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物（3 3）LRDLRD后序遍历后序遍历ABCDEFGT后序遍历结果后序遍历结果: :DCBGFEAYL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物ABCDEFGHK练习：分别写出先序、中序、后序遍历的结果。练习：分别写出先序、中序、后序遍历的结果。先序序列先

24、序序列: : A B C D E F G H K A B C D E F G H K中序序列中序序列: : B D C A H G K F E B D C A H G K F E后序序列后序序列: : D C B H K G F E A D C B H K G F E AYL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 【问题【问题1 1】若已知二叉树结点的先序序列和中序序若已知二叉树结点的先序序列和中序序列，能否确定这棵二叉树呢？这样确定的二叉树是列，能否确定这棵二叉树呢？这样确定的二叉树是

25、否是唯一的呢？否是唯一的呢？ 任意一棵二叉树结点的先序序列、中序序列和后任意一棵二叉树结点的先序序列、中序序列和后序序列都是唯一的。序序列都是唯一的。 回答是肯定的。回答是肯定的。 【问题【问题2 2】若已知二叉树结点的先序序列和后】若已知二叉树结点的先序序列和后序序列，能否确定这棵二叉树？序序列，能否确定这棵二叉树？回答是不能。回答是不能。想一想，为什么？想一想，为什么？YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3 3、由遍历序列恢复二叉树、由遍历序列恢复二叉树 【例】一棵二叉树的前序

26、序列为：【例】一棵二叉树的前序序列为：ABDECABDEC，中，中序序列为：序序列为：DBEACDBEAC。请画出这棵树。请画出这棵树。ABCDE练习：已知二叉树的中序和后序序列分别为：练习：已知二叉树的中序和后序序列分别为：DCBEADCBEA和和DCEBADCEBA；请画出这棵树，并写出先序序列。；请画出这棵树，并写出先序序列。ABCDEABCDEYL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 若二叉树为空树，则空操作若二叉树为空树，则空操作；否则，；否则，（1 1）访问根结点；）访问根

27、结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序遍历右子树。）先序遍历右子树。（1 1）先序的遍历算法：）先序的遍历算法： （教材（教材P129P129，算法，算法6.16.1）4 4、遍历算法、遍历算法void PreOrderTraverse (BiTree Tvoid PreOrderTraverse (BiTree T） if (T=NULL) return;if (T=NULL) return; printf(“%c”,T-data);printf(“%c”,T-data); / / 访问根结访问根结点点 PreOrderTraverse(T-lchild);PreO

28、rderTraverse(T-lchild); / / 遍历左子树遍历左子树 PreOrderTraverse(T-rchild);PreOrderTraverse(T-rchild);/ / 遍历右子树遍历右子树 YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1 1）中序遍历左子树；）中序遍历左子树；（2 2）访问根结点；）访问根结点；（3 3）中序遍历右子树。）中序遍历右子树。（2 2）中序的遍历算法：）中序的遍历算法：v

29、oid InOrderTraverse (BiTree Tvoid InOrderTraverse (BiTree T） if (T=NULL) return; if (T=NULL) return; InOrderTraverse(T-lchild); / InOrderTraverse(T-lchild); / 遍历左子树遍历左子树 printf(“%c”,T-data); / printf(“%c”,T-data); / 访问根结访问根结点点 InOrderTraverse(T-rchild);/ InOrderTraverse(T-rchild);/ 遍历右子树遍历右子树 YL-201

30、1我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1 1）后序遍历左子树；）后序遍历左子树；（2 2）后序遍历右子树；）后序遍历右子树；（3 3）访问根结点。）访问根结点。（2 2）后序的遍历算法：）后序的遍历算法：void PostOrderTraverse (BiTree Tvoid PostOrderTraverse (BiTree T） if (T=NULL) return; if (T=NULL) return; PostOrde

31、rTraverse(T-lchild); / PostOrderTraverse(T-lchild); / 遍历左子树遍历左子树 PostOrderTraverse(T-rchild);/ PostOrderTraverse(T-rchild);/ 遍历右子树遍历右子树 printf(“%c”,T-data); / printf(“%c”,T-data); / 访问根结点访问根结点 YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物（1 1）输入结点值，构造二叉树（教材）输入结点值，构造二叉树（

32、教材P131P131算法算法6.46.4）算法基本思想算法基本思想: : 先序先序( (或中序或后序或中序或后序) )遍历二叉树，读入一个字符，遍历二叉树，读入一个字符，若读入字符为空，则二叉树为空若读入字符为空，则二叉树为空, ,若读入字符非空，若读入字符非空，则生成一个结点。则生成一个结点。 将算法中将算法中“访问结点访问结点”的操作的操作改为：生成一个结改为：生成一个结点，输入结点的值。点，输入结点的值。5 5、遍历算法的应用、遍历算法的应用YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生

33、物void CreateBiTree (BiTree void CreateBiTree (BiTree * *T)T) char ch; char ch; scanf(“%c”,&ch); scanf(“%c”,&ch); if(ch if(ch#) #) * *T=NULL; /T=NULL; /以以# #表示虚结点的值表示虚结点的值 elseelse * *T=(BiTree)malloc(sizeof(BiTNode); T=(BiTree)malloc(sizeof(BiTNode); ( (* *T)-data=ch; /T)-data=ch; /生成根结点生成根结点 Create

34、BiTree( &(CreateBiTree( &(* *T)-lchild); /T)-lchild); /构造左子树构造左子树 CreateBiTree( &(CreateBiTree( &(* *T)-rchild); /T)-rchild); /构造右子树构造右子树 YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物（2 2）求二叉树的深度）求二叉树的深度( (后序遍历后序遍历) )算法基本思想算法基本思想: : 首先分析二叉树的深度和它的左、右子树深度之首先分析二叉树的深度和它的左、右

35、子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加应为其左、右子树深度的最大值加1 1。 需先分别求得左、右子树的深度，算法中需先分别求得左、右子树的深度，算法中“访问访问结点结点”的操作改为：的操作改为：求得左、右子树深度的最大值，求得左、右子树深度的最大值，然后加然后加1 1。YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物int Depth (BiTree T )int Depth (BiTree T )

36、int depthleft,depthright; int depthleft,depthright; if (T=NULL ) return 0; if (T=NULL ) return 0; else else depthleft = Depth( T-lchild ); depthleft = Depth( T-lchild ); depthright= Depth( T-rchild ); depthright= Depth( T-rchild ); if(depthleft=depthright) if(depthleft=depthright) return depthleft+1

37、; return depthleft+1; else else return depthright+1; return depthright+1; YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物（3 3）统计二叉树中叶子结点的个数）统计二叉树中叶子结点的个数算法基本思想算法基本思想: : 类似求二叉树深度的算法。二叉树的叶类似求二叉树深度的算法。二叉树的叶子总数等于它的左、右子树叶子数之和。需子总数等于它的左、右子树叶子数之和。需先判断结点是否为叶子。先判断结点是否为叶子。YL-2011我吓

38、了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物int CountLeaf(BiTree T)int CountLeaf(BiTree T) int lnum,rnum; int lnum,rnum; if(T=NULL) return 0; if(T=NULL) return 0; else if(T-lchild=NULL)&(T-rchild=NULL) return 1; else if(T-lchild=NULL)&(T-rchild=NULL) return 1; else else lnum=Co

39、untLeaf( T-lchild); lnum=CountLeaf( T-lchild); rnum=CountLeaf( T-rchild); rnum=CountLeaf( T-rchild); return (lnum+rmum); return (lnum+rmum); YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物四、线索二叉树1 1、为什么要建线索二叉树？、为什么要建线索二叉树？-n n个结点个结点，一共有，一共有2n2n个指针个指针域，有域，有n-1n-1条分支线，也就是条分

40、支线，也就是说，其实说，其实存在存在2n-2n-（n-1n-1）= =n+1n+1个空指针域个空指针域。-在二叉链表中，想知道某个在二叉链表中，想知道某个结点的前驱和后继必须遍历一结点的前驱和后继必须遍历一次。次。线索二叉树线索二叉树可以可以将遍历时将遍历时结点的线性关系保留下来结点的线性关系保留下来YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 指向遍历顺序中的指向遍历顺序中的 “ “前驱前驱”和和“后继后继” ” 的的指针，称作指针，称作“线索线索”A B C D E F G H K D

41、 C B E 2 2、什么叫线索？、什么叫线索？ 包含包含 “ “线索线索” ” 的存储结的存储结构，称作构，称作 “ “线索链表线索链表”；加加上上“线索线索”的二叉树，称为的二叉树，称为“线索二叉树线索二叉树”。线索化（教材线索化（教材P132P132）线索化的实质（教材线索化的实质（教材P134P134）YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物增加两个标志域，增加两个标志域， LtagLtag和和RtagRtag 在二叉链表中，若结点有孩子，则让指针指向它的在二叉链表中，若结点有

42、孩子，则让指针指向它的孩子，否则，指向其前驱（后继）。孩子，否则，指向其前驱（后继）。3 3、建立线索二叉树的方法、建立线索二叉树的方法 【问题】如何区分指针的是左右孩子的指针还是前驱、【问题】如何区分指针的是左右孩子的指针还是前驱、后继的线索？后继的线索？lchildlchildLTagLTagdatadataRTagRTagrchildrchild关于关于LTagLTag和和RTagRTag的具体含义的具体含义：教材：教材P132P132LTag=LTag=0 lchild0 lchild域指示结点的左孩子域指示结点的左孩子1 lchild1 lchild域指示结点的前驱域指示结点的前驱R

43、Tag=RTag=0 rchild0 rchild域指示结点的右孩子域指示结点的右孩子1 rchild1 rchild域指示结点的后继域指示结点的后继YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物typedef struct BiThrNod typedef struct BiThrNod TElemType data; TElemType data; struct BiThrNode struct BiThrNode * *lchild, lchild, * *rchild; / rchi

44、ld; / 左右指针左右指针 PointerThr LTag, RTag; / PointerThr LTag, RTag; / 左右标志左右标志 BiThrNode, BiThrNode, * *BiThrTree;BiThrTree;二叉树的线索存储类型描述二叉树的线索存储类型描述：教材：教材P133P133 typedef enum Link, Thread PointerThr; typedef enum Link, Thread PointerThr; / Link=0: / Link=0:指针，指针，Thread=1:Thread=1:线索线索YL-2011我吓了一跳，蝎子是多么丑

45、恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物CBDAFHGIECBDAFHGIE例如：例如：YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 1 1、树、森林与二叉树的转换、树、森林与二叉树的转换 （1 1）树转换为二叉树）树转换为二叉树五、树和森林YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物YL-2011我吓了一跳，蝎子

46、是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 （2 2）森林转换为二叉树）森林转换为二叉树YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物（3 3）二叉树转树）二叉树转树YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感

47、到愉快，证实我的猜测没有错：表里边有一个活的生物（4 4）二叉树转森林）二叉树转森林YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物先根先根(次序次序)遍历遍历:后根后根(次序次序)遍历遍历: 若树不空，则先访问根结点，然后依次先根若树不空，则先访问根结点，然后依次先根遍历各棵子树。遍历各棵子树。 若树不空，则先依次后根遍历各棵子树，然若树不空，则先依次后根遍历各棵子树，然后访问根结点。后访问根结点。3 3、树和森林的遍历树和森林的遍历（1 1）树的遍历树的遍历YL-2011我吓了一跳，蝎子是

48、多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 先根遍历时顶点的访问次序：先根遍历时顶点的访问次序：A B C E F G D 后根遍历时顶点的访问次序：后根遍历时顶点的访问次序：B E G F C D AABCDEFGYL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 B C DE F G H I J K1森林中第一棵树的根结点；森林中第一棵树的根结点；2 2森林中第一棵树的子树森林；森林中第一棵树的子树森林；3森林中其它

49、树构成的森林。森林中其它树构成的森林。森林由三部分构成：森林由三部分构成：（2 2）森林的遍历森林的遍历YL-2011我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 B C DE F G H I J K例如：例如： 先序遍历时顶点的访问次序：先序遍历时顶点的访问次序：B E F C D G H I J K 后序遍历时顶点的访问次序：后序遍历时顶点的访问次序：E F B C I J K H G D先序先序遍历遍历: : 依次从依次从左至右左至右对森林中的对森林中的每一棵树每一棵树进行进行先根遍历先根遍历。中序中序遍历遍历: : 依次从依次从左至右左至右对森林中的对森林中的每一棵树每一棵树进行进行后根遍历后根遍历。