数据结构第5章课件-中国石油大学(华东)

11第五章树与二叉树22第五章树与二叉树5.1树的基本概念5.2二叉树5.3

二叉树的存储表示5.5线索二叉树5.6树和森林5.8哈夫曼树与哈夫曼编码5.4二叉树的遍历及其应用5.7树和森林的遍历及其应用335.1树的基本概念5.1.1树的定义和术语两种树：自由树与有根树。

①自由树： 一棵自由树Tf

可定义为一个二元组

Tf

=(V,E)

其中V={v1,...,vn}

是由n(n＞0)个元素组成的有限非空集合，称为顶点集合。E={(vi,vj)|vi,vj

V,1≤i,j≤n}

是n-1个序对的集合，称为边集合，E

中的元素(vi,vj）称为边或分支。44自由树②有根树： 一棵有根树T，简称为树，它是n(n≥0)

个结点的有限集合。当n=0时，T称为空树；否则，T

是非空树，记作

55r是一个特定的称为根(root)的结点，它只有直接后继，没有直接前驱；根以外的其他结点划分为m(m

0)个互不相交的有限集合T1,T2,…,Tm，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。6a.直观表示法：

用圆圈表示结点，元素写在圆圈中，连线表示元素之间的关系。根在上，叶子在下（即树向下生长）。acebdfg③树的常见表示方法7b.嵌套集合表示法：根据树的集合定义，写出集合划分。{a,{b,{e},{f}},

{c},

{d,{g}}}c.文氏图表示法：集合表示的一种直观表示，用图表示集合。acbefdgacebdfg直观表示法8结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数即结点拥有的子树数一棵树中各结点度数的最大值度为零的结点度大于零的结点DHIJM④树的基本术语9子女结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：(从根到结点的)路径：由从根到该结点所经分支和结点构成。ABCDEFGHIJMKL规定根结点的层次为1，它的孩子为第2层……树中叶子结点所在的最大层次1010等于根结点的高度，即根结点所有子女高度的最大值加一。高度：树的高度:有序树：无序树:森林:规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。树中结点的各棵子树T0,T1,…是有次序的，即为有序树。树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。是m（m≥0）棵树的集合。

1111二叉树的五种不同形态LLRR5.2二叉树(BinaryTree)5.2.1二叉树的定义 每个结点最多有2棵子树，且有左右之分。问：二叉树有几种可能的形态？

1212二叉树的性质性质1:

若二叉树结点的层次从1开始,则在二叉树的第i层最多有

2i-1

个结点。(i≥1)[证明用数学归纳法]性质2:

深度为k

的二叉树最少有k

个结点，最多有2k-1个结点。(k≥1)每一层最少要有1个结点，因此，最少结点数为k。最多结点个数借助性质1：用求等比级数前k项和的公式:

20+21+22+…+2k-1=2k-1问：第i层上至少有

个结点？11313性质3:

对任何一棵二叉树，如果其叶结点有n0个,度为2的非叶结点有n2个,则有

n0＝n2＋1

若设度为1的结点有n1个，总结点数为n， 总边数为e，则根据二叉树的定义，

n=n0+n1+n2

e

=2n2+n1=

n-1

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

n2=n0-1n0=n2+11414定义1:

满二叉树(FullBinaryTree)

定义2:

完全二叉树(CompleteBinaryTree)若设二叉树的深度为k，则共有k层。除第k层外，其它各层(1～k-1)的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。151231145891213571014151231145891257101234557123455问：下列哪棵二叉树为完全二叉树？1616性质4:

具有n(n≥0)个结点的完全二叉树的深度为

log2(n+1)

。

设完全二叉树的深度为k，则有

2k-1-1<n

≤2k-1

变形2k-1<n+1≤2k

取对数k-1<log2(n+1)≤k,有

log2(n+1)

=k上面k-1层结点数包括第k层的最大结点数23-124-11717性质5：如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,…,n，则有以下关系：若i=1,则i无双亲若i>1,则i的双亲为

i／2

若2*i<=n,则i的左子女为

2*i， 若2*i+1<=n,则i的右子女为2*i+1若i为奇数,且i!=1,

则其左兄弟为i-1,若

i为偶数,且i!=n,

则其右兄弟为i+11234856791018讨论：②设一棵完全二叉树具有1000个结点，则它有

个叶子结点，有

个度为2的结点，有

个结点只有非空左子树，有

个结点只有非空右子树。50049910①为什么要研究满二叉树和完全二叉树这两种特殊形式？因为只有这两种形式可以实现顺序存储！由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。易求出总层数和末层叶子数。总层数k=

log2n+1)=10;且前9层总结点数为29-1=511(完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。末层的叶子只占据了上层的245个结点（

489/2),上层（k=9)右边的0度结点数还有29-1-245=11个！195.3二叉树的存储结构5.3.2

