数据结构之树和二叉树课件

第六章树和二叉树第六章树和二叉树16.1树的类型定义6.2二叉树的类型定义6.3

二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码6.1树的类型定义6.2二叉树的类型定义6.3二叉树的26.1树的类型定义6.13数据对象D：D是具有相同特性的数据元素的集合。

若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。

数据关系R：数据对象D：D是具有相同特性的数据元素的集合。若D4

基本操作：查找类

插入类删除类基本操作：查找类插入类删除类5

Root(T)//求树的根结点

查找类：Value(T,cur_e)//求当前结点的元素值

Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历Root(T)//求树的根结点查找类：Val6InitTree(&T)//初始化置空树

插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树InitTree(&T)//初始化置空树插入类：C7

ClearTree(&T)//将树清空

删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树ClearTree(&T)//将树清空删除类：De81、树（Tree)：是n个结点的有限集（n>=0)。在任意一棵非空树中，有且仅有一个特定的称为根的结点（root)；当n>1时，其余结点可分为m（m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合Ti本身又是一棵符合本定义的树，并且称为根root的子树。1、树（Tree)：是n个结点的有限集（n>=0)。在任意一9(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：树中结点的各子树之间的先后次序是有意义的，不能互换，否则就成为另一棵树了。子树之间存在确定的次序关系。无序树：树中结点的各子树之间的先后次序无意义，可以互换。子树之间不存在确定的次序关系。(１)有确定的根；有向树：有序树：树中结点的各子树之间的先10ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2树根例如:ABCDEFGHIJMKLA(B(E,F(K,L)),11树的示意图：根结点根结点叶结点分支结点子树子树子树Level1Level2Level3Level4结点的层次树的示意图：根结点根结点叶结点分支结点子树子树子树Level12对比树型结构和线性结构的结构特点对比树型结构和线性结构的结构特点13~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~14基本术语基本术语151、结点:2、结点的度:3、树的度:4、叶子结点:5、分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM（终端结点）（非终端结点）1、结点:2、结点的度:3、树的度:4、叶子结点:5、分支结166、(从根到结点的)路径：7、孩子结点、双亲结点兄弟结点、堂兄弟结点祖先结点、子孙结点8、结点的层次:9、树的深度：

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，依次加1树中叶子结点所在的最大层次6、(从根到结点的)路径：7、孩子结点、双亲结点8、结点的层17任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林10、森林：是m（m≥0）棵互不相交的树的集合。ArootBCDEFGHIJMKLF任何一棵非空树是一个二元组10、森林：是m（m≥0）棵互Ar186.2

二叉树的类型定义二叉树是树的基础，一般的树可以转化为二叉树来处理。6.219

1、二叉树的定义：

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成（即左、右子树次序不能颠倒）。ABCDEFGHK根结点左子树右子树1、二叉树的定义：二叉树或为空树，或是由一个根结点加202、二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树2、二叉树的五种基本形态：N空树只含根结点NNNLRR右子树21

二叉树的主要基本操作：查找类插入类删除类二叉树的主要基本操作：查找类插入类删除22

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());Root(T);Value(T,e);23

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);InitBiTree(&T);24ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);ClearBiTree(&T);25二叉树

的重要特性二叉树

的重要特性26

性质1：

在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：

归纳基：

归纳假设：

归纳证明：i=1

层时，只有一个根结点：

2i-1=20=1；假设对所有的j，1≤j

i，命题成立；由归纳假设知：第I-1层上至多有2i-2个结点。又因为二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1

。性质1：在二叉树的第i层上至多有27性质2：

深度为k的二叉树上至多有2k-1个结点（k≥1）。证明：[证明用求等比数列前k项和的公式]基于上一条性质，深度为k的二叉树上的结点数至多为

20+21+

+2k-1=2k-1。性质2：

深度为k的二叉树上至多有2k-128

性质3：

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n0*0+n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。性质3：

对任何一棵二叉树，若它含有n0个叶子29两类特殊形态的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcdefghij两类特殊形态的二叉树：满二叉树：指的是深度为k且含有2k-130

性质4：

