数据结构 第6 章 树和二叉树.ppt

数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中1、树和森林的概念（树的定义、树的术语、性质、树和森林的概念（树的定义、树的术语、性质 及运算）；及运算）；2、二叉树的定义、性质及运算；、二叉树的定义、性质及运算；3、二叉树的存储结构（顺序、链式表示）；、二叉树的存储结构（顺序、链式表示）；4、遍历二叉树、遍历二叉树 5、树的存储结构；树、森林与二叉树的转换；遍、树的存储结构；树、森林与二叉树的转换；遍 历树；遍历森林历树；遍历森林 6、哈夫曼树、哈夫曼编码。、哈夫曼树、哈夫曼编码。教学内容教学内容 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中树型结构（非线性结构）树型结构（非线性结构）结点之间有分支结点之间有分支 具有层次关系具有层次关系 例例 自然界：树自然界：树 人类社会人类社会 家谱家谱 行政组织机构行政组织机构 计算机领域计算机领域 编译：用树表示源程序的语法结构编译：用树表示源程序的语法结构 数据库系统：用树组织信息数据库系统：用树组织信息 算法分析：用树描述执行过程算法分析：用树描述执行过程 国务院国务院 山东省山东省 北京市北京市 西藏自治区西藏自治区 济南市济南市 青岛市青岛市 威海市威海市 历下区历下区 市中区市中区 商河县商河县 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中6.1 树的定义和基本术语树的定义和基本术语 定义：定义：树树(Tree)是是 n(n0)个结点的有限集。个结点的有限集。若若 n=0，称称 为空树；为空树；若若 n 0，则则它满足如下两个条件：它满足如下两个条件：(1)有且仅有一个特定的称为有且仅有一个特定的称为根根根根(Root)的结点；的结点；(2)其余结点可分为其余结点可分为 m(m0)个互不相交的有限集个互不相交的有限集 T1,T2,T3,Tm，其中每一个集合本身又是一棵树，并称为其中每一个集合本身又是一棵树，并称为 根的根的子树子树(SubTree)。显然，树的定义是一个递归的定义。显然，树的定义是一个递归的定义。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中树的逻辑结构：树的逻辑结构：树的逻辑结构：树的逻辑结构：树中任一结点都可以有零个或多个直接后继结点树中任一结点都可以有零个或多个直接后继结点 但至多只能有一个直接前趋结点。但至多只能有一个直接前趋结点。T3 T2 T1 基本术语：基本术语：结点的结点的度：度：度：度：结点拥有的子树数。结点拥有的子树数。度度=0叶子叶子叶子叶子 终端结点终端结点终端结点终端结点 度度 0分支结点分支结点分支结点分支结点 非终端非终端非终端非终端 结点结点结点结点 根结点以根结点以 外的分支外的分支 结点称为结点称为 内部结点内部结点内部结点内部结点 树的树的度：度：度：度：树内各结点的度的最大值。树内各结点的度的最大值。双亲双亲 孩子孩子 兄弟兄弟 结点的结点的祖先：祖先：祖先：祖先：从根到该结点所经分支上的所有结点。从根到该结点所经分支上的所有结点。结点的结点的子孙：子孙：子孙：子孙：以某结点为根的子树中的任一结点。以某结点为根的子树中的任一结点。第第 1 层层 第第 2 层层 第第 3 层层 第第 4 层层 堂兄弟堂兄弟 双亲在同一层的结点双亲在同一层的结点 树的树的深度：深度：深度：深度：树中结点的最大层次。树中结点的最大层次。有序树：有序树：有序树：有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。树中结点的各子树从左至右有次序（最左边的为第一个孩子）。无序树：无序树：无序树：无序树：树中结点的各子树无次序。树中结点的各子树无次序。结点：结点：数据元素数据元素+指向子树的分支指向子树的分支 根结点：根结点：非空树中无前驱结点的结点非空树中无前驱结点的结点 森林：森林：森林：森林：是是 m(m0)棵互不相交的树的集合。棵互不相交的树的集合。一棵树可以看成是一个特殊的森林。一棵树可以看成是一个特殊的森林。把根结点删除树就变成了森林。把根结点删除树就变成了森林。给森林中的各子树加上一个双亲结点，森林就变成了树。给森林中的各子树加上一个双亲结点，森林就变成了树。树树 森林森林 一定是一定是 不一定是不一定是 E F G H I A B C D J K L M 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 树的逻辑结构描述树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为：一棵树的逻辑结构可以用二元组描述为：Tree=(root,F)数据元素数据元素 根结点根结点 包含包含 m(m0)棵树的森林棵树的森林 F=(T1,T2,Tm)Ti=(ri,Fi)Ti 称做称做根根 root 的第的第 i 棵子树。棵子树。当当 m0 时，在树根和其子树森林之间存在下列关系：时，在树根和其子树森林之间存在下列关系：RF=|i=1,2,m,m 0数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中RF=,Tree=(A,F)F=(T1,T2,T3)T1=(B,F1)T2=(C,F2)T3=(D,F3)r1F1=,r2F2=r3F3=,E F G H I A B C D J K L M 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 树的抽象数据类型定义：树的抽象数据类型定义：ADT Tree 数据对象数据对象 D：D 是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系 R：（：（略）略）基本操作基本操作 P：结构初始化结构初始化结构初始化结构初始化 InitTree(&T)；操作结果：操作结果：构造空树构造空树 T。CreateTree(&T,definition)；初始条件：初始条件：definition 给出树给出树 T 的定义。的定义。操作结果：操作结果：按按 definition 构造树构造树 T。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 销毁销毁销毁销毁结构结构结构结构 DestroyTree(&T)；初始条件：初始条件：树树 T 存在存在。操作结果：操作结果：销毁树销毁树 T。引用型操作引用型操作引用型操作引用型操作 TreeEmpty(T)初始条件：初始条件：树树 T 存在。存在。操作结果：操作结果：若若 T 为空树，则返回为空树，则返回 TURE，否则否则 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 有右兄弟，则返回它的右兄弟，有右兄弟，则返回它的右兄弟，否则函数值为否则函数值为“空空”。TraverseTree(T,Visit()；初始条件：初始条件：树树 T 存在，存在，Visit 是对结点操作的函数。是对结点操作的函数。操作结果：操作结果：按某种次序对按某种次序对 T 的每个结点调用函数的每个结点调用函数 Visit()一次且至多一次。一旦一次且至多一次。一旦 Visit()失败，则操作失败。失败，则操作失败。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中加工型操作加工型操作加工型操作加工型操作 ClearTree(&T)；初始条件：初始条件：树树 T 存在。存在。操作结果：操作结果：将树将树 T 清为空树。清为空树。InsertChild(&T,&p,i,c)；初始条件：初始条件：树树 T 存在，存在，p 指向指向 T 中某个结点，中某个结点，1ip 所指结点的度所指结点的度+1，非空树，非空树 c 与与 T 不相交。不相交。操作结果：操作结果：插入插入 c 为为 T 中中 p 指结点的第指结点的第 i 棵子树。棵子树。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 DeleteChild(&T,&p,i)；初始条件：初始条件：树树 T 存在，存在，p 指向指向 T 中某个结点，中某个结点，1ip 所指结点的度。所指结点的度。操作结果：操作结果：删除删除 T 中中 p 所指结点的第所指结点的第 i 棵子树。棵子树。ADT Tree 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 树的表示形式树的表示形式 1树形表示法树形表示法 A 空树空树 A B 仅含有根结点的树仅含有根结点的树 2嵌套集合（文氏）表示法嵌套集合（文氏）表示法 ABEFK LDHIMJCG E F G H I A B C D J K L M 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中3凹入表示法凹入表示法 A B E K L F C G D H M I J 4广义表表示法广义表表示法 E F G H I A B C D J K L M(A(A(B(E(K,L),F),C(G),D(H(M),I,J)数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中6.2 二叉树二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉二叉树在树结构的应用中起着非常重要的作用，因为对二叉 树的许多操作算法简单，而任何树都可以与二叉树相互转换，这树的许多操作算法简单，而任何树都可以与二叉树相互转换，这 样就解决了树的存储结构及其运算中存在的复杂性。样就解决了树的存储结构及其运算中存在的复杂性。6.2.1 二叉树的定义二叉树的定义 二叉树是二叉树是 n(n0)个结点的有限集，它或者是个结点的有限集，它或者是空集空集(n=0)，或者由一个或者由一个根结点根结点及及两棵互不相交两棵互不相交的的 分别称作这个根的分别称作这个根的左子树左子树和和右子树右子树的二叉树组成。的二叉树组成。定义定义 特点特点 1、每个结点最多有俩孩子、每个结点最多有俩孩子(二叉树中不存在度大于二叉树中不存在度大于二叉树中不存在度大于二叉树中不存在度大于 2 2 的结点的结点的结点的结点)。2、子树有左右之分，其次序不能颠倒。、子树有左右之分，其次序不能颠倒。3、二叉树可以是空集合，根可以有空的左子树或空的右子树。、二叉树可以是空集合，根可以有空的左子树或空的右子树。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 二叉树二叉树结点的子树要区分左子树和右子树，即使只有一棵子结点的子树要区分左子树和右子树，即使只有一棵子 树也要进行区分，说明它是左子树，还是右子树。树树也要进行区分，说明它是左子树，还是右子树。树当结点只有当结点只有 一个孩子时，就无须区分它是左还是右的次序。（一个孩子时，就无须区分它是左还是右的次序。（也就是二叉树也就是二叉树 每个结点位置或者说次序都是固定的，可以是空，但是不可以说每个结点位置或者说次序都是固定的，可以是空，但是不可以说 它没有位置，而树的结点位置是相对于别的结点来说的，没有别它没有位置，而树的结点位置是相对于别的结点来说的，没有别 的结点时，它就无所谓左右了）的结点时，它就无所谓左右了），因此二者是不同的。，因此二者是不同的。这是二叉这是二叉 树与树的最主要的差别。树与树的最主要的差别。二二叉叉树树不是不是不是不是树的特殊情况，它们是两个概念。树的特殊情况，它们是两个概念。注注 A B 具有两个结点的树只有一种状态具有两个结点的树只有一种状态 A B A B 具有两个结点的二叉树有两种状态具有两个结点的二叉树有两种状态 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 二叉树的二叉树的 5 种基本形态种基本形态 (a)空二叉空二叉树树(b)根和空的根和空的 左右子树左右子树(c)根和左子树根和左子树(d)根和右子树根和右子树 (e)根和左右子树根和左右子树 注：虽然二叉树与树概念不同，注：虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。但有关树的基本术语对二叉树都适用。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中二叉树的抽象数据类型定义：二叉树的抽象数据类型定义：ADT BinaryTree 数据对象数据对象 D：D 是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系 R：（略）略）基本操作基本操作 P：结构初始化结构初始化结构初始化结构初始化InitBiTree(&T);操作结果：操作结果：构造空二叉树构造空二叉树 T。CreateBiTree(&T,definition);初始条件：初始条件：definition 给出二叉树给出二叉树 T 的定义。的定义。操作结果：操作结果：按按 definition 构造二叉树构造二叉树 T。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 销毁结构销毁结构销毁结构销毁结构DestroyBiTree(&T);初始条件：初始条件：二叉树二叉树 T 存在。存在。操作结果：操作结果：销毁二叉树销毁二叉树 T。引用型操作引用型操作引用型操作引用型操作BiTreeEmpty(T);初始条件：初始条件：二叉树二叉树 T 存在存在。操作结果：操作结果：若若 T 为空二叉树，则返回为空二叉树，则返回 TRUE，否则返回否则返回 FALSE。BiTreeDepth(T);初始条件：初始条件：二叉树二叉树 T 存在存在。操作结果：操作结果：返回返回 T 的深度的深度。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 Root(T);初始条件：初始条件：二叉树二叉树 T 存在。存在。操作结果：操作结果：返回返回 T 的根。的根。Value(T,e);初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。操作结果：操作结果：返回返回 e 的值。的值。Parent(T,e);初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。操作结果：操作结果：若若 e 是是 T 的非根结点，则返回它的双亲，的非根结点，则返回它的双亲，否则返回否则返回“空空”。LeftChild(T,e);初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。操作结果：操作结果：返回返回 e 的左孩子。若的左孩子。若 e 无左孩子则返回无左孩子则返回“空空”。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 RightChild(T,e);初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。操作结果：操作结果：返回返回 e 的右孩子。若的右孩子。若 e 无右孩子则返回无右孩子则返回“空空”。LeftSibling(T,e);初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。操作结果：操作结果：返回返回 e 的左兄弟。若的左兄弟。若 e 是其双亲的左孩子或是其双亲的左孩子或 无左兄弟，则返回无左兄弟，则返回“空空”。RightSibling(T,e);初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 的结点。的结点。操作结果：操作结果：返回返回 e 的右兄弟。若的右兄弟。若 e 是其双亲的右孩子或是其双亲的右孩子或 无右兄弟，则返回无右兄弟，则返回“空空”。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中PreOrderTraverse(T,visit();初始条件：初始条件：二叉树二叉树 T 存在，存在，visit 是对结点操作的应用函数。是对结点操作的应用函数。操作结果：操作结果：先序遍历先序遍历先序遍历先序遍历 T，对每个结点调用函数对每个结点调用函数 visit 一次一次 且仅一次。一旦且仅一次。一旦 visit()失败，则操作失败。失败，则操作失败。InOrderTraverse(T,vsit();初始条件：初始条件：二叉树二叉树 T 存在，存在，visit 是对结点操作的应用函数。是对结点操作的应用函数。操作结果：操作结果：中序遍历中序遍历中序遍历中序遍历 T，对每个结点调用函数对每个结点调用函数 Visit 一次一次 且仅一次。一旦且仅一次。一旦 visit()失败，则操作失败。失败，则操作失败。PostOrderTraverse(T,visit();初始条件：初始条件：二叉树二叉树T存在，存在，visit 是对结点操作的应用函数。是对结点操作的应用函数。操作结果：操作结果：后序遍历后序遍历后序遍历后序遍历 T，对每个结点调用函数对每个结点调用函数 visit 一次一次 且仅一次。一旦且仅一次。一旦 visit()失败，则操作失败。失败，则操作失败。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中LevelOrderTraverse(T,visit();初始条件：初始条件：二叉树二叉树 T 存在，存在，visit 是对结点操作的应用函数。是对结点操作的应用函数。操作结果：操作结果：按按按按层次遍历层次遍历层次遍历层次遍历 T，对每个结点调用函数对每个结点调用函数 visit 一次一次 且仅一次。一旦且仅一次。一旦 visit()失败，则操作失败。失败，则操作失败。加工型操作加工型操作加工型操作加工型操作ClearBiTree(&T);初始条件：初始条件：二叉树二叉树 T 存在。存在。操作结果：操作结果：将二叉树将二叉树 T 清为空树。清为空树。Assign(&T,&e,value);初始条件：初始条件：二叉树二叉树 T 存在，存在，e 是是 T 中某个结点。中某个结点。操作结果：操作结果：结点结点 e 赋值为赋值为 value。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 InsertChild(&T,p,LR,c);初始条件：初始条件：二叉树二叉树 T 存在，存在，p 指向指向 T 中某个结点，中某个结点，LR 为为 0 或或 1，非空二叉树，非空二叉树 c 与与 T 不相交且右子不相交且右子 树为空。树为空。操作结果：操作结果：根据根据 LR 为为 0 或或 1，插入，插入 c 为为 T 中中 p 所指结所指结 点的左或右子树。点的左或右子树。p 所指结点原有左或右子所指结点原有左或右子 树成为树成为 c 的右子树。的右子树。DeleteChild(&T,p,LR);初始条件：初始条件：二叉树二叉树 T 存在，存在，p 指向指向 T 中某个结点，中某个结点，LR 为为 0 或或 1。操作结果：操作结果：根据根据 LR 为为 0 或或 1，删除，删除 T 中中 p 所指结点的所指结点的 左或右子树。左或右子树。ADT BinaryTree 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中6.2.2 二叉树的性质二叉树的性质 性质性质性质性质 1 1：在二叉树的第在二叉树的第 i 层上至多有层上至多有 2 i-1 个结点个结点(i 1)。证：证：采用归纳法证明此性质。采用归纳法证明此性质。归纳基：归纳基：当当 i=1 时，只有一个根结点，时，只有一个根结点，2 i-1=20=1，命题成立。命题成立。归纳假设：归纳假设：设对所有的设对所有的 j(1j i)，命题成立，即第命题成立，即第 j 层上至多层上至多 有有2j-1 个结点。那么可以证明个结点。那么可以证明 ji 时命题也成立。时命题也成立。归纳证明：归纳证明：由归纳假设可知，第由归纳假设可知，第 i 1 层上至多有层上至多有 2 i-2个结点。个结点。由于二叉树每个结点的度最大为由于二叉树每个结点的度最大为 2，故在第，故在第 i 层上最层上最 大结点数为第大结点数为第 i 1 层上最大结点数的层上最大结点数的 2 倍，即：倍，即：22 i 22 i 1。证毕。证毕。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中性质性质性质性质 2 2：深度为深度为 k 的二叉树至多有的二叉树至多有 2k1 个结点（个结点（k 1)。证：证：由性质由性质 1 可知，深度为可知，深度为 k 的二叉树的最大结点数为：的二叉树的最大结点数为：证毕。证毕。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中性质性质性质性质 3 3：对任何一棵二叉树对任何一棵二叉树 T，如果其叶子数为如果其叶子数为 n0，度为度为 2 的结点的结点 数为数为 n2，则则 n0=n2+1。证：证：设设 n1 为二叉树为二叉树 T 中度为中度为 1 的结点数。因为二叉树中所有结点的结点数。因为二叉树中所有结点 均均2，所以其结点总数为：，所以其结点总数为：n=n0+n1+n2 再看二叉树中的分支数，除根结点外，其余结点都有一个分再看二叉树中的分支数，除根结点外，其余结点都有一个分 支进入，设支进入，设 B 为分支总数，则有：为分支总数，则有：n=B1 由于这些分支都是由度为由于这些分支都是由度为 1 和和 2 的结点射出的，所以有：的结点射出的，所以有：B=n1+2n2 于是有：于是有：n=B+1n1+2n2+1 所以有：所以有：n0+n1+n2=n1+2n2+1 即：即：n0=n2+1 证毕。证毕。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 满二叉树满二叉树(Full binary tree)特点：特点：每一层上的结点数都达到最大。每一层上的结点数都达到最大。叶子全部在最底层。叶子全部在最底层。编号规则：编号规则：从根结点开始，自上而下，自左而右从根结点开始，自上而下，自左而右。一棵深度为一棵深度为 k 且有且有 2k-1 个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。2453671数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 完全二叉树完全二叉树(Complete binary tree)深度为深度为 k 的具有的具有 n 个结点的二叉树，当且仅当其每一个结点的二叉树，当且仅当其每一 个结点都与深度为个结点都与深度为 k 的满二叉树中编号为的满二叉树中编号为 1 n 的结点一一的结点一一 对应时，称之为对应时，称之为完全二叉树完全二叉树。特点：特点：叶子只可能分布在层次最大的两层上。叶子只可能分布在层次最大的两层上。对任一结点，如果其右子树的最大层次为对任一结点，如果其右子树的最大层次为 l，则其左子则其左子 树的最大层次必为树的最大层次必为 l 或或 l+1。满二叉树满二叉树 完全二叉树完全二叉树 是是定定一一 不不 一一定定 是是 245361完全二叉树完全二叉树 245361非完全二叉树非完全二叉树 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中完全二叉树的性质完全二叉树的性质 性质性质性质性质 4 4：具有具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。证：假设此二叉树的深度为证：假设此二叉树的深度为 k，则根据性质则根据性质 2 及完全二叉树的及完全二叉树的 定义得到：定义得到：2k-1 1 n2k 1 或或 2k-1n 2k 取对数得：取对数得：k 1log2n 1，则其双亲是结点则其双亲是结点 i/2。(2)如果如果 2i n，则结点则结点 i 为叶子结点，无左孩子；否则，其为叶子结点，无左孩子；否则，其 左孩子是结点左孩子是结点 2i。(3)如果如果 2i+1 n，则结点则结点 i 无右孩子；否则，其右孩子是无右孩子；否则，其右孩子是 结点结点 2i+1。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中证：证：(1)可以从可以从(2)和和(3)推出，所以先证明推出，所以先证明(2)和和(3)。对于对于对于对于 i i1 1，由完全二叉树的定义，其左孩子是由完全二叉树的定义，其左孩子是 结点结点 2=2i，若若 2=2i n=1，即不存在结点即不存在结点 2，此，此 时，结点时，结点 i 无左孩子。无左孩子。(2)得证得证。i 1 结点结点 i 的右孩子也只能是结点的右孩子也只能是结点 3=2i+1，若若 3=2i+1 n，即不存在结点即不存在结点 3，此时结点此时结点 i 无右孩子。无右孩子。(3)得证得证。2i 22i+1 32i 2数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 (1)设第设第 j(1j log2n)层的层的 第一个结点第一个结点第一个结点第一个结点的编号为的编号为 i(由二叉树的由二叉树的 定义和性质定义和性质 2 知知 i=2 j1)，则其左孩则其左孩 子必为第子必为第 j+1 层的第一个结点，其层的第一个结点，其 编号为编号为 2 j22 j 12i。1 第第 j 层层 23 对于对于对于对于 i i 1 1，可分为两种情况：可分为两种情况：第第 j 1 层层 第第 j+1 层层 i 2 j-1 2i=2j 2i+12 j-1-1=2j-1 如果如果 2i n，则无左孩子。则无左孩子。(2)得证得证。其右孩子必定为第其右孩子必定为第 j+1 层的第二个结点，层的第二个结点，编号为编号为2i+1。若若 2i+1 n，则无右孩子。则无右孩子。(3)得证得证。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 (2)设第设第 j(1j log2n)层的层的某个结点某个结点某个结点某个结点的编号为的编号为 i(2 j 1i 2 j 1)，且且 2i+11 时：时：如果如果 i 为左孩子，且为左孩子，且 i 的双亲为的双亲为 p，则，则有有 i=2p，p=i/2=i/2，即，即 i/2 是是 i 的双亲；的双亲；i 为偶数为偶数 i 为奇数为奇数 如果如果 i 为右孩子，且为右孩子，且 i 的双亲为的双亲为 p，则有则有 i2p+1，p=(i-1)/2=i/2 1/2=i/2，即即 i/2 是是 i 的双亲的双亲。证毕证毕。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中6.2.3 二叉树的存储结构二叉树的存储结构 1、顺序存储结构顺序存储结构 完全二叉树：完全二叉树：用一组地址连续的用一组地址连续的 存储单元依次存储单元依次自上而下、自左至右自上而下、自左至右自上而下、自左至右自上而下、自左至右存存 储结点元素，即将编号为储结点元素，即将编号为 i 的结点元的结点元 素存储在一维数组中下标为素存储在一维数组中下标为 i 1 的分的分 量中。量中。1 2 3 4 5 6 1 2 3 4 5 0 0 6 一般二叉树：一般二叉树：将其每个结点与完将其每个结点与完 全二叉树上的结点相对照，存储在一全二叉树上的结点相对照，存储在一 维数组的相应分量中。维数组的相应分量中。这种顺序存储结构仅适用于完全二叉树这种顺序存储结构仅适用于完全二叉树 245361完全二叉树完全二叉树 245361非完全二叉树非完全二叉树 1 2 3 4 5 6 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中最坏情况：最坏情况：最坏情况：最坏情况：深度为深度为 k 的且只的且只 有有 k 个结点的右单支树需要个结点的右单支树需要 长度为长度为2k-1 的一维数组。的一维数组。1 0 2 0 0 0 3 表示方式：表示方式：#define MAX_TREE_SIZE 100 /二叉树的最大结点数二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE;/0 号单元存储根结点号单元存储根结点SqBiTree bt;231右单支树右单支树 0000数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中2 2、链式存储结构链式存储结构链式存储结构链式存储结构 存储方式存储方式 二叉树结点的特点二叉树结点的特点 lchild data rchild结点结构结点结构 data rchild lchild data parentlchildrchild数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 A B C D E F G A B C D 二叉链表二叉链表 在在 n 个结点的二叉链表中，有个结点的二叉链表中，有 n+1 个空指针域。个空指针域。ABCDEFGABCD数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中typedef struct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针左右孩子指针 BiTNode,*BiTree;C 语言的类型描述如下：语言的类型描述如下：数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 A B C D E F G 三叉链表三叉链表 ABCDEFGparentdatalchild rchild lchild data parent rchild 结点结构结点结构 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 6.3.1 遍历二叉树（遍历二叉树（重点，是进行其他运算的基础重点，是进行其他运算的基础重点，是进行其他运算的基础重点，是进行其他运算的基础）遍历概念遍历概念 顺着某一条搜索路径顺着某一条搜索路径巡访巡访二叉树中的结点，使二叉树中的结点，使 得每个结点得每个结点均被访问一次均被访问一次，而且，而且仅被访问一次仅被访问一次。“访问访问访问访问”的含义很广，可以是对结点作各种处理，如：输出结的含义很广，可以是对结点作各种处理，如：输出结 点的信息、修改结点的数据值等，但要求这种访问点的信息、修改结点的数据值等，但要求这种访问不破坏原来的不破坏原来的不破坏原来的不破坏原来的 数据结构数据结构数据结构数据结构。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 遍历方法遍历方法 依次遍历二叉树中的三个组成依次遍历二叉树中的三个组成 部分，便是遍历了整个二叉树部分，便是遍历了整个二叉树 假设：假设：L：遍历左子树遍历左子树 D：访问根结点：访问根结点 R：遍历右子树遍历右子树 则遍历整个二叉树方案共有：则遍历整个二叉树方案共有：遍历目的遍历目的 得到树中所有结点的一个得到树中所有结点的一个线性线性排列。排列。根结点根结点 左子树左子树 右子树右子树 DLR、LDR、LRD、DRL、RDL、RLD 六种。六种。数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中若规定先左后右，则只有前三种情况：若规定先左后右，则只有前三种情况：DLR DLR 先（根）序遍历，先（根）序遍历，LDR LDR 中（根）序遍历，中（根）序遍历，LRD LRD 后（根）序遍历。后（根）序遍历。根结点根结点 左子树左子树 右子树右子树 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 先序先序先序先序遍历二叉树的操作定义：遍历二叉树的操作定义：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 (1)访问根结点；访问根结点；(2)先序遍历左子树；先序遍历左子树；(3)先序遍历右子树。先序遍历右子树。先序遍历的顺序为：先序遍历的顺序为：ABC 先序遍历的顺序为：先序遍历的顺序为：ABELDHMIJ A B C A B D E LH M I J 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 中序中序中序中序遍历二叉树的操作定义：遍历二叉树的操作定义：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 (1)中序遍历左子树；中序遍历左子树；(2)访问根结点；访问根结点；(3)中序遍历右子树。中序遍历右子树。中序遍历的顺序为：中序遍历的顺序为：BAC 中序遍历的顺序为：中序遍历的顺序为：ELBAMHIDJ A B C A B D E LH M I J 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 后序后序后序后序遍历二叉树的操作定义：遍历二叉树的操作定义：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 (1)后序遍历左子树；后序遍历左子树；(2)后序遍历右子树；后序遍历右子树；(3)访问根结点。访问根结点。后序遍历的顺序为：后序遍历的顺序为：BCA 后序遍历的顺序为：后序遍历的顺序为：LEBMIHJDA A B C A B D E LH M I J 数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中-/+abcdef例：例：请写出下图所示二叉树的先序、中序和后序遍历顺序。请写出下图所示二叉树的先序、中序和后序遍历顺序。遍历结果：遍历结果：先序：先序：-+ab-c d/e f 中序：中序：a+bc-d-e/f 后序：后序：a b c d-+e f/-表达式的表达式的前缀表示前缀表示前缀表示前缀表示（波兰式）（波兰式）表达式的表达式的中缀表示中缀表示中缀表示中缀表示 表达式的表达式的后缀表示后缀表示后缀表示后缀表示（逆波兰式）（逆波兰式）数据结构数据结构 第六章第六章 树和二叉树树和二叉树制作：制作：计算机科学与技术系 徐振中 先序遍