二叉树的链式存储表示5.3.1二叉树的顺序存储表示20205.3.1二叉树的顺序表示完全二叉树的顺序表示1123456789

10

24891056731412346789

12

1412376489125101113一般二叉树的顺序表示21211371531极端情形:只有右单支的二叉树1371531顺序存储的特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树2222二叉树结点定义：每个结点有3个数据成员，data域存储结点数据，leftChild和rightChild分别存放指向左子女和右子女的指针。leftChilddatarightChilddataleftChildrightChild二叉链表5.3.2二叉树的链表表示（二叉链表）2323leftChilddataparentrightChildparentdataleftChildrightChild三叉链表二叉树的链表表示（三叉链表）每个结点增加一个指向双亲的指针parent，使得查找双亲也很方便。2424二叉树链表表示的示例

AABBCCDDFFEErootroot

ABCDFEroot二叉树二叉链表三叉链表2525二叉链表的静态结构ABCDFErootdataparentleftChildrightChild012345A

-11-1B

023C

1

-1-1D

145E

3-1-1F

3-1-12626二叉树的类定义#include<iostream.h>classBinaryTree;classBinTreeNode{

//结点类的定义friendBinaryTree;public:BinTreeNode(){leftChild=NULL;rightChild=NULL;}

BinTreeNode(DataTypex,BinTreeNode

*left=NULL,BinTreeNode*right=NULL):data(x),leftChild(left),rightChild(right){}//构造函数

~BinTreeNode(){}//析构函数private:BinTreeNode*leftChild,*rightChild;//左、右子女链域DataTypedata;//数据域};

2727classBinaryTree{public: BinaryTree():root(NULL){} BinaryTree(DataTypevalue){RefValue=value;root=NULL;} ~BinaryTree(){destroy(root);} voidCreateBinTree(){CreateBinTree(root);}为什么既定义公有函数又定义私有函数？boolIsEmpty(){return(root==NULL)?true:false;}BinTreeNode*Parent(BinTreeNode*current) {return(root==NULL||root==current)?NULL:Parent(root,current);}2828BinTreeNode*LeftChild(BinTreeNode*current) {return(current!=NULL)?current->leftChild:NULL;}BinTreeNode*RightChild(BinTreeNode*current) {return(current!=NULL)?current->rightChild:NULL;} intHeight(

){returnHeight(root);} intSize(

){returnSize(root);} BinTreeNode*GetRoot()const{returnroot;} voidpreOrder(){preOrder(root);}//前序遍历 voidinOrder(

){inOrder(root);}//中序遍历 voidpostOrder(

){postOrder(root);}//后序遍历 voidlevelOrder();//不需要递归，所以直接对外接口调用即可。层序遍历

2929private:BinTreeNode*root;//二叉树的根指针 DataTypeRefValue;//数据输入停止标志

voidCreateBinTree(BinTreeNode*&subTree) BinTreeNode*Parent(BinTreeNode*subTree,BinTreeNode*current);

intHeight(BinTreeNode*subTree); intSize(BinTreeNode*subTree); voidpreOrder(BinTreeNode*subTree);//前序遍历

