敦案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 目 录 6.1树的定义和基本术语 0 6.2二叉树.… 6.2.1二叉树的定义 6.2.2二叉树的性质 3 6.2.3二叉树的存储结构.. 4 6.3树和森林.. 5 6.4二叉树的先中后序遍历算法. 6 6.5先后引中序遍历的应用扩展 。,。。 8 6.5.1基于先序遍历的二叉树（二叉链的创建 8 6.5.2统计二叉树中叶子结点的数目8 6.5.3求二叉树的高度 .9 6.5.4释放二叉树的所有结点空间. 10 6.5.5删除并释放二叉树中以元素值为x的结点作为根的各子树 11 65.6求位于二叉树先序序列中第k个位置的结点的值12 6.5.7线索二叉树12 6.5.8树和森林的遍历14 6.6二叉树的层次遍历… ,。,。。。,,,,,,,,。,。。,。,。,。,,,。, 6.7判断一棵二叉树是否为完全二叉树 。,,,,,,,,,, 6.8哈夫曼树及其应用 18 6.8.1最优二叉树（哈夫曼树） .18 6.8.2哈夫曼编码 18 6.9遍历二叉树的非递归算法 .19 6.9.1先序非递归算法 .19 6.9.2中序非递归算法 .20 6.9.3后序非递归算法 .20 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第0页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 0 页 第六章 树和二叉树 基本概念、遍历算法及其应用 目 录 6.1 树的定义和基本术语.................................................................................................0 6.2 二叉树......................................................................................................................1 6.2.1 二叉树的定义..................................................................................................1 6.2.2 二叉树的性质..................................................................................................3 6.2.3 二叉树的存储结构...........................................................................................4 6.3 树和森林..................................................................................................................5 6.4 二叉树的先|中|后序遍历算法.....................................................................................6 6.5 先|后|中序遍历的应用扩展........................................................................................8 6.5.1 基于先序遍历的二叉树(二叉链)的创建............................................................8 6.5.2 统计二叉树中叶子结点的数目.........................................................................8 6.5.3 求二叉树的高度..............................................................................................9 6.5.4 释放二叉树的所有结点空间...........................................................................10 6.5.5 删除并释放二叉树中以元素值为x的结点作为根的各子树............................... 11 6.5.6 求位于二叉树先序序列中第k个位置的结点的值.............................................12 6.5.7 线索二叉树...................................................................................................12 6.5.8 树和森林的遍历............................................................................................14 6.6 二叉树的层次遍历..................................................................................................15 6.7 判断一棵二叉树是否为完全二叉树..........................................................................16 6.8 哈夫曼树及其应用..................................................................................................18 6.8.1 最优二叉树(哈夫曼树)...................................................................................18 6.8.2 哈夫曼编码...................................................................................................18 6.9 遍历二叉树的非递归算法........................................................................................19 6.9.1 先序非递归算法............................................................................................19 6.9.2 中序非递归算法............................................................................................20 6.9.3 后序非递归算法............................................................................................20
敦案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 第6章二叉树和树 6.1树的定义和基本术语 1、树的递归定义 1)结点数n=0时，是空树 2)结点数n>0时 一有且仅有一个根结点、m个互不相交的有限结点集一一m棵子树 2、基本术语 结点：叶子（终端结点）、根、内部结点（非终端结点、分支结点）： 树的规模：结点的度、树的度、结点的层次、树的高度（深度） 结点间的关系：双亲(1)一孩子(m),祖先一子孙，兄弟，堂兄弟 兄弟间是否存在次序：无序树、有序树 去掉根结点 非空树 森林 引入一个根结点 3、树的抽象数据类型定义 树特有的操作： 查找：双亲、最左的孩子、右兄弟 结点的度不定，给出这两种操作可以查找到一个结点的全部孩子 插入、删除：孩子 遍历：存在一对多的关系，给出一种有规律的方法遍历（有且仅访问一次）树中的结点 ADT Tree{ 数据对象：D={ala∈ElemSet,i=l,2,…,n,n≥0) 数据关系：若D为空集，则称为空树： 若D仅含一个数据元素，则R为空集，否则R=H田，H是如下二元 关系： (I)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱： (2)若D-{root;≠④，则存在D-{root}的一个划分D1,D2,,Dm(m>0) (D:表示构成第i棵子树的结点集，对任意j≠k(1≤j,k≤m)有 D,∩Dk=心，且对任意的i(1≤i≤m),唯一存在数据元素：∈D,有4oot, x>∈H(H表示结点之间的父子关系， (3)对应于D{root)的划分，H-{oot,x1>,…,}有唯一的一 个划分H,H2,,Hm(>0)(H:表示第i棵子树中的父子关系)对任 意j≠k1≤j,k≤m)有H∩H=中，且对任意i1≤i≤m),H是D:上的 二元关系，(D,{H})是一棵符合本定义的树，称为根root的子树。 基本操作： InitTree(&T) 操作结果：构造空树T Destroy Tree(&T) 初始条件：树T已存在 操作结果：销毁树T Clear Tree(&T) 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第0页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 0 页 第六章 树和二叉树 基本概念、遍历算法及其应用 第6章 二叉树和树 6.1 树的定义和基本术语 1、树的递归定义 1）结点数 n=0 时，是空树 2）结点数 n>0 时 有且仅有一个根结点、m 个互不相交的有限结点集——m 棵子树 2、基本术语 结点： 叶子(终端结点)、根、内部结点（非终端结点、分支结点）； 树的规模：结点的度、树的度、结点的层次、树的高度(深度) 结点间的关系：双亲(1)—孩子(m)，祖先—子孙，兄弟，堂兄弟 兄弟间是否存在次序：无序树、有序树 去掉根结点 非空树 森林 引入一个根结点 3、树的抽象数据类型定义 树特有的操作： 查找：双亲、最左的孩子、右兄弟 结点的度不定，给出这两种操作可以查找到一个结点的全部孩子 插入、删除：孩子 遍历：存在一对多的关系，给出一种有规律的方法遍历(有且仅访问一次)树中的结点 ADT Tree{ 数据对象：D={ai | ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：若 D 为空集，则称为空树； 若 D 仅含一个数据元素，则 R 为空集，否则 R={H}，H 是如下二元 关系： (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) 若D-{root}≠Ф，则存在D-{root}的一个划分D1, D2, …, Dm (m>0) （Di 表示构成第 i 棵子树的结点集），对任意 j≠k (1≤j, k≤m) 有 Dj∩Dk=Ф，且对任意的i (1≤i≤m)，唯一存在数据元素xi∈Di, 有∈H（H 表示结点之间的父子关系）； (3) 对应于 D-{root}的划分，H-{,…, }有唯一的一 个划分 H1, H2, …, Hm(m>0)（Hi 表示第 i 棵子树中的父子关系），对任 意 j≠k(1≤j,k≤m)有 Hj∩Hk=Ф，且对任意 i(1≤i≤m)，Hi 是 Di 上的 二元关系，(Di, {Hi})是一棵符合本定义的树，称为根 root 的子树。 基本操作： InitTree(&T) 操作结果：构造空树 T DestroyTree(&T) 初始条件：树 T 已存在 操作结果：销毁树 T ClearTree(&T)
教案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 初始条件：树T已存在 操作结果：将树T清为空树 TreeEmpty(T) 初始条件：树T己存在 操作结果：若T为空树，则返回TRUE,否则返回FALSE TreeDepth(T) 初始条件：树T已存在 操作结果：返回树T的深度 Root(T) 初始条件：树T已存在 操作结果：返回T的根 Value(T,cur e) 初始条件：树T己存在，cure是T中某个结点 操作结果：返回cure的值 Assign(T,&cur_e,value) 初始条件：树T已存在，cure是T中某个结点 操作结果：结点cure赋值为value Parent(T,cur_e) 初始条件：树T已存在，cure是T中某个结点 操作结果：若cure是T的非根结点，则返回它的双亲，否则函数值为 “空” LeftChild(T,cur_e) 初始条件：树T己存在，cure是T中某个结点 操作结果：若cure是T的非叶子结点，则返回它的最左孩子，否则返 回“空” RightSibling(T,cur_e) 初始条件：树T已存在，cure是T中某个结点 操作结果：若cure有右兄弟，则返回它的右兄弟，否则返回“空” InsertChild(&T,p,i,c) 初始条件：树T已存在，p指向T中某个结点，1≤≤p所指结点的度 +1,非空树c与T不相交 操作结果：插入c为T中p所指结点的第i棵子树。 DeleteChild(&T,p,i) 初始条件：树T己存在，P指向T中某个结点，1≤≤p所指结点的度 操作结果：删除T中p所指结点的第i棵子树。 TraverseTree(T.visit()) 初始条件：树T已存在，visit是对结点操作的应用函数 操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。 一旦visit()失败，则操作失败 ADT Tree 6.2二叉树 一般树的度不定，直接考虑其操作比较困难，故首先考虑度为二的树。这里引入二叉树。 6.2.1二叉树的定义 1、二叉树的特殊性 ·0≤度≤2 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第1页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 1 页 第六章 树和二叉树 基本概念、遍历算法及其应用 初始条件：树 T 已存在 操作结果：将树 T 清为空树 TreeEmpty(T) 初始条件：树 T 已存在 操作结果：若 T 为空树，则返回 TRUE，否则返回 FALSE TreeDepth(T) 初始条件：树 T 已存在 操作结果：返回树 T 的深度 Root(T) 初始条件：树 T 已存在 操作结果：返回 T 的根 Value(T, cur_e) 初始条件：树 T 已存在，cur_e 是 T 中某个结点 操作结果：返回 cur_e 的值 Assign(T, &cur_e, value) 初始条件：树 T 已存在，cur_e 是 T 中某个结点 操作结果：结点 cur_e 赋值为 value Parent(T, cur_e) 初始条件：树 T 已存在，cur_e 是 T 中某个结点 操作结果：若 cur_e 是 T 的非根结点，则返回它的双亲，否则函数值为 “空” LeftChild(T, cur_e) 初始条件：树 T 已存在，cur_e 是 T 中某个结点 操作结果：若 cur_e 是 T 的非叶子结点，则返回它的最左孩子，否则返 回“空” RightSibling(T, cur_e) 初始条件：树 T 已存在，cur_e 是 T 中某个结点 操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回“空” InsertChild(&T, p, i, c) 初始条件：树 T 已存在，p 指向 T 中某个结点，1≤i≤p 所指结点的度 +1，非空树 c 与 T 不相交 操作结果：插入 c 为 T 中 p 所指结点的第 i 棵子树。 DeleteChild(&T, p, i) 初始条件：树 T 已存在,p 指向 T 中某个结点，1≤i≤p 所指结点的度 操作结果：删除 T 中 p 所指结点的第 i 棵子树。 TraverseTree(T, visit( ) ) 初始条件：树 T 已存在，visit 是对结点操作的应用函数 操作结果：按某种次序对 T 的每个结点调用函数 visit( )一次且至多一次。 一旦 visit( )失败，则操作失败 }ADT Tree 6.2 二叉树 一般树的度不定，直接考虑其操作比较困难，故首先考虑度为二的树。这里引入二叉树。 6.2.1 二叉树的定义 1、二叉树的特殊性 ·0≤度≤2
第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 ·子树有左右之分（子树的个数=1或2时） 注意：0≤度≤2的有序树≠二叉树 当某个结点只有一棵子树时，不存在序的概念 2、二叉树的抽象数据类型定义 二叉树相对树的特殊性： 最左的孩子、右兄弟◆左孩子、右孩子 遍历的规律性：L(左子树)、D(根)、R(右子树)的排列上 限定为L在R前访问（有对称关系的，只须考虑其中的一种） ADT BinaryTree{ 数据对象：D={ala∈ElemSet,.i=l,2,…,n,n≥0} 数据关系：若D为空集，则称为空树： 若D仅含一个数据元素，则R为空集，否则R={H,H是如下二元 关系： (I)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱： (2)若D-{root}≠①，则存在D-{root;的一个划分DL,DR(左、右子 树的结点集，且DL∩DR=中： (3)若DL≠中，则DL中存在唯一元素XL,有∈H(H表示结 点之间的父子关系)且存在DL上的关系HLCH:若DR卡心，则Dr 中存在唯一元素R,有∈H,且存在DR上的关系HRCH: (3)(DL,H)是一棵符合本定义的二叉树，称为根的左子树：(D,HR) 是一棵符合本定义的二叉树，称为根的右子树。 基本操作： InitBiTree(&T) 操作结果：构造空二叉树T Destroy BiTree(&T) 初始条件：二叉树T已存在 操作结果：销毁二叉树T ClearBiTree(&T) 初始条件：二叉树T已存在 操作结果：将二叉树T清为空树 BiTreeEmpty(T) 初始条件：二叉树T己存在 操作结果：若T为空二叉树，则返回TRUE,否则返回FALSE BiTreeDepth(T) 初始条件： 二叉树T已存在 操作结果：返回二叉树T的深度 Root(T) 初始条件：二叉树T已存在 操作结果：返回T的根 Value(T,cur_e) 初始条件： 二叉树T己存在，cure是T中某个结点 操作结果：返回cure的值 Assign(T,&cur_e,value) 初始条件：二叉树T已存在，cure是T中某个结点 操作结果：结点cure赋值为value Parent(T,cur_e) 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第2页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 2 页 第六章 树和二叉树 基本概念、遍历算法及其应用 ·子树有左右之分（子树的个数 = 1 或 2 时） 注意：0≤度≤2 的有序树≠二叉树 当某个结点只有一棵子树时，不存在序的概念 2、二叉树的抽象数据类型定义 二叉树相对树的特殊性： 最左的孩子、右兄弟 左孩子、右孩子 遍历的规律性： L(左子树)、D(根)、R(右子树)的排列上 限定为 L 在 R 前访问(有对称关系的，只须考虑其中的一种) ADT BinaryTree{ 数据对象：D={ai | ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：若 D 为空集，则称为空树； 若 D 仅含一个数据元素，则 R 为空集，否则 R={H}，H 是如下二元 关系： (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) 若 D-{root}≠Ф，则存在 D-{root}的一个划分 DL, DR（左、右子 树的结点集），且 DL∩DR=Ф； (3) 若 DL≠Ф，则 DL 中存在唯一元素 xL, 有∈H（H 表示结 点之间的父子关系），且存在 DL 上的关系 HL H；若 DR≠Ф，则 DR 中存在唯一元素 xR, 有∈H，且存在 DR上的关系 HR H； (3) (DL, {HL})是一棵符合本定义的二叉树，称为根的左子树；(DR, {HR}) 是一棵符合本定义的二叉树，称为根的右子树。 基本操作： InitBiTree(&T) 操作结果：构造空二叉树 T DestroyBiTree(&T) 初始条件：二叉树 T 已存在 操作结果：销毁二叉树 T ClearBiTree(&T) 初始条件：二叉树 T 已存在 操作结果：将二叉树 T 清为空树 BiTreeEmpty(T) 初始条件：二叉树 T 已存在 操作结果：若 T 为空二叉树，则返回 TRUE，否则返回 FALSE BiTreeDepth(T) 初始条件：二叉树 T 已存在 操作结果：返回二叉树 T 的深度 Root(T) 初始条件：二叉树 T 已存在 操作结果：返回 T 的根 Value(T, cur_e) 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：返回 cur_e 的值 Assign(T, &cur_e, value) 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：结点 cur_e 赋值为 value Parent(T, cur_e)
教裂 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 初始条件：二叉树T已存在，cure是T中某个结点 操作结果：若cure是T的非根结点，则返回它的双亲，否则函数值为 “空” LeftChild(T,cur_e) 初始条件：二叉树T己存在，cure是T中某个结点 操作结果：若cure是T的非叶子结点，则返回它的左孩子，否则返回 “空” RightChild(T,cur_e) 初始条件：二叉树T已存在，cure是T中某个结点 操作结果：若cure有右孩子，则返回它的右孩子，否则返回“空” LeftSibling(T,cur e) 初始条件：二叉树T已存在，cure是T中某个结点 操作结果：返回cure的左兄弟，若cure是T的左孩子或无左兄弟， 则返回“空” RightSibling(T,cur_e) 初始条件：二叉树T已存在，cure是T中某个结点 操作结果：返回cure的右兄弟，若cure是T的右孩子或无右兄弟， 则返回“空” InsertChild(&T,p,LR,c) 初始条件：二叉树T已存在，p指向T中某个结点，LR为0或1，非空 二叉树c与T不相交 操作结果：插入c为T中p所指结点的左或右子树。p所指结点的原有 左或右子树则成为c的右子树 DeleteChild(&T,p,LR) 初始条件：二叉树T已存在，p指向T中某个结点，LR为0或1 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。 PreOrderTraverse(T,visit()) 初始条件：二叉树T已存在，visit是对结点操作的应用函数 操作结果：先序遍历T,对每个结点调用函数visit()一次且仅一次。一旦 visit()失败，则操作失败 InOrderTraverse(T,visit()) 初始条件：二叉树T己存在，visit是对结点操作的应用函数 操作结果：中序遍历T,对每个结点调用函数visit()一次且仅一次。一 旦visit()失败，则操作失败 PostOrderTraverse(T,visit()) 初始条件：二叉树T已存在，visit是对结点操作的应用函数 操作结果：后序遍历T,对每个结点调用函数vist()）一次且仅一次。一 旦visit()失败，则操作失败 LevelOrderTraverse(T,visit()) 初始条件：二叉树T已存在，visit是对结点操作的应用函数 操作结果：层序遍历T,对每个结点调用函数vist()一次且仅一次。一 旦visit()失败，则操作失败 ADT BinaryTree 6.2.2二叉树的性质 1、性质1：第i层至多有2-1个结点（由每个结点最多只有2个孩子推出) 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第3页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 3 页 第六章 树和二叉树 基本概念、遍历算法及其应用 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：若 cur_e 是 T 的非根结点，则返回它的双亲，否则函数值为 “空” LeftChild(T, cur_e) 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：若 cur_e 是 T 的非叶子结点，则返回它的左孩子，否则返回 “空” RightChild(T, cur_e) 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：若 cur_e 有右孩子，则返回它的右孩子，否则返回“空” LeftSibling(T, cur_e) 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：返回 cur_e 的左兄弟，若 cur_e 是 T 的左孩子或无左兄弟， 则返回“空” RightSibling(T, cur_e) 初始条件：二叉树 T 已存在，cur_e 是 T 中某个结点 操作结果：返回 cur_e 的右兄弟，若 cur_e 是 T 的右孩子或无右兄弟， 则返回“空” InsertChild(&T, p, LR, c) 初始条件：二叉树 T 已存在，p 指向 T 中某个结点，LR 为 0 或 1，非空 二叉树 c 与 T 不相交 操作结果：插入 c 为 T 中 p 所指结点的左或右子树。p 所指结点的原有 左或右子树则成为 c 的右子树 DeleteChild(&T, p, LR) 初始条件：二叉树 T 已存在，p 指向 T 中某个结点，LR 为 0 或 1 操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。 PreOrderTraverse( T, visit( )) 初始条件：二叉树 T 已存在，visit 是对结点操作的应用函数 操作结果：先序遍历 T，对每个结点调用函数 visit()一次且仅一次。一旦 visit()失败，则操作失败 InOrderTraverse( T, visit( )) 初始条件：二叉树 T 已存在，visit 是对结点操作的应用函数 操作结果：中序遍历 T，对每个结点调用函数 visit( )一次且仅一次。一 旦 visit( )失败，则操作失败 PostOrderTraverse( T, visit( )) 初始条件：二叉树 T 已存在，visit 是对结点操作的应用函数 操作结果：后序遍历 T，对每个结点调用函数 visit( )一次且仅一次。一 旦 visit( )失败，则操作失败 LevelOrderTraverse( T, visit( )) 初始条件：二叉树 T 已存在，visit 是对结点操作的应用函数 操作结果：层序遍历 T，对每个结点调用函数 visit( )一次且仅一次。一 旦 visit( )失败，则操作失败 }ADT BinaryTree 6.2.2 二叉树的性质 1、性质 1：第 i 层至多有 2 i-1 个结点（由每个结点最多只有 2 个孩子推出）
敦案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 2、性质2：深度为k的二叉树至多有2-1个结点（由性质1，将各层最多的结点数累加，再 结合等比数列的求和得出) 思考：深度为k的二叉树至少有多少个结点？(k个)深度为k的b叉树至多/至少有多少 个结点？((bk1)/b-1), 3、性质3：no=2+1(n:表示二叉树中度为i的结点个数) 从两个角度考虑：二叉树中结点的构成（根据度）n=+1+m 二叉树中充当其余结点的孩子的结点数-1（去掉根）=n1+2×2 满二叉树：达到性质1,2中所述的最大值情况 完全二叉树：去掉最下一层的结点，其余结点形成一棵满二叉树；叶子集中在最下2层（或 1层)，最下一层的结点总是尽可能地占满左边的位置 4性质4：具有n个结点的完全二叉树的深度为6g,m+1 5、性质5：结点间的编号关系 考虑二叉树的顺序映像问题，寻求一种将二叉树映像为向量的方法： 对完全二叉树从上至下，从左至右，从根开始依次编号(1.)。 孩子编号 双亲编号 求双亲 i/2>0) 求孩子 左：2*i() i-1>0) 求右兄弟 +1(0) 求右兄弟 p+1(<n+1) p(p-1)%k≠0) 6.2.3二叉树的存储结构 1、二叉树的顺序存储结构 1)方法 二叉树→补虚结点形成完全二叉树→自上而下、自左至右存储 2)类型定义 #define MAX TREE SIZE 100 *二叉树的最大结点数/ typedef Elem'Type SqBiTree[MAX TREE SIZE];/体0号单元存储根结点 */ 必须引入特殊符号表示虚结点的值 上述类型定义的缺陷：未指明实际二叉树占用的长度，可改进为： typedef struct{ ElemType elem[MAX TREE SIZE+1];/体1号单元存储根结点/ 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第4页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 4 页 第六章 树和二叉树 基本概念、遍历算法及其应用 2、性质 2：深度为 k 的二叉树至多有 2 k-1 个结点（由性质 1，将各层最多的结点数累加，再 结合等比数列的求和得出） 思考：深度为 k 的二叉树至少有多少个结点？( k 个 ) 深度为 k 的 b 叉树至多/至少有多少 个结点？( (bk-1)/(b-1)，k) 3、性质 3：n0=n2+1 (ni 表示二叉树中度为 i 的结点个数) 从两个角度考虑：二叉树中结点的构成（根据度）n = n0 + n1 + n2 二叉树中充当其余结点的孩子的结点数 n-1(去掉根) = n1+2×n2 满二叉树：达到性质 1,2 中所述的最大值情况 完全二叉树：去掉最下一层的结点，其余结点形成一棵满二叉树；叶子集中在最下 2 层(或 1 层)，最下一层的结点总是尽可能地占满左边的位置 4、性质 4：具有 n 个结点的完全二叉树的深度为 5、性质 5：结点间的编号关系 考虑二叉树的顺序映像问题，寻求一种将二叉树映像为向量的方法： 对完全二叉树从上至下，从左至右，从根开始依次编号(1..n)。 孩子编号 双亲编号 求双亲 i i/2(>0) 求孩子 左：2*i(1) i-1(>0) 求右兄弟 i+1(0) 求右兄弟 p+1(<n+1) p((p-1)%k≠0) 6.2.3 二叉树的存储结构 1、二叉树的顺序存储结构 1) 方法 二叉树→补虚结点形成完全二叉树→自上而下、自左至右存储 2) 类型定义 #define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */ typedef ElemType SqBiTree[MAX_TREE_SIZE]; /* 0 号单元存储根结点 */ 必须引入特殊符号表示虚结点的值 上述类型定义的缺陷：未指明实际二叉树占用的长度，可改进为： typedef struct{ ElemType elem[MAX_TREE_SIZE+1]; /* 1 号单元存储根结点 */ log2 n +1
敦案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 int length; }SqBiTree: 3)不足：空间的利用率不高 如：若深度为5且仅含有5个结点的二叉树，必须要占用2425-1空间。 2、二叉树的链式存储结构 parent 1)引入辅助空间表示结点间的相对关系 双亲(1)一一孩子(2)（如右图） data Ichild data rchild parent Ichild data rchild 二叉链表 三叉链表 lchild rchild 若需要找指定结点的双亲，则用三叉链表可在O(1)时间内获得某结点的双亲；而用二 叉链表则需从根开始，采用一定的巡查方法进行搜索。 2) 二叉链表的类型定义 typedef struct BiTNode ElemType data: struct BiTNode *lchild,*rchild; /体左右孩子指针*/ }BiTNode,*BiTree; 3)二叉链表的链域 若有n个结点，则共有2n个链域：其中n-1不为空，指向孩子。 4) 二叉树（链式存储）的创建 输入序列与二叉树的映射关系 (1)完全二叉树的顺序映射 通过补虚结点，将一般的二叉树转变成完全二叉树，再对该完全二叉树的结点按 自上而下、自左至右进行输入。 (2)二叉树的先序遍历 通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍 历进行输入。 (3)二叉树的两种遍历序列：先序+中序，后序+中序 6.3树和森林 1、树的存储结构 1)双亲表示法 针对每一结点，附设指示其双亲位置的数据域。采用顺序表（非顺序映像）。 #define MAX TREE SIZE 100 体树的最大结点数 typedef struct PTNode ElemType data, int parent; PTNode: typedef struct PTNode nodes[MAX TREE_SIZE]; int n; 体结点数 */ PTree; 2)孩子表示法 各结点的孩子数是不定的，用顺序表表示必须给出树的度的最大值，以及每一结点的 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第5页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 5 页 第六章 树和二叉树 基本概念、遍历算法及其应用 int length; }SqBiTree; 3) 不足：空间的利用率不高 如：若深度为 5 且仅含有 5 个结点的二叉树，必须要占用 2 4~2 5-1 空间。 2、二叉树的链式存储结构 1) 引入辅助空间表示结点间的相对关系 双亲(1)——孩子(2) (如右图) lchild data rchild parent lchild data rchild 二叉链表 三叉链表 若需要找指定结点的双亲，则用三叉链表可在 O(1)时间内获得某结点的双亲；而用二 叉链表则需从根开始，采用一定的巡查方法进行搜索。 2) 二叉链表的类型定义 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; /* 左右孩子指针 */ }BiTNode, *BiTree; 3) 二叉链表的链域 若有 n 个结点，则共有 2n 个链域；其中 n-1 不为空，指向孩子。 4) 二叉树(链式存储)的创建 输入序列与二叉树的映射关系 (1) 完全二叉树的顺序映射 通过补虚结点，将一般的二叉树转变成完全二叉树，再对该完全二叉树的结点按 自上而下、自左至右进行输入。 (2) 二叉树的先序遍历 通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍 历进行输入。 (3) 二叉树的两种遍历序列：先序+中序，后序+中序 6.3 树和森林 1、树的存储结构 1) 双亲表示法 针对每一结点，附设指示其双亲位置的数据域。采用顺序表（非顺序映像）。 #define MAX_TREE_SIZE 100 /* 树的最大结点数 */ typedef struct PTNode{ ElemType data; int parent; }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; /* 结点数 */ }PTree; 2) 孩子表示法 各结点的孩子数是不定的，用顺序表表示必须给出树的度的最大值，以及每一结点的 data parent lchild rchild
第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 实际度数，空间浪费大。故以链表存储每一结点的所有孩子的位置信息。 typedef struct CTNode /*孩子结点 利 int child; 体孩子结点的位置编号*/ struct CTNode *next; 体下一个孩子结点制 }*ChildPtr: typedef struct TElemType data; ChildPtr firstchild; /体孩子链表的头指针/ CTBox: typedef struct{ CTBox nodes[MAX TREE SIZE]; int n,r; /体结点数和根的位置/ }CTree; 3)孩子兄弟法 二叉链表表示。针对每一结点，引入其第一个孩子和下一个右兄弟的位置域。 typedef struct CSNode ElemType data struct CSNode *firstchild,*nextsibling; 体第一个孩子、下一个兄弟指针*/ CSNode.*CSTree: 2、森林与二叉树的转换 森林用孩子兄弟法表示，形成二叉链表，可以将它理解为一个二叉树的二叉链表： 二叉树用二叉链表表示，可以将该二叉链表理解为孩子兄弟链表，从而获得森林。 6.4二叉树的先中后序遍历算法 1、遍历 ·对于二叉树中的结点，有且仅访问一次 ·遍历的规律性：（左子树）、D(根)、R(右子树)的排列上 限定L在R前访问（有对称关系的，只须考虑其中的一种） ·先（根）序遍历 DLR ·中（根）序遍历 LDR ·后（根）序遍历 LRD 2、二叉树遍历的递归实现 遍历路径 二叉树的递归定义性质，决定了它的很多算法都可用递归实现， 遍历就是其中之一。 先序访问 对于二叉树的遍历，可以不去具体考虑各子问题（左子树、根、右 子树)的遍历结果是什么，而去考虑如何由各子问题的求解结果构成原 问题（二叉树）的遍历结果一一递归规律的确定。必须注意的是，当二 叉树小到一定程度，即空树时，应直接给出解答一一递归结束条件及 处理。 三种遍历的区别（右图）：所经过的搜索路线是相同的：只是访问中序访问)后序访问 结点的时机不同。每一结点在整个搜索路线中会经过3次（第一次进入到该结点、由左子树回 溯到该结点、由右子树回溯到该结点)，如在第一次遇到时就访问该结点，那么称之为先序：第 二次经过时访问为中序：第三次经过时访问则为后序。 1)先序遍历 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第6页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 6 页 第六章 树和二叉树 基本概念、遍历算法及其应用 实际度数，空间浪费大。故以链表存储每一结点的所有孩子的位置信息。 typedef struct CTNode{ /* 孩子结点 */ int child; /* 孩子结点的位置编号*/ struct CTNode *next; /* 下一个孩子结点 */ }*ChildPtr; typedef struct{ TElemType data; ChildPtr firstchild; /* 孩子链表的头指针 */ }CTBox; typedef struct{ CTBox nodes[MAX_TREE_SIZE]; int n, r; /* 结点数和根的位置 */ }CTree; 3) 孩子兄弟法 二叉链表表示。针对每一结点，引入其第一个孩子和下一个右兄弟的位置域。 typedef struct CSNode{ ElemType data; struct CSNode *firstchild, *nextsibling; /* 第一个孩子、下一个兄弟指针 */ }CSNode, *CSTree; 2、森林与二叉树的转换 森林用孩子兄弟法表示，形成二叉链表，可以将它理解为一个二叉树的二叉链表； 二叉树用二叉链表表示，可以将该二叉链表理解为孩子兄弟链表，从而获得森林。 6.4 二叉树的先|中|后序遍历算法 1、遍历 ·对于二叉树中的结点，有且仅访问一次 ·遍历的规律性：L(左子树)、D(根)、R(右子树)的排列上 限定 L 在 R 前访问(有对称关系的，只须考虑其中的一种) ·先(根)序遍历 DLR ·中(根)序遍历 LDR ·后(根)序遍历 LRD 2、二叉树遍历的递归实现 二叉树的递归定义性质，决定了它的很多算法都可用递归实现， 遍历就是其中之一。 对于二叉树的遍历，可以不去具体考虑各子问题(左子树、根、右 子树)的遍历结果是什么，而去考虑如何由各子问题的求解结果构成原 问题(二叉树)的遍历结果——递归规律的确定。必须注意的是，当二 叉树小到一定程度，即空树时，应直接给出解答——递归结束条件及 处理。 三种遍历的区别(右图)：所经过的搜索路线是相同的；只是访问 结点的时机不同。每一结点在整个搜索路线中会经过 3 次（第一次进入到该结点、由左子树回 溯到该结点、由右子树回溯到该结点），如在第一次遇到时就访问该结点，那么称之为先序；第 二次经过时访问为中序；第三次经过时访问则为后序。 1) 先序遍历 - * c a b 遍历路径 先序访问 中序访问 后序访问
教黎 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 Status PreOrderTraverse(BiTree T,Status(*Visit )(ElemType e)){ if(T!=NULL if Visit(T->data)) if PreOrderTraverse(T->lchild,Visit ) if(PreOrderTraverse(T->rchild,Visit ) return OK: return ERROR: } else return OK; 2)后序遍历 Status PostOrderTraverse(BiTree T,Status(*Visit )(ElemType e)){ if(T!=NULL) if(PostOrderTraverse(T->lchild,Visit ) if PostOrderTraverse(T->rchild,Visit)) if (Visit(T->data)) return OK; return ERROR: else return OK; 3)中序遍历 Status InOrderTraverse(BiTree T,Status(*Visit )(ElemType e)){ if(T!=NULL){ if(InOrderTraverse(T->lchild,Visit ) if Visit(T->data)) if(InOrderTraverse(T->rchild,Visit ) return OK; return ERROR: } else return OK; 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第7页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 7 页 第六章 树和二叉树 基本概念、遍历算法及其应用 Status PreOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) ){ if ( T != NULL ){ if ( Visit(T->data) ) if ( PreOrderTraverse( T->lchild, Visit ) ) if ( PreOrderTraverse( T->rchild, Visit ) ) return OK; return ERROR; } else return OK; } 2) 后序遍历 Status PostOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) ){ if ( T != NULL ){ if ( PostOrderTraverse( T->lchild, Visit ) ) if ( PostOrderTraverse( T->rchild, Visit ) ) if ( Visit(T->data) ) return OK; return ERROR; } else return OK; } 3) 中序遍历 Status InOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) ){ if ( T != NULL ){ if ( InOrderTraverse( T->lchild, Visit ) ) if ( Visit(T->data) ) if ( InOrderTraverse( T->rchild, Visit ) ) return OK; return ERROR; } else return OK; }
敦案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 6.5先后中序遍历的应用扩展 利用二叉树的遍历算法，适当修改访问结点操作的内容，可以得到求解许多问题的算法。 ◇二叉树的创建（基于先序遍历） 令二叉树的线索化 查找指定结点：在访问结点时，判断当前访问的结点是否是指定的结点，若是则返回 该结点位置，否则继续遍历： 查找位于某种遍历次序中的第k位的结点：遍历前，引入一计数器，用来统计已访问 过的结点数，初值为0在访问结点时，将该计数器增1，并看是否达到k,: 令求叶子结点的数目：遍历前，引入叶子结点计数器，初值为0：访问结点时，将该计 数器增1：遍历结束，则计数器中的值即为所求解： 令判断二叉树中是否仅包含有度为2和0的结点：访问结点时，判断该结点孩子的有无 情况，… 求指定结点的层次：孩子结点的层次比其双亲结点层次多一： ◇求二叉树的高度：二叉树的高度=max(左子树的高度，右子树的高度)+1 6.5.1基于先序遍历的二叉树（二叉链）的创建 【本例特征】 如何基于二叉树的先序、中序、后序遍历的递归算法进行问题求解？ 【思路】 先序遍历PreOrderTraverse 创建CreateBiTree 输入 二叉链表示的二叉树的头指针T 带虚结点的先序序列ch 输入的表现方式 参数 由输入设备输入scanf(&ch) 输出 对结点的访问结果 二叉链表示的二叉树的头指针T 输出的表现方式 由输出设备输出 变参 空树（递归结束）的 T==NULL ch一END DATA(表示虚结点的值) 条件及处理 (直接求解) 空 T=NULL 根结点的访问 T=(BiTree)malloc(sizeof(BiTNode ) (子问题直接求解) Visit(T->data T->data=ch 左子树 (使用递归调用的解) PreOrderTraverse(T->lchild CreateBiTree(T->Ichild 右子树 PreOrderTraverse(T->rchild) CreateBiTree(T->rchild (使用递归调用的解) 【算法】见《数据结构(C语言版)》P131算法6.4。 6.5.2统计二叉树中叶子结点的数目 【本例特征】 如何通过全局变量、变参、返回值三种渠道返回处理结果？ 【思路】 在遍历二叉树时，对一些特殊的结点（无左右孩子）进行计数。可以修改遍历算法的结点访 问操作为对特殊结点的判定和计数过程，需要注意的是计数器的处理方式。可以有以下几种计 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第8页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 8 页 第六章 树和二叉树 基本概念、遍历算法及其应用 6.5 先|后|中序遍历的应用扩展 利用二叉树的遍历算法，适当修改访问结点操作的内容，可以得到求解许多问题的算法。 二叉树的创建（基于先序遍历） 二叉树的线索化 查找指定结点：在访问结点时，判断当前访问的结点是否是指定的结点，若是则返回 该结点位置，否则继续遍历； 查找位于某种遍历次序中的第 k 位的结点：遍历前，引入一计数器，用来统计已访问 过的结点数，初值为 0；在访问结点时，将该计数器增 1，并看是否达到 k，……； 求叶子结点的数目：遍历前，引入叶子结点计数器，初值为 0；访问结点时，将该计 数器增 1；遍历结束，则计数器中的值即为所求解； 判断二叉树中是否仅包含有度为 2 和 0 的结点：访问结点时，判断该结点孩子的有无 情况，…… 求指定结点的层次：孩子结点的层次比其双亲结点层次多一； 求二叉树的高度：二叉树的高度 = max(左子树的高度, 右子树的高度) +1 6.5.1 基于先序遍历的二叉树(二叉链)的创建 【本例特征】 如何基于二叉树的先序、中序、后序遍历的递归算法进行问题求解？ 【思路】 先 序 遍 历 PreOrderTraverse 创 建 CreateBiTree 输入 二叉链表示的二叉树的头指针 T 带虚结点的先序序列 ch 输入的表现方式 参数 由输入设备输入 scanf( &ch ) 输出 对结点的访问结果 二叉链表示的二叉树的头指针 T 输出的表现方式 由输出设备输出 变参 空树（递归结束）的 条件及处理 (直接求解) T == NULL ch == END_DATA（表示虚结点的值） 空 T = NULL 根结点的访问 (子问题直接求解) Visit( T->data ) T = ( BiTree)malloc( sizeof( BiTNode )) T->data = ch 左子树 (使用递归调用的解) PreOrderTraverse( T->lchild ) CreateBiTree( T->lchild ) 右子树 (使用递归调用的解) PreOrderTraverse( T->rchild ) CreateBiTree( T->rchild ) 【算法】见《数据结构(C 语言版)》P131 算法 6.4。 6.5.2 统计二叉树中叶子结点的数目 【本例特征】 如何通过全局变量、变参、返回值三种渠道返回处理结果？ 【思路】 在遍历二叉树时，对一些特殊的结点(无左右孩子)进行计数。可以修改遍历算法的结点访 问操作为对特殊结点的判定和计数过程，需要注意的是计数器的处理方式。可以有以下几种计
