数据结构课件：第6章 树和二叉树1基本概念和二叉树

树和森林第6章树和二叉树树的基本概念二叉树遍历二叉树和线索二叉树赫夫曼树及其应用第6章树和二叉树第6章树和二叉树计算机学院材冶学院机械学院计算机科学系计算机技术系软件工程系……武汉科技大学网络工程系第6章树和二叉树第6章树和二叉树树的逻辑定义§6.1树的基本概念

树是由n(n≥0)个结点组成的有限集合T。在任意一个非空树中：有且仅有一个特定的结点称为根(root)；n>1时，其余结点可以分为m(m>0)个互不相交的有限集T1,T2,T3,…,Tm，其中每一个集合本身又是一棵树，且称为根的子树。注意：1.树的定义具有递归性，即树中有树。2.n=0个结点时为空树。树的逻辑定义§6.1树的基本概念其中A是根结点，其余结点分成三个互不相交的子集：T1={B，E，F，K，L},T2={C，G},T3={D，H，I，J，M}T1,T2,T3

都是A的子树，且本身也是一棵树。ABCDEFGHIJKLM右图是具有13个结点的树树的逻辑定义§6.1树的基本概念其中A是根结点，其余结点分成三个互不相交的子集：T1={B，E，F，K，L},T2={C，G},T3={D，H，I，J，M}T1,T2,T3

