数据结构课件：树和二叉树-1

对于线性数据结构，每个元素都有唯一的前驱（第一个除外）和后继（最后一个除外），但是在现实应用中，一些问题的数据元素之间的关系就不这样简单。

本章学习一种非线性数据结构-----树，数据元素之间是一种层次关系，元素有且只有一个前驱，但可以有多个后继树和二叉树树的概念和基本术语二叉树二叉树遍历线索二叉树树与森林霍夫曼树

树和二叉树1树的概念和基本术语树的定义

树是由n(n0)个结点的有限集合。如果n=0，称为空树；如果n>0，则

有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；

当n>1，除根以外的其它结点划分为m(m>0)个互不相交的有限集

T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)ACGBDEFKLHMIJ例如A只有根结点的树有13个结点的树其中:A是根,其余结点分成三个互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲ACGBDEFKLHMIJ兄弟结点：同一双亲的孩子结点

堂兄结点：双亲在同一层的结点互为堂兄弟结点层次

：根结点的层定义为1根的孩子为第二层结点依此类推ACGBDEFKLHMIJ树的基本术语树的高度（或深度）：树中结点的最大层次结点的度：结点子树的个数树的度：树内各结点的度的最大值叶子结点：也叫终端结点，是度为0的结点分枝结点：也叫非终端结点，度不为0的结点有序树：子树有序的树，（子树不能互换）如：家族树无序树：不考虑子树的顺序ACGBDEFKLHMIJ树的基本术语路径：树中的k个结点n1,n2，…，nk，满足ni

是ni+1的双亲，n1到nk有一条路径路径长度：分支数＝路径上结点个数一1根没有双亲，叶子没有孩子；vi是vj

的双亲，则L(vi)=L(vj)-1;

堂兄弟的双亲是兄弟关系吗？有序树和无序树的区别注意ACGBDEFKLHMIJ任何一棵非空树是一个二元组

Tree=（root，F）其中：root被称为根结点，

F被称为子树森林是m（m≥0）棵互不相交的树的集合ArootBEFKLCGDHIJMF森林对比树型结构和线性结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素

(无前驱)

根结点

(无前驱)最后一个数据元素

(无后继)多个叶子结点

(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)树的常见表示方法1.直观表示法：用圆圈表示结点，元素写在圆圈中，连线表示元素之间的关系.根在上，叶子在下（即树向下生长）2、集合表示法：根据树的集合定义，写出集合划分

3、文氏图表示法：

集合表示的一种直观表示，用图表示集合树的常见表示法4、目录表示法：

将一棵树描述为一本书，书--章--节--小节树的常见表示法5、广义表表示法：将一棵树描述为一个广义表，子树就对应子表人们最常用的是第一种，但是不适合计算机！树的常见表示法树的基本操作

InitTree（＆T）操作结果：构造空树T。

DestroyTree（＆T）初始条件：树T存在。操作结果：销毁树T。

CreateTree（＆T，definition）初始条件：definition给出树T的定义。操作结果：按definition构造树T。

ClearTree（＆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的非根结点，则返回它的双亲，否则函数值为“空”。

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（）失败，则操作失败LeftChild（T，cur＿e）

初始条件：树T存在，cur＿e是T中某个结点。操作结果：若cur＿e是T的非叶子结点，则返回它的最左孩子，否则返回“空”

6.2二叉树一二叉树的概念二二叉树的性质三二叉树的存储结构定义:二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成ABCDEFGHK根结点左子树右子树2二叉树(BinaryTree)特点:每个结点至多只有两棵子树（二叉树中不存在度大于2的结点）二叉树的五种基本形态N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树应用举例

e

d

c

b

f

a

+

*

/

-

-

a+b*(c-d)-e/f例可以用二叉树表示表达式性质1 在二叉树的第i层上至多有2i－1个结点(i

1)

[证明用归纳法]证明：当i=1时，只有根结点，2i-1=20=1。假设对所有j，i>j1，命题成立，即第j层上至多有2j-1

个结点。由归纳假设第i-1

层上至多有2i－2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i－2=2i-1。性质性质2 深度为k的二叉树至多有2k-1个结点(k1)证明：由性质1可见，深度为k的二叉树的最大结点数为

＝20+21+…+2k-1=2k-1＝性质3 对任何一棵二叉树T,如果其叶结点数为n0,度为2的结点数为n2,则n0＝n2＋1.证明：若度为1的结点有n1

个，总结点个数为n，总边数为e，则根据二叉树的定义，

n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2

-1n2=n0

-1n0=n2+1定义1满二叉树(FullBinaryTree)

一棵深度为k且有2k-1个结点的二叉树称为满二叉树两种特殊形态的二叉树6217543891011131412满二叉树152154367216543非完全二叉树定义2完全二叉树(CompleteBinaryTree)

若设二叉树的高度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。621754389101112完全二叉树性质4

具有n(n0)个结点的完全二叉树的深度为log2(n)＋1

证明： 设完全二叉树的深度为h，则根据性质2和完全二叉树的定义有

2h－1

-1<n2h-1或2h－1

n<2h取对数h－1<log2nh，又h是整数，因此有h=log2(n)

＋1性质5：在完全二叉树中编号（1开始）为i的结点，1）若有左孩子，则左孩编号为2i；2）若有右孩子，则有孩子结点编号为2i+1；3）若有双亲，则双亲结点编号为

i/2；2i+2

2i2i+1

2i+22i+3i+1

2i2i+1iii+1二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。顺序存储结构这种存储结构适用于完全二叉树其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点二叉树的存储结构一般二叉树的顺序表示ABCDEFGHIJABDHIJEFGC顺序表示IABCFEDGH9J完全二叉树的顺序表示ABCD0EFGH0000IJ--------二叉树的顺序存储表示------------#defineMAX_TREE_SIZE100//二叉树的最大结点数

typedef

TElemType

SqBiTree[MAX_TREE_SIZE];//0号单元存放根结点

SqBiTree

bt;最坏情况：深度为k的且只有k个结点的单支树需要长度为2k-1的一维数组。链式存储结构

在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构常见的二叉树结点结构如下所示：lChild

data

rChild其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。类型定义为：

typedef

struct

BiTNode{

TElemTypedata;

struct

BiTNode

*Lchild,*Rchlid;}BTNode,*BTree;GHDEFBCA^G^^H^^D^E^F^B^CABT这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示lChilddataparentrChild

typedef

struct

TriTNode

{//结点结构

TElemType