voidinOrder(BinTreeNode*subTree);//中序遍历

voidpostOrder(BinTreeNode*subTree);//后序遍历

voiddestroy(BinTreeNode*&subTree);};

30305.4二叉树遍历二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问且仅访问一次。设访问根结点记作

V

遍历根的左子树记作

L

遍历根的右子树记作

R则可能的遍历次序有(只考虑先左后右)

前序VLR

中序

LVR

后序LRV

3131中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果:

a+b*c

-

d

-

e/f5.4.1二叉树遍历的递归算法

①中序遍历(InorderTraversal)--/+*abcdef3232前序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。遍历结果:

-+a*b

-

cd/ef②前序遍历(PreorderTraversal)--/+*abcdef3333后序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果:

abcd

-*+ef/-③后序遍历(PostorderTraversal)--/+*abcdef3434

voidBinaryTree::inOrder(BinTreeNode*subTree){

//私有函数，中序遍历以subTree为根的二叉树if(subTree!=NULL){ inOrder(subTree->leftChild); cout<<subTree->data; inOrder(subTree->rightChild);}}二叉树递归的中序遍历算法3535

voidBinaryTree::PreOrder(BinTreeNode*subTree){

//私有函数，前序遍历以subTree为根的二叉树if(subTree!=NULL){ cout<<subTree->data; PreOrder(subTree->leftChild); PreOrder(subTree->rightChild);}}二叉树递归的前序遍历算法3636

voidBinaryTree::PostOrder(BinTreeNode*subTree){

//私有函数，后序遍历以subTree为根的二叉树if(subTree!=NULL){ PostOrder(subTree->leftChild); PostOrder(subTree->rightChild); cout<<subTree->data;}}二叉树递归的后序遍历算法37375.4.2递归算法在树中的应用以递归方式建立二叉树。输入结点值的顺序必须对应二叉树结点完全前序遍历的顺序。约定以输入序列中不可能出现的值作为空结点的值以结束递归,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整数序列空结点。3838如图所示的二叉树的前序遍历顺序为ABC@@DE@G@@F@@@ABCDEGF@@@@@@@@39voidBinaryTree::CreateBinTree(BinTreeNode*&subTree){//私有函数:建立根为subTree的子树DataTypeitem; cin>>item; if(item!=RefValue){ subTree=newBinTreeNode(item); CreateBinTree(subTree->leftChild); CreateBinTree(subTree->rightChild);

} elsesubTree=NULL;};39^item^ABC@@DE@G@@F@@@4040BinTreeNode*BinaryTree::Parent(BinTreeNode*subTree,BinTreeNode*current){//私有函数:从结点

subTree开始,搜索结点

current的//双亲,若找到则返回双亲结点地址,否则返回NULLif(subTree==NULL)returnNULL;if(subTree->leftChild==current||

subTree->rightChild==current)

returnsubTree; //找到,返回父结点地址

returnParent(subTree->leftChild,current);returnParent(subTree->rightChild,

current); };//改错找双亲节点4141

清空树voidBinaryTree::destroy(BinTreeNode*subTree){//私有函数:删除根为subTree的子树

if(subTree!=NULL){

destroy(subTree->leftChild);//删除左子树

destroy(subTree->rightChild);//删除右子树

deletesubTree; //删除根结点

}};4242