具有n个结点的完全二叉树的深度为log2n+1。证明：设完全二叉树的深度为k，则由性质2和完全二叉树的定义知：深度为k-1的二叉树应该是一棵满二叉树，故结点数为2k-1-1；深度为k的完全二叉树当为满二叉树时结点数最多为2k–1。所以得2k-1-1

<n≤2k–1

2k-1≤n<2k

即k-1≤log2n<k因为k只能是整数，因此，k=log2n

+1。性质4：具有n个结点的完全二叉树的深度为31性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：

(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；

(2)若2i>n，则该结点无左孩子，

否则，编号为2i的结点为其左孩子结点；

(3)若2i+1>n，则该结点无右孩子结点，

否则，编号为2i+1的结点为其右孩子结点。性质5：若对含n个结点的完全二叉树从上到下且从左至右321、完全二叉树第3层有2个叶子，则该二叉树有多少个结点？分析：第3层最多有23-1=4个结点。完全二叉树只有3层，则前2层为满二叉树，结点数为22-1=3个结点，故总结点数=3+2=5；完全二叉树含有4层，则前3层为满二叉树，结点数为23-1=7个结点。又第3层上结点数为4，由题知其中两个为叶子，则其它（4-2）=2个结点应为内部结点。由完全二叉树的定义知：这两个结点中有一个结点的度可以为1或2，而其它结点的度必为2。综上：总结点数=7+1+（2-1）*2=10或总结点数=7+2*2=11。练习：1、完全二叉树第3层有2个叶子，则该二叉树有多少个结点？练习33作业已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点中有（m-1）个结点的度为2，其余度为1。含n个结点的完全三叉树的高度为多少？完全二叉树第7层有10个叶子，问该二叉树共有多少个结点？作业已知二叉树有50个叶子结点，则该二叉树的总结点数至少应346.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示6.3二、二叉树的链式存储表示一、二叉树的顺序存储表示35（适合存储完全二叉树）即用一组地址连续的存储单元集资从上至下，从左至右存储完全二叉树上的结点元素。也就是说，将完全二叉树上编号为i的结点存放在数组下标为（i-1)的分量中。若要存储一棵一般的二叉树，结点的存放应与完全二叉树上的结点对照，存储在数组的相应分量中。用“0”表示不存在该结点。可能会浪费很多存储空间，单支树就是一个极端情况。一、二叉树的顺序存储表示（适合存储完全二叉树）一、二叉树的顺序存储表示36完全二叉树的数组表示一般二叉树的数组表示数组表示完全二叉树的数组表示一般二叉树的数组表示数组表示37#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;C语言描述#defineMAX_TREE_SIZE10038ADEBCFrootlchilddatarchild结点结构1.二叉链表二、二叉树的顺序存储表示ADEBCFrootlchilddata39typedefstruct

BiTNode

