1、Data StructureData StructurePage 12023-1-10q学习目标学习目标v领会树和二叉树的类型定义，领会树和二叉树的类型定义，理解树和二叉树的结构理解树和二叉树的结构差别差别。v熟记熟记二叉树的主要特性二叉树的主要特性，并掌握它们的证明方法。，并掌握它们的证明方法。v掌握掌握二叉树的各种遍历算法二叉树的各种遍历算法，并能灵活运用遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。实现二叉树的其它操作。v熟练掌握二叉树各种熟练掌握二叉树各种存储结构存储结构及其建立的算法。及其建立的算法。Data StructureData StructurePage 22023-
2、1-10q重点和难点重点和难点v重点：二叉树和树的重点：二叉树和树的遍历遍历及其应用。及其应用。v难点：编写实现难点：编写实现二叉树和树的各种操作的递归算法二叉树和树的各种操作的递归算法。q知识点知识点v树的类型定义、二叉树的类型定义树的类型定义、二叉树的类型定义v二叉树的存储表示二叉树的存储表示v二叉树的遍历以及其它操作的实现二叉树的遍历以及其它操作的实现Data StructureData StructurePage 32023-1-10v社会的组织结构社会的组织结构v家族的族谱家族的族谱v计算机中的目录组织计算机中的目录组织描述层次结构，是一种一对多的逻辑关系描述层次结构，是一种一对多的
3、逻辑关系Data StructureData StructurePage 42023-1-10树型结构是一类非常重要的非线性数据结构。树型结构是一类非常重要的非线性数据结构。Data StructureData StructurePage 52023-1-10q 树树(tree)(tree)v是是n(nn(n 0)0)个结点的有限集个结点的有限集T T；v在任意一棵非空树中，在任意一棵非空树中，有且仅有一个特定的结点，称为树的有且仅有一个特定的结点，称为树的根根(root)(root)；当当n1n1时，其余结点可分为时，其余结点可分为m(m0)m(m0)个个互不相交互不相交的有限集的有限集T1
4、,T2,T1,T2,TmTm，其中每一个集合本身又是一棵树，称为根的，其中每一个集合本身又是一棵树，称为根的子子树树(subtreesubtree)。v特点特点：非空树中至少有一个结点非空树中至少有一个结点根；根；树中各子树是互不相交的集合。树中各子树是互不相交的集合。Data StructureData StructurePage 62023-1-10AABCDEFGHIJKLM只有根结只有根结点的树点的树有子树有子树的树的树根根子树子树Data StructureData StructurePage 72023-1-10ADT ADT TreeTree 数据对象：数据对象：D D是具有相同
5、特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系：数据关系：若若 D D 为空集，则称为为空集，则称为空树空树；若若 D D 中仅含一个数据元素，则关系中仅含一个数据元素，则关系R R为空集为空集；若若 D D 中含多于一个数据元素，则中含多于一个数据元素，则 R=HR=H，H H是如下二元关系：是如下二元关系：(1)(1)在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素 rootroot，它在关系，它在关系H H下无前驱；下无前驱；(2)(2)当当n1n1时，其余数据元素可分为时，其余数据元素可分为 m(m0)m(m0)个互不相交的个互不相交的(非空非空)有限
6、有限 集集 T1,T2,T1,T2,Tm,Tm,其中每一个子集本身又是一棵符合本定义的树，其中每一个子集本身又是一棵符合本定义的树，称为根称为根 root root 的子树，每一棵子树的根的子树，每一棵子树的根xixi都是根都是根rootroot的后继，即的后继，即 H H，i=1,2,i=1,2,m,m。Data StructureData StructurePage 82023-1-10基本操作：基本操作：InitTree(&TInitTree(&T););操作结果：构造空树操作结果：构造空树 T T。CreateTree(&T,definitionCreateTree(&T,defini
7、tion););初始条件：初始条件：definition definition 给出树给出树T T的定义。的定义。操作结果：按操作结果：按 definition definition 构造树构造树 T T。DestroyTree(&TDestroyTree(&T););初始条件：树初始条件：树 T T 存在。存在。操作结果：销毁树操作结果：销毁树 T T。TreeEmpty(TTreeEmpty(T););初始条件：树初始条件：树 T T 存在。存在。操作结果：若操作结果：若 T T 为空树，则返回为空树，则返回 TRUETRUE，否则返回，否则返回 FALSEFALSE。Data Struc
8、tureData StructurePage 92023-1-10TreeDepth(TTreeDepth(T););初始条件：树初始条件：树T T存在。存在。操作结果：返回操作结果：返回T T的深度。的深度。Root(T);Root(T);初始条件：树初始条件：树 T T 存在。存在。操作结果：返回操作结果：返回 T T 的根。的根。Value(T,cur_e);Value(T,cur_e);初始条件：树初始条件：树 T T 存在，存在，cur_e cur_e 是是 T T 中某个结点。中某个结点。操作结果：返回操作结果：返回 cur_e cur_e 的值。的值。Data Structure
9、Data StructurePage 102023-1-10Parent(T,cur_e);Parent(T,cur_e);初始条件：树初始条件：树 T T 存在，存在，cur_e cur_e 是是 T T 中某个结点。中某个结点。操作结果：若操作结果：若 cur_e cur_e 是是T T的非根结点，则返回它的双亲，的非根结点，则返回它的双亲，否则返回否则返回“空空”。LeftChild(TLeftChild(T,cur_e);,cur_e);初始条件：树初始条件：树 T T 存在，存在，cur_e cur_e 是是 T T 中某个结点。中某个结点。操作结果：若操作结果：若 cur_e cu
10、r_e 是是T T的非叶子结点，则返回它的最左的非叶子结点，则返回它的最左 孩子，否则返回孩子，否则返回“空空”。RightSibling(TRightSibling(T,cur_e);,cur_e);初始条件：树初始条件：树 T T 存在，存在，cur_e cur_e 是是 T T 中某个结点。中某个结点。操作结果：若操作结果：若 cur_e cur_e 有右兄弟，则返回它的右兄弟，否则有右兄弟，则返回它的右兄弟，否则 返回返回“空空”。Data StructureData StructurePage 112023-1-10TraverseTree(TTraverseTree(T,visit
11、();,visit();初始条件：树初始条件：树T T存在，存在，visit visit 是对结点操作的应用函数。是对结点操作的应用函数。操作结果：按某种次序对操作结果：按某种次序对 T T 的每个结点调用函数的每个结点调用函数 visit()visit()一次且至多一次。一旦一次且至多一次。一旦 visit()visit()失败，则操作失败，则操作 失败。失败。Assign(T,cur_e,value);Assign(T,cur_e,value);初始条件：树初始条件：树T T存在，存在，cur_e cur_e 是是 T T 中某个结点。中某个结点。操作结果：结点操作结果：结点 cur_e
12、cur_e 赋值为赋值为 valuevalue。ClearTree(&TClearTree(&T););初始条件：树初始条件：树 T T 存在。存在。操作结果：将树操作结果：将树 T T 清为空树。清为空树。Data StructureData StructurePage 122023-1-10InsertChild(&TInsertChild(&T,&p,i,c);,&p,i,c);初始条件：树初始条件：树 T T 存在，存在，p p 指向指向T T中某个结点，中某个结点，1ip 1ip 所所 指结点的度指结点的度1 1，非空树，非空树 c c 与与 T T 不相交。不相交。操作结果：插入操
13、作结果：插入 c c 为为 T T 中中 p p 所指结点的第所指结点的第 i i 棵子树。棵子树。DeleteChild(&TDeleteChild(&T,&p,i);,&p,i);初始条件：树初始条件：树 T T 存在，存在，p p 指向指向 T T 中某个结点，中某个结点，1ip1ip 指结点的度。指结点的度。操作结果：删除操作结果：删除 T T 中中 p p 所指结点的第所指结点的第 i i 棵子树。棵子树。ADT Tree ADT TreeData StructureData StructurePage 132023-1-10q 基本术语基本术语v结点结点(node)(node)：包
14、含一个数据元素及若干指向其子树的分支。：包含一个数据元素及若干指向其子树的分支。v结点的度结点的度(degree)(degree)：结点拥有的子树数。：结点拥有的子树数。v叶子叶子(leaf)(leaf)：度为：度为0 0的结点。的结点。v分支结点分支结点：度不为：度不为0 0的结点。的结点。v树的度树的度：一棵树中各结点的度的最大值。：一棵树中各结点的度的最大值。v孩子孩子(child)(child)：结点的子树的根称为该结点的孩子。：结点的子树的根称为该结点的孩子。v双亲双亲(parents)(parents)：孩子结点的上层结点。：孩子结点的上层结点。v兄弟兄弟(sibling)(sib
15、ling)：同一双亲的孩子之间互称为兄弟。：同一双亲的孩子之间互称为兄弟。v祖先祖先：从根结点到该结点所经分支上的所有结点。：从根结点到该结点所经分支上的所有结点。v子孙子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。：以某结点为根的子树中的任一结点都称为该结点的子孙。Data StructureData StructurePage 142023-1-10v结点的层次结点的层次(level)(level)：从根结点算起，根为第一层，根的孩子为：从根结点算起，根为第一层，根的孩子为 第二层第二层。v堂兄弟堂兄弟：其双亲在同一层的结点互为堂兄弟。：其双亲在同一层的结点互为堂兄弟。v深度深度
16、(depth)(depth)：树中结点的最大层次。：树中结点的最大层次。v有序树有序树：将树中结点的各子树看成从左至右是有次序的，即不能：将树中结点的各子树看成从左至右是有次序的，即不能 互换。互换。v无序树无序树：将树中结点的各子树看成从左至右是无次序的，即可以：将树中结点的各子树看成从左至右是无次序的，即可以 互换。互换。v森林森林(forest)(forest)：m(mm(m 0)0)棵互不相交的树的集合。棵互不相交的树的集合。Data StructureData StructurePage 152023-1-10ABCDEFGHIJKLM结点结点A A的度：的度：结点结点B B的度：的
17、度：结点结点M M的度：的度：叶子：叶子：结点结点A A的孩子：的孩子：结点结点B B的孩子：的孩子：结点结点I I的双亲：的双亲：结点结点L L的双亲：的双亲：结点结点B B，C C，D D为为结点结点K K，L L为为树的度：树的度：结点结点A A的层次：的层次：结点结点M M的层次：的层次：树的深度：树的深度：结点结点A A是结点是结点F F，G G的的结点结点F F，G G为为3203B，C，DE，F14K，L，F，G，M，I，JDE兄弟兄弟兄弟兄弟4堂兄弟堂兄弟祖先祖先Data StructureData StructurePage 162023-1-10q 树的表示方法树的表示方法
18、v树形表示法：树形表示法：自然界倒长的树；自然界倒长的树；v文氏表示法：文氏表示法：用集合表示；用集合表示；v凹入表示法：凹入表示法：类似书目；类似书目；v嵌套括号表示法：嵌套括号表示法：广义表表示法。广义表表示法。树形树形文氏文氏ABDCG凹入凹入ABCDG嵌套括号嵌套括号(A(B,C(G),D)Data StructureData StructurePage 172023-1-10树和线性结构对照树和线性结构对照线性结构线性结构树结构树结构存在存在唯一的没有前驱唯一的没有前驱的的 首元素首元素 存在存在唯一的没有前驱的唯一的没有前驱的 根结点根结点 存在存在唯一的没有后继唯一的没有后继的的
19、 尾元素尾元素 存在存在多个没有后继多个没有后继的的 叶子叶子 其余元素均存在其余元素均存在唯一唯一的的 前驱元素前驱元素 和唯一和唯一的的 后继元素后继元素 其余结点均存在其余结点均存在唯一的唯一的 前驱前驱(双亲双亲)结点结点 和和多多个个 后继后继(孩子孩子)结点结点 Data StructureData StructurePage 182023-1-10q 二叉树的定义二叉树的定义v是是n(n=0)n(n=0)个结点的有限集个结点的有限集，其子树分为，其子树分为互不相交的互不相交的两个集合，两个集合，分别称为分别称为左子树和右子树左子树和右子树，左子树和右子树也是二叉树左子树和右子树也
20、是二叉树。ABCDEIJGH根结点根结点左子树左子树右子树右子树Data StructureData StructurePage 192023-1-10v二叉树不是树的特例。二叉树不是树的特例。v特点特点每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2 2的结点的结点)；二叉树的子树有左、右之分，且其次序不能任意颠倒。二叉树的子树有左、右之分，且其次序不能任意颠倒。v基本形态基本形态AABABABC空二空二叉树叉树只有根结点只有根结点的二叉树的二叉树右子树右子树为空为空左子左子树为树为空空左、右子树左、右子树均非空均非空Data StructureData Stru
21、cturePage 202023-1-10二叉树的性质二叉树的性质q性质性质1：在二叉树的第在二叉树的第 i 层至多有层至多有 2i-1 个结点个结点(i1)。证明：i=1,只有根结点，显然成立 设i=k时成立，最多有2k-1个结点 当i=k+1时，最多的结点个数：2k-1*2=2k-1+1=2k=2(k+1)-1Data StructureData StructurePage 212023-1-10二叉树的性质二叉树的性质q性质性质2：深度为深度为 k 的二叉树至多有的二叉树至多有 2k-1 个结点。个结点。证明：二叉树的结点个数为：1+2+2k-1=2k-1Data StructureDa
22、ta StructurePage 222023-1-10二叉树的性质二叉树的性质q 性质性质3 3：对于任何一棵二叉树对于任何一棵二叉树T T，若其终端结点，若其终端结点(叶子叶子)数为数为 n n0 0，度为，度为1 1的结点数为的结点数为n n1 1，度为，度为2 2的结点数的结点数n n2 2，则则n n0 0=n=n2 2+1+1。证明：设n1为T中度为1的结点数，则总结点数：n=n0+n1+n2 (1)另：除根结点外，所有结点都有且仅有一个双亲结点，也就是仅有一个分支进入，若B为分支数，则n=B+1 =n1+2*n2+1 (2)由(1)和(2)有：n1+2*n2 1=n0+n1+n2
23、 故 n0=n2+1;Data StructureData StructurePage 232023-1-10几种特殊形式的二叉树几种特殊形式的二叉树q 满二叉树满二叉树v深度为深度为k k且有且有2 2k k-1-1个个结点的二叉树。结点的二叉树。v特点特点每一层上的结点数都是最大结点数；每一层上的结点数都是最大结点数；所有的分支结点的度数都为所有的分支结点的度数都为2 2；叶子结点都在同一层次上。叶子结点都在同一层次上。123114589121367101415Data StructureData StructurePage 242023-1-10q 完全二叉树完全二叉树v若对满二叉树的结
24、点从上到下从左至右进行编号，则深度为若对满二叉树的结点从上到下从左至右进行编号，则深度为k k且有且有n n个结点的二叉树称为完全二叉树，当且仅当其每一个结点都与深度个结点的二叉树称为完全二叉树，当且仅当其每一个结点都与深度为为k k的满二叉树的编号从的满二叉树的编号从1 1到到n n一一对应时。一一对应时。v特点特点叶子结点只可能在层次最大的两层上出现；叶子结点只可能在层次最大的两层上出现；前前k-1k-1层中的结点都是层中的结点都是“满满”的，且第的，且第 k k 层的结点都集中在左层的结点都集中在左边。边。123114589126710Data StructureData Structu
25、rePage 252023-1-101234567123456思考：满二叉树与完全二叉树的关系？思考：满二叉树与完全二叉树的关系？Data StructureData StructurePage 262023-1-10q 性质性质4 4：具有具有n n个结点的完全二叉树的深度是个结点的完全二叉树的深度是 loglog2 2n n+1+1。证明：证明：假设假设n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k k，则，则n n的值应大于深度为的值应大于深度为k-1k-1的满二叉树的结点数的满二叉树的结点数2 2k-1k-1-1-1，小于等于深度为小于等于深度为k k的满二叉树的结点数的
26、满二叉树的结点数2 2k k-1-1，即，即 2 2k-1k-1-1n2-1n2k k-1 -1 进一步可推导出进一步可推导出 2 2k-1k-1n+12n+12k k两边取对数后，有两边取对数后，有 k-1logk-11i1，则其则其双亲是双亲是 i/2i/2；v如果如果2in2in，则结点，则结点i i无左孩子；如果无左孩子；如果2i2i n n，则其，则其左孩子左孩子是是2 2i i；v如果如果2i+1n2i+1n，则结点，则结点i i无右孩子；如果无右孩子；如果2i+12i+1 n n，则其，则其右右孩子是孩子是2 2i+1i+1。Data StructureData Structur
27、ePage 282023-1-102i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1 i/2i/2 j层j+1层Data StructureData StructurePage 292023-1-102i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1LCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1)i/2i/2 Data StructureData StructurePage 302023-1-10二叉树的存储结构二叉树的存储结构q 顺序存储结构顺序存储结构v用一组用一组地址连续的存储单元存储地址连续的存储单元存储二
28、叉树中的数据元素。二叉树中的数据元素。完全二叉树完全二叉树，只要，只要从根起按层序存储从根起按层序存储即可。将完全二叉树上编即可。将完全二叉树上编号为号为 i i 的结点元素存储在一维数组中下标为的结点元素存储在一维数组中下标为 i-1 i-1 的分量中。的分量中。一般的二叉树一般的二叉树，可，可对照完全二叉树的编号进行相应的存储对照完全二叉树的编号进行相应的存储，但，但在在没有结点的分量中需填充空白字符没有结点的分量中需填充空白字符(例如填充例如填充0)。v顺序存储表示顺序存储表示#define MAX_TREE_SIZE 100#define MAX_TREE_SIZE 100 /最大结点
29、数最大结点数TypedefTypedef TElemType SqBiTreeMAX_TREE_SIZETElemType SqBiTreeMAX_TREE_SIZE;/0/0号根结点号根结点SqBiTree btSqBiTree bt;Data StructureData StructurePage 312023-1-1012345101167891211 1210987654321 1 2 3 4 5 6 7 8 9 10 11 12没有浪费没有浪费Data StructureData StructurePage 322023-1-10abcdefggf0000edcba 1 2 3 4
30、5 6 7 8 9 10 11浪费浪费4个个Data StructureData StructurePage 332023-1-1000004000300020112341 2 3 4 5 6 7 8 9 10 11 12 13 14 15浪费浪费11个个Data StructureData StructurePage 342023-1-10顺序存储结构适用于满二叉树和完全二叉树的存储。顺序存储结构适用于满二叉树和完全二叉树的存储。Data StructureData StructurePage 352023-1-10链式存储结构链式存储结构q 二叉链表二叉链表v结点除包括元素自身的信息外，还
31、包括指向其左、右子树的指针。结点除包括元素自身的信息外，还包括指向其左、右子树的指针。即结点要包括即结点要包括数据域，左子树指针域和右子树指针域数据域，左子树指针域和右子树指针域。v 二叉链表的存储表示二叉链表的存储表示typedef struct BiTNodetypedef struct BiTNodeTElemTypeTElemType data;data;struct BiTNodestruct BiTNode *lchild,lchild,*rchildrchild;BiTNodeBiTNode,*BitreeBitree;lchilddatarchildData Structure
32、Data StructurePage 362023-1-10ABCDEFG AB C D E F G在在n n个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1个空指针域个空指针域。Data StructureData StructurePage 372023-1-10q 三叉链表三叉链表v结点包括结点包括数据域，左子树指针域、双亲域和右子树指针域数据域，左子树指针域、双亲域和右子树指针域。lchilddataparentrchildv三叉链表的存储表示三叉链表的存储表示typedef struct TriTNodetypedef struct TriTNodeTElemTypeTEle
33、mType datadata;struct TriTNodestruct TriTNode *lchild,lchild,*rchildrchild,*parentparent;TriTNode TriTNode,*TritreeTritree;Data StructureData StructurePage 382023-1-10 A B C D E F GABCDEFGData StructureData StructurePage 392023-1-106.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 遍历是树结构的一种常用的、重要的运算，是树的其遍历是树结构的一种常用的、重
34、要的运算，是树的其它运算的基础。它运算的基础。Data StructureData StructurePage 402023-1-10q 遍历遍历v按一定的按一定的规律规律，走遍走遍二叉树的二叉树的每个结点每个结点，使每个，使每个结点被访问一结点被访问一次，且只被访问一次次，且只被访问一次。v遍历方式遍历方式按根、左子树、右子树三个部分进行访问；按根、左子树、右子树三个部分进行访问；按层次访问；按层次访问；遍历的过程就是把非线性结构的二叉树中的结点排成一个遍历的过程就是把非线性结构的二叉树中的结点排成一个线性序列的过程。线性序列的过程。Data StructureData StructureP
35、age 412023-1-10q 设设D D表示根结点，表示根结点，L L表示左子树，表示左子树，R R表示右子树，则对这三表示右子树，则对这三个部分进行访问的组合共有个部分进行访问的组合共有6 6种，种，vDLRDLRvDRLDRLvLDRLDRvLRDLRDvRDLRDLvRLDRLDq 若限定先左后右，则只有若限定先左后右，则只有DLRDLR，LDRLDR，LRDLRD三种，分别称为三种，分别称为先序遍历，中序遍历，后序遍历。先序遍历，中序遍历，后序遍历。Data StructureData StructurePage 422023-1-10q 若二叉树为空，则空操作；否则若二叉树为空，
36、则空操作；否则v访问根结点：访问根结点：v先序遍历左子树；先序遍历左子树；v先序遍历右子树。先序遍历右子树。Data StructureData StructurePage 432023-1-10ADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D CA B D CData StructureData StructurePage 442023-1-10Status PreOrderTraverse(BiTree TStatus PreOrderTraverse(BiTree T，Status(Status(*visit)(TElemTypevisit)
37、(TElemType e)e)/采用二叉链表存储结构，采用二叉链表存储结构，visitvisit是对元素操作的应用函数，是对元素操作的应用函数，/先序遍历二叉树先序遍历二叉树T T的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数visitvisit。/最简单的最简单的visitvisit函数是输出元素的值。函数是输出元素的值。if(T)if(T)visit(T-data)visit(T-data)；PreOrderTraverse(T-lchildPreOrderTraverse(T-lchild,visit),visit)；PreOrderTraverse(T-rchil
38、dPreOrderTraverse(T-rchild,visit);,visit);/if/if/PreOrderTraverse/PreOrderTraverseData StructureData StructurePage 452023-1-10ABCDGEFH先序遍历：先序遍历：A A B B D D G G C C E E F F H HData StructureData StructurePage 462023-1-10q 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则v中序遍历左子树；中序遍历左子树；v访问根结点；访问根结点；v中序遍历右子树。中序遍历右子树。Data
39、 StructureData StructurePage 472023-1-10ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A CB D A CData StructureData StructurePage 482023-1-10Status InOrderTraverse(BiTree TStatus InOrderTraverse(BiTree T，Status(Status(*visit)(TElemTypevisit)(TElemType e)e)/采用二叉链表存储结构，采用二叉链表存储结构，visitvisit是对元素操作的应用函数，
40、是对元素操作的应用函数，/中序遍历二叉树中序遍历二叉树T T的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数visitvisit。/最简单的最简单的visitvisit函数是输出元素的值。函数是输出元素的值。if(T)if(T)InOrderTraverse(T-lchildInOrderTraverse(T-lchild,visit),visit)；visit(T-data)visit(T-data)；InOrderTraverse(T-rchildInOrderTraverse(T-rchild,visit),visit)；/if/if/InOrderTraverse/
41、InOrderTraverseData StructureData StructurePage 492023-1-10D GBAECH中序遍历：中序遍历：ABCDGEFHFData StructureData StructurePage 502023-1-10q若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则v后序遍历左子树；后序遍历左子树；v后序遍历右子树；后序遍历右子树；v访问根结点。访问根结点。Data StructureData StructurePage 512023-1-10ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列：D B C AD
42、 B C ABData StructureData StructurePage 522023-1-10ABCDGEFH后序遍历：后序遍历：C CG GF FD DH HB B E EA AData StructureData StructurePage 532023-1-10Status PostOrderTraverse(BiTree TStatus PostOrderTraverse(BiTree T，Status(Status(*visit)(TElemTypevisit)(TElemType e)e)/采用二叉链表存储结构，采用二叉链表存储结构，visitvisit是对元素操作的应用函
43、数，是对元素操作的应用函数，/先序遍历二叉树先序遍历二叉树T T的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数visitvisit。/最简单的最简单的visitvisit函数是输出元素的值。函数是输出元素的值。if(T)if(T)PostOrderTraverse(T-lchildPostOrderTraverse(T-lchild,visit);,visit);PostOrderTraverse(T-rchild PostOrderTraverse(T-rchild,visit);,visit);visit(T-data);visit(T-data);/if/if/In
44、OrderTraverse/InOrderTraverseData StructureData StructurePage 542023-1-10相同点：相同点：如果把访问根结点这个如果把访问根结点这个不涉及递归的语句抛开，则不涉及递归的语句抛开，则三个递归算法走过的路线是三个递归算法走过的路线是一样的。一样的。Data StructureData StructurePage 552023-1-10不同点：不同点：v 前序遍历是每进入一层递前序遍历是每进入一层递 归调用时归调用时先访问根结点先访问根结点，然后再依次向它的左、右然后再依次向它的左、右 子树执行递归调用；子树执行递归调用；v 中序
45、遍历是在执行完中序遍历是在执行完左子左子 树递归调用后再访问根结树递归调用后再访问根结 点点，然后向它的右子树递，然后向它的右子树递 归调用；归调用；v 后序遍历则是在从后序遍历则是在从右子树右子树 递归调用退出后访问根结递归调用退出后访问根结 点点。Data StructureData StructurePage 562023-1-10q 算法思想：算法思想：对二叉树对二叉树“遍历遍历”一遍，并在遍历过程中对一遍，并在遍历过程中对“叶子结点计叶子结点计数数”即可。为了在遍历的同时进行计数，在算法的参数中设即可。为了在遍历的同时进行计数，在算法的参数中设 一个一个“计数器计数器”。这个遍历的次
46、序可以随意，即先序或中。这个遍历的次序可以随意，即先序或中 序或后序均可。序或后序均可。void CountLeaf(BiTree T,intvoid CountLeaf(BiTree T,int&count)&count)/先序遍历二叉树，以先序遍历二叉树，以 count count 返回二叉树中叶子结点的数目返回二叉树中叶子结点的数目 if(T)if(T)if(!T-Lchild)&(!T-Rchild if(!T-Lchild)&(!T-Rchild)count+;count+;CountLeaf(T-Lchild CountLeaf(T-Lchild,count);,count);Co
47、untLeaf(T-Rchild CountLeaf(T-Rchild,count);,count);/if/if/CountLeaf/CountLeafData StructureData StructurePage 572023-1-10q 算法思想算法思想：深度为树中叶子结点所在层次的最大值。：深度为树中叶子结点所在层次的最大值。结点的层次需从根结点起递推，根结点为第一层。结点的层次需从根结点起递推，根结点为第一层。需要在先序遍历二叉树的过程中求每个结点的层次数，并需要在先序遍历二叉树的过程中求每个结点的层次数，并 将其中的最大值设为二叉树的深度。将其中的最大值设为二叉树的深度。算法一：
48、算法一：void BiTreeDepth(BiTree T,int level,intvoid BiTreeDepth(BiTree T,int level,int&depth)&depth)/T/T指向二叉树的根，指向二叉树的根，level level 为为 T T 所指结点所在层次，所指结点所在层次，/其初值为其初值为1 1，depth depth 为当前求得的最大层次为当前求得的最大层次,其初值为其初值为0 0 if(T)if(T)if(leveldepth)depth=level;if(leveldepth)depth=level;BiTreeDepth(T-Lchild BiTree
49、Depth(T-Lchild,level+1,depth);,level+1,depth);BiTreeDepth(T-Rchild BiTreeDepth(T-Rchild,level+1,depth);,level+1,depth);/if/if/BiTreeDepth/BiTreeDepthData StructureData StructurePage 582023-1-10Data StructureData StructurePage 592023-1-10算法二：算法二：int depth(Bitree T)if(T=NULL)return 0;else h1=depth(T-l
50、child);h2=depth(T-rchild);return max(h1,h2)+1;Data StructureData StructurePage 602023-1-10q 问题描述问题描述v假设给定一个和二叉树中数据元素有相同类型的值，在已知二叉树假设给定一个和二叉树中数据元素有相同类型的值，在已知二叉树中进行中进行查找查找，若，若存在和给定值相同的数据元素存在和给定值相同的数据元素，则，则返回返回函数值为函数值为 TRUETRUE，并用引用参数，并用引用参数返回指向该结点的指针返回指向该结点的指针；否则返回否则返回函数值为函数值为 FALSEFALSE。q 算法的基本思想为：算法