计算二叉树深度或高度的函数intBinaryTree::Depth(constBinTreeNode*subTree)const{ if(subTree==NULL)return0;//空二叉树的深度为0 elsereturn1+Max(Depth(subTree->leftChild),Depth(subTree->rightChild));}4343

计算二叉树结点个数的函数intBinaryTree::Size(constBinTreeNode*subTree)const{//私有函数，计算根指针为subTree的二叉树中的结点个数if(subTree==NULL)return0;elsereturn}1+Size(subTree->leftChild)+Size(subTree->rightChild);44思路：①若根不为空，访问根，若右子树不为空则入栈；②若左子树不为空，则访问左子树，

若左子树为空，退栈。重复执行上述过程，直到遍历完44abcde5.4.3二叉树遍历的非递归算法

①前序遍历的非递归算法4545前序遍历的非递归算法voidBinaryTree::PreOrder(BinTreeNode*t){SeqstackS;

BinTreeNode

*p=root;

S.Push(NULL); while(p!=NULL){

cout<<p->data; //访问结点

if(p->rightChild!=NULL)S.Push(p->rightChild);//预留右指针在栈中if(p->leftChild!=NULL)p=p->leftChild; //访问左子树

elseS.Pop(p); //左子树为空

}};4646层次序遍历二叉树就是从根结点开始，按层次逐层遍历，如图：遍历顺序abcdef--+/*层次序遍历二叉树的算法4747这种遍历需要使用一个先进先出的队列，在处理上一层时，将其下一层的结点直接进到队列（的队尾）。在上一层结点遍历完后，下一层结点正好处于队列的队头，可以继续访问它们。算法是非递归的。4848abcdeQaa

进队Qa出队,访问ab进队,c

进队bcQb出队,访问bd

进队cdQc出队,访问ce

进队deQd出队,访问deQe出队,访问eP205Bug4949层次序遍历的（非递归）算法voidBinaryTree::levelOrder(){if(root==NULL)return;SeqQueue

Q;

BinTreeNode*p=root; Q.EnQueue(p);

while(!Q.IsEmpty()){Q.DeQueue(p);cout<<p->data;if(p->leftChild!=NULL){Q.EnQueue(p->leftChild);}

if(p->rightChild!=NULL){ Q.EnQueue(p->rightChild);}}};5050有0个,1个,2个,3个,4个结点的不同二叉树如下b0=1b1=1b2=2b3=5

b4=145.4.4二叉树的计数5151计算具有n个结点的不同二叉树的棵数Catalan函数bibn-i-115252例如,有3个数据{1,2,3

}，可得5种不同的二叉树。它们的前序排列均为

123，中序序列可能是321，231，213，132，123。

问题：前序序列为123，中序序列为

312

的二叉树存在吗？1231231231231235353思考：由二叉树的前序序列和中序序列可唯一地确定一棵二叉树吗？试：前序序列{ABHFDECKG}

中序序列{HBDFAEKCG

}

构造一棵二叉树HBDFEKCGAEKCGABHDF5454前序序列{ABHFDECKG}

中序序列{HBDFAEKCG

}EKCGABHDFEKCGABHFDKCGEABHFDEABHFDCKG55555.5线索化二叉树

(ThreadedBinaryTree)又称为穿线树。通过二叉树的遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。5656线索(Thread)bdaec增加前驱Pred指针和后继Succ指针的二叉树predleftChilddatarightChildsuccabcdepredpredpredsuccsuccsuccD∧∧AE∧∧B∧∧C∧∧rootpredpredpredpredsuccsuccsuccsucc5757缺点：每个结点增加两个指针，当结点数很大时存储消耗较大。改造树结点，将pred指针和succ指针压缩到leftChild和rightChild的空闲指针中，并增设两个标志ltag和rtag，指明指针是指示子女还是前驱／后继。后者称为线索。ltag(或rtag)=0，表示相应指针指示左子女（或右子女结点）；当ltag(或rtag)=1,表示相应指针为前驱（或后继）线索。leftChildltagdatartagrightChild

5858leftChildltagdatartagrightChild

abcdepredpredpredsuccsuccsuccDAEB∧C∧rootpredpredsuccsucc0000111111线索化二叉树及其链表表示bdaec5959if(current->rtag==1)

后继为current->rightChildelse//current->rtag==0

后继为当前结点右子树的中序下的第一个结点

寻找当前结点在中序下的后继ABDECFHIKGJ6060寻找当前结点在中序

下的前驱if(current->ltag==1)

前驱为current->leftChildelse//current->ltag==0

前驱为当前结点左子树

中序下的最后一个结点

ABDECFHIKGJL61615.6.1树的存储表示5.6树与森林ABCDEFGdataparentABCDEFG-100011301234561.双亲表示：找双亲容易

树中结点的存放顺序一般不做特殊要求，但为了操作实现的方便，有时也会规定结点的存放顺序。例如，可以规定按树的前序次序存放树中的各个结点，或规定按树的层次次序安排所有结点。

62622.子女(孩子)链表表示：找孩子容易无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG012345663633.孩子-兄弟表示法：找孩子容易也称为树的二叉树表示。结点构造为：firstChild指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。nextSibling指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。若想找某结点的所有子女，可先找firstChild,再反复用nextSibling沿链扫描。

datafirstChildnextSibling6464树的子女-

兄弟表示

datafirstChildnextSiblingABCDEFGABCDGFE6565树的二叉树表示5.7树的遍历①深度优先遍历先根次序遍历后根次序遍历②广度优先遍历ABCDEFGABCEDGF6666ABCEDGF树的先根次序遍历当树非空时访问根结点依次先根遍历根的各棵子树树先根遍历：对应二叉树前序遍历：树的先根遍历结果与其对应二叉树表示的前序遍历结果相同树的先根遍历可以借助对应二叉树的前序遍历算法实现ABCDEFGABEFCDGABEFCDG6767ABCEDGF树的后根次序遍历当树非空时

依次后根遍历根的各棵子树访问根结点树后根遍历：对应二叉树中序遍历：树的后根遍历结果与其对应二叉树表示的中序遍历结果相同树的后根遍历可以借助对应二叉树的中序遍历算法实现ABCDEFGEFBCGDAEFBCGDA6868广度优先（层次次序）遍历按广度优先次序遍历树的结果

ABCDEFG遍历算法用到一个队列。ABCEDGFABCDEFG6969

将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。森林与二叉树表示的转换可以借助树的二叉树表示来实现。5.6.2森林与二叉树的转换7070T1T2T3AT1T2T3AFHBCDGIJEKFBCDEGHIKJABCEDHIKJFG3

棵树的森林各棵树的二叉树表示森林的二叉树表示1.森林转化成二叉树71712.二叉树转换为森林T1T2T3AFHBCDGIJEKABCEDHIKJFG5.7森林的遍历森林的遍历也分为深度优先遍历和广度优先遍历，深度优先遍历又可分为先根次序遍历和后根次序遍历。7373森林的先根次序遍历的结果序列:

ABCDEFGHIKJ对应二叉树的前序遍历结果：ABCEDHIKJFGT1T2T3AFHBCDGIJEK7474ABCEDHIKJFG森林的后根次序遍历的结果序列:

BCEDAGFKIJH对应二叉树中序遍历的结果：T1T2T3AFHBCDGIJEK7575广度优先遍历（层次序遍历）AFHBCDGIJEK若森林F

为空，返回；否则：①依次遍历各棵树的根结点；②依次遍历各棵树根结点的所有子女；③依次遍历这些子女结点的子女结点；

T1T2T3AFHBCDGIJEK76765.8Huffman树路径长度(PathLength)

两个结点之间的路径长度PL

是连接两结点的路径上的分支数。树的外部路径长度是各叶结点（外结点）到根结点的路径长度之和EPL。树的内部路径长度是各非叶结点（内结点）到根结点的路径长度之和IPL。树的路径长度PL=EPL+IPL。77771122334455667788IPL=0+1+1+2=4EPL=2+2+2+3=9PL=13IPL=0+1+2+3=6EPL=1+2+3+4=10PL=167878在很多应用问题中为树的叶结点赋予一个权值，用于表示出现频度、概率值等，称为扩充二叉树。若一棵扩充二叉树有n个外结点，第i个外结点的权值为wi，它到根的路径长度为li，则该外结点到根的带权路径长度为wi*li。扩充二叉树的带权路径长度定义为树的各外结点到根的带权路径长度之和。2457带权路径长度

(WeightedPathLength,WPL)7979具