中国科学技术大学：《数据结构及其算法》课程教学资源（教案讲义）第6章树和二叉树.doc

程序设计——数据结构文档编号完成人张昱完成时间修改时间 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>,…,<root,xm>}有唯一的一个划分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, 有<root, xi>∈H（H 表示结点之间的父子关系）； (3) 对应于 D-{root}的划分，H-{<root, x1>,…, <root, xm>}有唯一的一个划分 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)

程序设计——数据结构文档编号完成人张昱完成时间修改时间 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,有<root,x>∈H(H表示结点之间的父子关系)且存在DL上的关系HLCH:若DR卡心，则Dr 中存在唯一元素R,有<rOot,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, 有<root, xL>∈H（H 表示结点之间的父子关系），且存在 DL 上的关系 HL H；若 DR≠Ф，则 DR 中存在唯一元素 xR, 有<root, 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 个孩子推出）

中国科学技术大学：《数据结构及其算法》课程教学资源（教案讲义）第6章 树和二叉树

中国科学技术大学：《数据结构及其算法》课程教学资源（教案讲义）第6章树和二叉树