都是A的子树，且本身也是一棵树。ABCDEFGHIJKLM右图是具有13个结点的树树的表示方法图形表示法(分支图表示法)嵌套集合表示法广义表表示法目录表示法左孩子－右兄弟表示法§6.1树的基本概念图形表示法(分支图表示法)§6.1树的基本概念ABCDEFGHIJKL广义表表示法§6.1树的基本概念(A(B(E(K,L),F),C(G),D(H(M),I,J))根作为由子树森林组成的表的名字写在表的左边嵌套集合表示法GCABDHIJEKFL§6.1树的基本概念嵌套集合：是一些集合的集体，对于其中任何两个集合，

或不相交，或一个包含另一个的形式表示。凹入表示法§6.1树的基本概念凹入表示：类似书的编目A*****************

B***************

E*************

F*************

K***********

L***********

C***************

G*************

D***************

H*************

I*************

J*************左孩子－右兄弟表示法§6.1树的基本概念ACDEFGHIJKLB左孩子－右兄弟表示法§6.1树的基本概念ABCDEFGHIJKL树的基本术语§6.1树的基本概念——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点

根叶子森林——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合

(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。有序树无序树树的基本术语§6.1树的基本概念——即树的数据元素——结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）结点结点的度树的度树的深度(或高度)——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝结点的层次终端结点分支结点1334树结构和线性结构的比较§6.1树的基本概念

第一个数据元素（无前驱）

最后一个数据元素（无后继）

其它元素（一个前驱、一个后继）

根结点（无前驱）

多个叶子结点（无后继）

其它结点（一个前驱、多个后继）

线性结构树结构树的抽象类型定义§6.1树的基本概念ADTTree{数据对象D：是具有相同特性的数据元素的集合数据关系R：若D为空集，则称为空树；

若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系

(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

(2)若D-{root}!=Φ，则存在D-{root}的一个划分D1,D2,…,Dm(m>0)，

对任意j≠k(1≤j，k≤m)有Dj∩Dk=Φ，且对任意的i(1≤i≤m)，

唯一存在数据元素xi∈Di，有<root，xi>∈H；(3)对应于D-{root}的划分，H-{<root，x1>，…，<root，xm>}有唯一

的一个划分H1，H2，…，Hm(m>0)，对任意j≠k(1≤j，k≤m)，

有Hj∩Hk=Φ，对任意i(1≤i≤m)，Hi是Di上的二元关系，(Di,{Hi})

是一棵符合本定义的子树，称为根root的子树。基本操作P：}ADTTree树的抽象类型定义§6.1树的基本概念1）InitTree(&T);//构造空树T2）DestroyTree(&T);//销毁树T3）TreeEmpty(T);//判别T是否为空树4）TreeDepth(T);//返回T的深度。5）Root(T);//返回T的根6）Value(T,cur_e);//返回cur_e的值7）Assign(&T,cur_e,value);//结点cur_e赋值value。8）Parent(T,cur_e);//若cur_e是T的非根结点，则返回它的9）LeftChild(T,cur_e);//若cur_e不是叶子结点，则返回它的最左孩子10)RightSibling(T,cur_e);//若cur_e有右兄弟，则返回它的右兄弟11)TraverseTree(T,Visit());//按某种次序对T的每个结点调用函数

树的存储结构§6.1树的基本概念讨论1：树是非线性结构，该怎样存储？————仍然有顺序存储、链式存储等方式。

树的存储结构§6.1树的基本概念讨论3：树的链式存储方案应该怎样制定？可规定为：从上至下、从左至右将树的结点依次存入内存。重大缺陷：复原困难（不能唯一复原就没有实用价值）。讨论2：树的顺序存储方案应该怎样制定？可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？

即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。树的存储结构§6.1树的基本概念解决思路：二叉树先研究最简单、最有规律的树，

然后设法把一般的树转化为简单树。二叉树的定义§6.2二叉树为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树。二叉树的定义§6.2二叉树或者是空树，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。二叉树的定义§6.2二叉树逻辑结构：一对二（1：2）

基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）②左子树和右子树次序不能颠倒（有序树）。基本形态：

二叉树的定义§6.2二叉树问：具有3个结点的二叉树可能有几种不同形态？

普通树呢？

5种/2种二叉树的抽象数据类型定义§6.2二叉树ADTBinaryTree{

数据对象D:

数据关系R:

基本操作P：}ADTBinaryTree若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明

④……

//关于左子树和右子树的说明D是具有相同特性的数据元素的集合。//至少有20个二叉树的抽象数据类型定义§6.2二叉树某些操作和树的基本操作类似，另由于二叉树本身特性，增加的操作有：RightChild(T,e);返回e的右孩子，否则其函数值为“空”。LeftSibling(T,e);返回e的左兄弟，若e是T的左孩子或无左兄弟PreOrderTraverse(T,Visit());先序遍历InOrderTraverse(T,Visit());中序遍历PostOrderTraverse(T,Visit());后序遍历LevelOrderTraverse(T,Visit());层序遍历二叉树的抽象数据类型定义§6.2二叉树某些操作和树的基本操作类似，另由于二叉树本身特性，增加的操作有：RightChild(T,e);返回e的右孩子，否则其函数值为“空”。LeftSibling(T,e);返回e的左兄弟，若e是T的左孩子或无左兄弟PreOrderTraverse(T,Visit());先序遍历InOrderTraverse(T,Visit());中序遍历PostOrderTraverse(T,Visit());后序遍历LevelOrderTraverse(T,Visit());层序遍历二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！（遍历——指每个结点都被访问且仅访问一次，不遗漏不重复）。二叉树的性质§6.2二叉树讨论1：第i层的结点数至多是多少？

（二进制性质）

性质1:在二叉树的第i层上至多有2i-1个结点（i>=1）2i-1个提问：第i层上至少有

个结点？1423156789101112131415二叉树的性质§6.2二叉树讨论2：深度为k的二叉树，至多有多少个结点？

（等比级数前k项和的公式）

性质2:深度为k的二叉树至多有2k-1个结点（k>=1）2k-1个提问：深度为k时至少有个结点？k423156789101112131415二叉树的性质§6.2二叉树讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？

性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1（即n0=n2+1）证明：∵

二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数)

又∵二叉树中全部结点数n＝B+1

(总分支数＋根结点)

（除根结点外，每个结点必有一个直接前趋，即一个分支）

而总分支数B=n1+2n2

(1度结点必有1个直接后继，2度结点必有2个)

三式联立可得：n0+n1+n2=

n1+2n2

+1,即n0=n2+1实际意义：叶子数＝2度结点数＋1两种特殊形式的二叉树§6.2二叉树满二叉树：深度为k且含有2k-1个结点的二叉树423156789101112131415218特点：每层都“充满”了结点两种特殊形式的二叉树§6.2二叉树完全二叉树：树中所含的n个结点和满二叉树中编号

为1至n的结点一一对应42315678910218两种特殊形式的二叉树§6.2二叉树423157621两种特殊形式的二叉树§6.2二叉树42315621两种特殊形式的二叉树§6.2二叉树423156789101112218特点：只有最后一层叶子不满，且全部集中在左边两种特殊形式的二叉树§6.2二叉树完全二叉树的特点(1)叶子结点只可能在层次最大的两层上出现；(2)对任一结点，若其右分支下的子孙的最大层次为

L，则其左分支下的子孙的最大层次必为L或L+1。二叉树的性质§6.2二叉树性质4：具有n个结点的完全二叉树的高度为

└

log2n┘+1证明：设完全二叉树的高度为k，则有(2k-1

-1)<n

≤(2k-1)

或2k-1

≤

n<2k

两边取对数k-1≤log2n<k

因为k是整数，所以k=└

log2n┘+1二叉树的性质§6.2二叉树性质5：具若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲;

否则，编号为└

i/2

┘的结点为其双亲结点;(2)若2i>n，则该结点无左孩子;

否则，编号为2i的结点为其左孩子结点；(3)若2i+1>n，则该结点无右孩子结点;

否则，编号为2i+1的结点为其右孩子结点。二叉树的性质§6.2二叉树性质6：满二叉树第k层的结点个数比其1~k-1层所有结点个数之和多一个。二叉树的存储结构§6.2二叉树

(1)二叉树的顺序存储表示(2)二叉树的链式存储表示二叉树的顺序存储表示§6.2二叉树

#defineMAX_TREE_SIZE100

//二叉树的最大结点数

typedefTElemTypeSqBiTree[MAX_TREE_SIZE];

//0号单元存储根结点

SqBiTreebt;二叉树的顺序存储表示§6.2二叉树

按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。ABCDEFGHI123456789ABCGEIDHFT[0]一般不用123456789二叉树的顺序存储表示§6.2二叉树

问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5）例如，对应[2]的两个孩子必为[4]和[5]，即B的左孩子必是D，右孩子必为E。二叉树的顺序存储表示§6.2二叉树

讨论：不是完全二叉树怎么办？答：一律转为完全二叉树！将各层空缺处统统补上“虚结点”AB^C^^^D^…E123456789…16ABECD12345678910111213141516二叉树的顺序存储结构的性能分析§6.2二叉树顺序存储结构仅适用于完全二叉树。(1)在最坏的情况下，一个深度为k且只有k个结点的单支树，却需要长度为2k-1的一维数组。这样就造成存储空间的浪费。

(2)插