{//结点结构TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言描述:typedefstructBiTNode{//结点40ADEBCFroot2．三叉链表parent

lchilddatarchild结点结构ADEBCFroot2．三叉链表parent41

typedefstruct

TriTNode

{//结点结构

structTriTNode

*parent;//双亲指针

structTriTNode*lchild,;//左孩子指针TElemTypedata;

structTriTNode*rchild;//右孩子指针

}TriTNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:typedefstructTriTNode{42二叉树链表表示的示例二叉树链表表示的示例436.4二叉树的遍历6.444一、遍历的概念二、先左后右的遍历算法三、算法的递归描述四、遍历算法的应用举例一、遍历的概念二、先左后右的遍历算法三、算法的递归描述四、遍45

按照某种顺序不重复地访问二叉树中的所有结点。此处的访问可以是输出、修改等操作，根据实际需要而定。

使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义可以很广，如：输出结点的信息。一、遍历的概念按照某种顺序不重复地访问二叉树中的所有结点。此处的46

“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。“遍历”是任何类型均有的操作，47对“二叉树”而言，可以有两条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；对“二叉树”而言，可以有两条搜索路径：1．先上后48二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算49

若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。遍历结果-+a*b-cd/ef先（根）序的遍历算法：若二叉树为空树，则空操作；否则，先（根）序的遍历算法：50voidPreorder(BiTreeT){if(T){//如果树不为空visit(T->data);//输出根结点Preorder(T->lchild);//先序遍历左子树Preorder(T->rchild);//先序遍历右子树}}先序voidPreorder(BiTree51

若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。遍历结果

a+b*c-d-e/f中（根）序的遍历算法：若二叉树为空树，则空操作；否则，中（根）序的遍历算法：52voidInorder(BiTreeT){if(T){//如果树不为空Inorder(T->lchild);//先序遍历左子树

visit(T->data);//输出根结点Inorder(T->rchild);//先序遍历右子树}}中序voidInorder(BiTree53

若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：遍历结果abcd-*+ef/-若二叉树为空树，则空操作；否则，后（根）序的遍历算法：遍54voidPastorder(BiTreeT){if(T){//如果树不为空

Pastorder(T->lchild);//先序遍历左子树

visit(T->data);//输出根结点Pastorder(T->rchild);//先序遍历右子树}}后序voidPastorder(BiTree55二、遍历算法的应用举例1、统计二叉树中叶子结点的个数(先序遍历)2、求二叉树的深度(后序遍历)3、建立二叉树的存储结构4、求二叉树的结点个数二、遍历算法的应用举例1、统计二叉树中叶子结点的个数2、求二561、统计二叉树中叶子结点的个数算法基本思想:分别求出左子树、右子树的叶子数，然后相加。1、统计二叉树中叶子结点的个数算法基本思想:分别求出左子57void

CountLeaf

(BiTreeT){if(!T)return0;elseif((!T->lchild)&&(!T->rchild))return1;else{nl=CountLeaf(T->lchild);nr=CountLeaf(T->rchild);returnnl+nr;

}//if}//CountLeafvoidCountLeaf(BiTreeT)582、求二叉树的深度(后序遍历)算法基本思想:从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。

首先分析二叉树的深度和它的左、右子树深度之间的关系。2、求二叉树的深度(后序遍历)算法基本思想:从二叉树深59int

Depth(BiTreeT){//返回二叉树的深度

if(!T)return0;else{dl=Depth(T->lchild);dr=Depth(T->rchild);

dep=1+(dl>dr?dl:dr);

}

return

dep;}intDepth(BiTreeT){//返回二叉603建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法3建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建61

以字符串的形式:根左子树右子树,定义一棵二叉树例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空树只含一个根结点的二叉树A以字符串“A”表示以下列字符串表示以字符串的形式:根左子树右子树,定义一62status

CreateBiTree(BiTree&T)

{scanf(&ch);

if(ch==‘')T=NULL;

else{

if(!(T=(BiTree)malloc(sizeof(BiTNode))))

exit(OVERFLOW);T->data=ch;//生成根结点

CreateBiTree(T->lchild);//构造左子树

CreateBiTree(T->rchild);//构造右子树

}

returnOK;}//CreateBiTreestatusCreateBiTree(BiTree&T)63AB

C

D

ABCD上页算法执行过程举例如下：ATBCD^^^^^ABCDABCD上页644、求二叉树的结点个数IntNodeCount(BiTreeT){if(!T)return0;else{nl=NodeCount(T->lchild);nr=NodeCount(T->rchild);returnnl+nr+1;}}4、求二叉树的结点个数IntNodeCount(BiTre65

仅知二叉树的先序序列“abcdefg”

不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树

如果同时已知二叉树的中序序列“cbdaegf”，则会如何？

二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根仅知二叉树的先序序列“abcdefg”不能唯一确定66主要思想：先序序列中第一个为“根”，标出之；在中序序列中标出“根”，并分出左、右子树；在先序序列中标出左、右子树；分别对左、右子树重复以上步骤。主要思想：67abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列abcdefgcbda68由二叉树的后序和中序序列建树二叉树的后序序列二叉树的中序序列左子树右子树根左子树右子树根主要思想：后序序列中第一个为“根”，标出之；在中序序列中标出“根”，并分出左、右子树；在后序序列中标出左、右子树；分别对左、右子树重复以上步骤。由二叉树的后序和中序序列建树二叉树的后序序列二叉树的中序序列69由二叉树的后序和先序序列能否建树？二叉树的后序序列二叉树的先序序列左子树右子树根左子树右子树根结论：不能唯一确定二叉树！ABAB或例：先序：AB后序：BA由二叉树的后序和先序序列能否建树？二叉树的后序序列二叉树的先70练习：先序：ABDEGCFH

中序：DBGEAFHC中序：DBGEAFHC

后序：DGEBHFCA画出二叉树，并写出后序序列。画出二叉树，并写出先序序列。练习：画出二叉树，并写出后序序列。画出二叉树，并写出先序序列71证明：在含有n个结点的二叉树中，含有n+1个空指针。Proof:设二叉树中度为0、1、2的结点数分别为n0,n1,n2，即n=n0+n1+n2由于二叉树中的空指针数=2n0+n1+0=n0+n0+n1由性质3知：n0=n2+1所以空指针数=n2+1+n0+n1=n+1

证毕。证明：在含有n个结点的二叉树中，含有n+1个空指针。Proo726.5

线索二叉树

何谓线索二叉树？线索链表的遍历算法如何建立线索链表？6.5

线索二叉树何谓线索二叉树？73一、何谓线索二叉树？是要借助含有n个结点的二叉树中(n+1)个空指针域，作为线索，直接指向遍历序列中“前驱”或“后继”结点。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA一、何谓线索二叉树？是要借助含有n个结点的二叉树中(n+1)74指向该线性序列中的“前驱”和“后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结构，称作“线索链表”ABCDEFGHK^D^

C^^B

E^指向该线性序列中的“前驱”和“后继”的指针，称作“线索751、对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针Link=0”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索Thread=1”

。1、对线索链表中结点的约定：在二叉链表的结点中增加两个76若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针Link=0”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索Thread=1”。

如此定义的二叉树的存储结构称作“线索链表”。若该结点的右子树不空，如此定义的二叉树的存储结构称作“线索链77typedefstruct

BiThrNod{

TElemTypedata;

structBiThrNode*lchild,*rchild;//左右指针

PointerThrLTag,RTag;//左右标志}BiThrNode,*BiThrTree;2、线索链表的类型描述：

typedef

enum{

Link,Thread

}PointerThr;

//Link==0:指针，Thread==1:线索typedefstructBiThrNod2、线索链表78二、线索链表的遍历算法:

for(p=

firstNode(T);p;p=Succ(p))Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。二、线索链表的遍历算法:for(p=firstNo79例如:对中序线索化链表的遍历算法

※中序遍历的第一个结点？

※在中序线索化链表中结点的后继？左子树上处于“最左下”（没有左子树）的结点。若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。例如:对中序线索化链表的遍历算法※中序遍历的第一80voidInOrder(BiThrTreeT,void(*Visit)(TElemTypee)){p=T->lchild;//p指向根结点

while(p!=T){

//空树或遍历结束时，p==Twhile(p->LTag==Link)p=p->lchild;//第一个结点while(p->RTag==Thread&&p->rchild!=T)

{//为右线索时找其右线索p=p->rchild;Visit(p->data);//访问后继结点

}p=p->rchild;//p进至其右子树根

}}

//InOrdervoidInOrder(BiThrTreeT,void81三、如何建立线索链表？ABDEGCFH中序遍历序列：DBEGAFHCNULLNULL方法：在遍历过程中修改空指针或先写出遍历序列，标出空指针，对照再画出线索。三、如何建立线索链表？ABDEGCFH中序遍历序列：DB82

6.6树和森林的表示方法6.6树和森林83树的三种存储结构一、双亲表示法二、孩子链表表示法三、树的二叉链表(孩子-兄弟）存储表示法树的三种存储结构一、双亲表示法二、孩子链表表示法三、树的二叉84一、双亲表示法:1、定义：用一组地址连续的空间存储树的结点，同时在每个结点中附设一个指示器指示双亲结点在链表中的位置。（即：保存结点信息和双亲的下标）一、双亲表示法:1、定义：用一组地址连续的空间存储树的结点，85ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparent2、特点：求双亲简便，求孩子麻烦。ABCDEFG0A-1r=0datap86

typedefstructPTNode{ElemTypedata;

intparent;//双亲位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:3、C语言的类型描述:typedefstructPTNode{dat87typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根结点的位置和结点个数

}PTree;树结构:typedefstruct{树结构:88二、孩子链表表示法:1、定义：把每个结点的孩子结点链成单链表。2、特点：求孩子方便，求双亲麻烦。二、孩子链表表示法:1、定义：把每个结点的孩子结点链成单链表89ABCDEFG0

A1

B2

C3

D4

E5

F6

Gr=0n=7datafirstchild123456孩子链表表示法ABCDEFG0Ar=0datafirstchi90ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparentfirstchild123456-10002243、可能把孩子链表表示法和双亲表示法结合起来。ABCDEFG0A-1r=0dataparen91typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子结点结构:

childnext4、C语言的类型描述:typedefstructCTNode{孩子结点结构:92

typedefstruct{ElemTypedata;ChildPtrfirstchild;//孩子链的头指针

}CTBox;双亲结点结构

datafirstchildtypedefstruct{双亲结点结构data93typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//结点数和根结点的位置

}CTree;树结构:typedefstruct{树结构:94三、树的二叉链表(孩子-兄弟）存储表示法1、定义：链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。2、结点结构：firstchilddatanextsibling第一个孩子下一个兄弟三、树的二叉链表(孩子-兄弟）存储表示法1、定义：链表中结95ABCDEFGABCEDFGrootABCEDFG

ABCDEFGAroot96typedefstructCSNode{TElemTypedata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;3、C语言的类型描述:结点结构:

firstchilddatanextsiblingtypedefstructCSNode{3、C语言的类型97四、树和二叉树的转换1、转换规则树的根树的第一个孩子右兄弟二叉树的根左孩子右孩子注：由树转换得到的二叉树的右子树永远为空！四、树和二叉树的转换1、转换规则二叉树的根左孩子右孩子注：98五、森林和二叉树的转换1、规则：森林中第一棵树的根变成二叉树的根森林中其它树的根当成第一棵树的根的兄弟把森林中每棵树都转化成相应的二叉树注：由森林转换得到的二叉树的右子树可能不为空！五、森林和二叉树的转换1、规则：注：由森林转换得到的二叉树99ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI1006.7树和森林的遍历6.7101一、树的遍历二、森林的遍历一、树的遍历二、森林的遍历102ABCDEFGHIJK一、树的遍历把树看成两部分：1。树的根2。根的子树森林12A一、树的遍历12103树的遍历可有三条搜索路径:按层次遍历:先根(次序)遍历:后根(次序)遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则自上而下自左至右访问树中每个结点。1、22、1树的遍历可有三条搜索路径:按层次遍历:先根(次序)遍历:后根104ABCDEFGHIJK先根遍历时顶点的访问次序：ABEFCDGHIJK后根遍历时顶点的访问次序：EFBCIJKHGDA层次遍历时顶点的访问次序：ABCDEFGHIJKA先根遍历时顶点的访问次105

BCDEFGHIJK森林中第一棵树的根结点；森林中第一棵树的子树森林；森林中其它树构成的森林。森林由三部分构成：二、森林的遍历123森林中第一棵树的根结点；森林中第一棵1061.先序遍历若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先序遍历。(1、2、3)1.先序遍历107

BCDEFGHIJK123先序遍历序列：BEFCDGHIJK123先序遍历序列：BEFCDGHI108２．中序遍历

若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中(除第一棵树之外)其

余树构成的森林。即：依次从左至右对森林中的每一棵树进行中序遍历。(2、1、3)２．中序遍历若森林不空，则即：依次从左至右对森109

BCDEFGHIJK123中序遍历序列：EFBCIJKHGD123中序遍历序列：EFBCIJKH1106.8哈夫曼树与

哈夫曼编码

几个预备概念

最优树的定义

如何构造最优树

前缀编码

6.8哈夫曼树与

哈夫曼编码111几个概念路径：树中一个结点到另一个结点所经过的分支。路径长度：路径上的分支数目。树的路径长度：从根到每一个结点的路径长度之和。（完全二叉树是路径长度最短的二叉树）ABCD几个概念路径：树中一个结点到另一个结点所经过的分支。ABCD112

一、最优树的定义结点的带权路径长度定义为：

结点的权值乘以该结点的路径长度。结点的路径长度定义为：

从根结点到该结点的路径上分支的数目。一、最优树的定义结点的带权路径长度定义为：结点的路径长度113树的带权路径长度定义为：

树中所有叶子结点的带权路径长度之和WPL(T)=wklk(对所有叶子结点)。

在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优二叉树”。例如：树的带权路径长度定义为：在所有含n个叶子结11427975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=7115用给定的n个权值构造n棵以各权值为根的二叉树。二、如何构造最优树(哈夫曼树）(1)(赫夫曼算法)以二叉树为例：问题：根据给定的n个权值{w1,w2,…,wn}，构造一棵以这些权值为叶子的哈夫曼树？用给定的n个权值构造n棵以各权值为根的二叉树。二、如何构116选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并且这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；并删去这两棵二叉树，同时加入刚新生成的二叉树；(2)(3)重复

第(2)

步，直至生成一棵树为止。选取其根结点的权值为最小的两棵二叉树，分别作为左、1179例如:已知权值W={5,6,2,9,7}5627527697671395279例如:已知权值W={5,6,2,9,7}51186713952795271667132900001111000110110111671395279527166713290000111100119

指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码码的前缀。三、前缀编码

利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即：使所传电文的总长度最短。指的是，任何一个字符的编码都三、前缀编码120有八种字符：abcdefgh，其在通信联络中出现的概率分别为：0.050.290.070.080.140.230.030.11,试设计哈夫曼遍码。

设权w=(5,29,7,8,14,23,3,11)n=8构造过程：52978142331153829781423117815292311141119291423142929232342295810000000001111111a:0000b:11c:1000d:1001e:101f:01g:0001h:001有八种字符：abcdefgh，其在通信联络中121作业以数据集{2，5，7，9，13}为权值构造一棵huffman树，并计算其带权路径长度。习题集P416.26（仅使用01编码方案）作业122按层次遍历二叉树（二叉链表）分析：使用一个队列，先将二叉树根结点入队列，然后出队，并输出该结点。若它有左孩子则左孩子入队；若有右孩子则右孩子入队，然后分别出队，直到队列为空。

按层次遍历二叉树（二叉链表）分析：123#defineMAXSIZE100structqueue{bitreev[MAXSIZE];

intfront,rear;

//队头、队尾指针}q;voidlevelorder(bitreet){q.front=q.rear=0;//初始化空队列

if(t!=NULL)printf(“%d”,t->data);

//遍历根结点

q.v[q.rear]=t;q.rear=q.rear+1;

//结点指针入队while(q.front<q.rear)//队列不空

{

s=q.v[q.front];q.front=q.front;

//队头出队if(s->lchild!=NULL)//遍历左孩子

{printf(“%d”,s->lchile->data);q.v[q.rear]=s->lchild;q.rear=q.rear+1;}if(s->rchild!=NULL)//遍历右孩子{printf(“%d”,s->rchile->data);q.v[q.rear]=s->rchild;q.rear=q.rear+1;}

}}

#defineMAXSIZE100124

1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。1.熟练掌握二叉树的结构特性，了解相应的证明方法。1254.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。4.理解二叉树线索化的实质是建立结点与其在相应序列中的1265.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握1至2种建立二叉树和树的存储结构的方法。6.学会编写实现树的各种操作的算法。7.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树127

第六章树和二叉树第六章树和二叉树1286.1树的类型定义6.2二叉树的类型定义6.3

二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码6.1树的类型定义6.2二叉树的类型定义6.3二叉树的1296.1树的类型定义6.1130数据对象D：D是具有相同特性的数据元素的集合。

若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。

数据关系R：数据对象D：D是具有相同特性的数据元素的集合。若D131

基本操作：查找类

插入类删除类基本操作：查找类插入类删除类132

Root(T)//求树的根结点

查找类：Value(T,cur_e)//求当前结点的元素值

Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历Root(T)//求树的根结点查找类：Val133InitTree(&T)//初始化置空树

插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树InitTree(&T)//初始化置空树插入类：C134

ClearTree(&T)//将树清空

删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树ClearTree(&T)//将树清空删除类：De1351、树（Tree)：是n个结点的有限集（n>=0)。在任意一棵非空树中，有且仅有一个特定的称为根的结点（root)；当n>1时，其余结点可分为m（m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合Ti本身又是一棵符合本定义的树，并且称为根root的子树。1、树（Tree)：是n个结点的有限集（n>=0)。在任意一136(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：树中结点的各子树之间的先后次序是有意义的，不能互换，否则就成为另一棵树了。子树之间存在确定的次序关系。无序树：树中结点的各子树之间的先后次序无意义，可以互换。子树之间不存在确定的次序关系。(１)有确定的根；有向树：有序树：树中结点的各子树之间的先137ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2树根例如:ABCDEFGHIJMKLA(B(E,F(K,L)),138树的示意图：根结点根结点叶结点分支结点子树子树子树Level1Level2Level3Level4结点的层次树的示意图：根结点根结点叶结点分支结点子树子树子树Level139对比树型结构和线性结构的结构特点对比树型结构和线性结构的结构特点140~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~141基本术语基本术语1421、结点:2、结点的度:3、树的度:4、叶子结点:5、分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM（终端结点）（非终端结点）1、结点:2、结点的度:3、树的度:4、叶子结点:5、分支结1436、(从根到结点的)路径：7、孩子结点、双亲结点兄弟结点、堂兄弟结点祖先结点、子孙结点8、结点的层次:9、树的深度：

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，依次加1树中叶子结点所在的最大层次6、(从根到结点的)路径：7、孩子结点、双亲结点8、结点的层144任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林10、森林：是m（m≥0）棵互不相交的树的集合。ArootBCDEFGHIJMKLF任何一棵非空树是一个二元组10、森林：是m（m≥0）棵互Ar1456.2

二叉树的类型定义二叉树是树的基础，一般的树可以转化为二叉树来处理。6.2146

1、二叉树的定义：

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成（即左、右子树次序不能颠倒）。ABCDEFGHK根结点左子树右子树1、二叉树的定义：二叉树或为空树，或是由一个根结点加1472、二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树2、二叉树的五种基本形态：N空树只含根结点NNNLRR右子树148

二叉树的主要基本操作：查找类插入类删除类二叉树的主要基本操作：查找类插入类删除149

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());Root(T);Value(T,e);150

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);InitBiTree(&T);151ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);ClearBiTree(&T);152二叉树

的重要特性二叉树

的重要特性153

性质1：

在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：

归纳基：

归纳假设：

归纳证明：i=1

层时，只有一个根结点：

2i-1=20=1；假设对所有的j，1≤j

i，命题成立；由归纳假设知：第I-1层上至多有2i-2个结点。又因为二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1

。性质1：在二叉树的第i层上至多有154性质2：

深度为k的二叉树上至多有2k-1个结点（k≥1）。证明：[证明用求等比数列前k项和的公式]基于上一条性质，深度为k的二叉树上的结点数至多为

20+21+

+2k-1=2k-1。性质2：

深度为k的二叉树上至多有2k-1155

性质3：

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n0*0+n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。性质3：

对任何一棵二叉树，若它含有n0个叶子156两类特殊形态的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcdefghij两类特殊形态的二叉树：满二叉树：指的是深度为k且含有2k-1157

性质4：

具有n个结点的完全二叉树的深度为log2n+1。证明：设完全二叉树的深度为k，则由性质2和完全二叉树的定义知：深度为k-1的二叉树应该是一棵满二叉树，故结点数为2k-1-1；深度为k的完全二叉树当为满二叉树时结点数最多为2k–1。所以得2k-1-1

<n≤2k–1

2k-1≤n<2k

即k-1≤log2n<k因为k只能是整数，因此，k=log2n

+1。性质4：具有n个结点的完全二叉树的深度为158性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：

(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；

(2)若2i>n，则该结点无左孩子，

否则，编号为2i的结点为其左孩子结点；

(3)