数据结构清华大学殷人昆演示文稿

数据结构清华大学殷人昆演示文稿1现在是1页\一共有201页\编辑于星期五数据结构清华大学殷人昆2现在是2页\一共有201页\编辑于星期五树的定义与基本概念二叉树二叉树遍历二叉树的计数线索二叉树树与树的遍历树的应用第4章树与二叉树现在是3页\一共有201页\编辑于星期五树和森林的概念树的定义

树是由n(n＞0)个结点组成的有限集合：有一个特定的称之为根(root)的结点；除根以外的其它结点划分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm，每个集合又是一棵树，并且称之为根的子树。此定义是离散数学和图论中给出的。它们把树视为图的一个极小连通子图。有n个结点的树有n-1条边，而且不能有回路。现在是4页\一共有201页\编辑于星期五这种观点的典型代表是

Knuth。他认为图至少有一个顶点，树也必须至少有一个顶点。树不能是空树，但N叉树可以是空树。N叉树是限制根的子树最多不能超过N棵的树。随着对树讨论的深入，人们放宽了对树结构的限制。若把树当作层次结构单独对待，树中允许结点个数为0。这样，树与N叉树就没有不可逾越的鸿沟了。从面向对象观点，N叉树是树的特殊实现：树是父类，N叉树是子类。N叉树继承了树的特性，它还有自己增加的特性，例如现在是5页\一共有201页\编辑于星期五理论上树不可是空树，N叉树可以是空树；树的子树可以有序，也可以不要求有序，而N叉树的子树必须有序。N叉树的定义也是递归的，递归到空树终止；树则递归到只有一个结点的子树。树的子树棵数不限，而N叉树中根的子树最多N棵。树可以区分为外向树和内向树，而N叉树一般是外向树，即边是有向的，从父指向子。树可以用N叉树实现。二叉树、B树等又都是N叉树的特殊情形。现在是6页\一共有201页\编辑于星期五树的特点树是分层结构，又是递归结构。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。1层2层4层3层depth=4height=4ACGBDEFKLHMIJ前驱后继现在是7页\一共有201页\编辑于星期五1层2层4层3层depth=4height=4ACGBDEFKLHMIJ结点结点的度分支结点叶结点子女双亲兄弟祖先树的度树深度树高度森林子孙结点层次结点深度结点高度现在是8页\一共有201页\编辑于星期五注意，结点的深度和结点的高度是不同的。结点的深度即结点所处层次，是从根向下逐层计算的；结点的高度是从下向上逐层计算的：叶结点的高度为1,其他结点的高度是取它的所有子女结点最大高度加一。树的深度与高度相等。 树的深度按离根最远的 叶结点算，树的高度按 根结点算，都是6。叶结点也称为终端结点， 非叶结点也称为非终端 结点。ABCDEFGHILKJ高度=4深度=3现在是9页\一共有201页\编辑于星期五二叉树的五种不同形态LLRR二叉树(BinaryTree)二叉树的定义

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。这个定义是递归的。现在是10页\一共有201页\编辑于星期五二叉树的性质性质1

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

个结点。(i≥1)[证明用数学归纳法]i=1时，根结点只有1个，21-1=20=1；若设i=k

时性质成立，即该层最多有2k-1

个结点，则当i=k+1

时，由于第k

层每个结点最多可有2个子女，第k+1层最多结点个数可有2*2k-1=2k

个，故性质成立。现在是11页\一共有201页\编辑于星期五性质2高度为h的二叉树最多有2h

-1个结点。(h≥1)[证明用求等比级数前k项和的公式] 高度为h的二叉树有h

层，各层最多结点个数相加，得到等比级数，求和得： 20+21+22+…+2h-1=2h-1

空树的高度为0，只有根结点的树的高度为1。现在是12页\一共有201页\编辑于星期五性质3

对任何一棵二叉树,如果其叶结点有

n0

个,度为2的非叶结点有

n2

个,则有

n0＝n2＋1证明： 若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，

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

2n2+n1=n0+n1+n2-1

n2=n0-1n0=n2+1

引申：可用于判断二叉树各类结点个数。现在是13页\一共有201页\编辑于星期五定义1

满二叉树(FullBinaryTree)

定义2

完全二叉树(CompleteBinaryTree)若设二叉树的高度为h，则共有h

层。除第

h

层外，其它各层(1～h-1)的结点数都达到最大个数，第h

层从右向左连续缺若干结点，这就是完全二叉树。现在是14页\一共有201页\编辑于星期五性质4

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

log2(n+1)

证明：设完全二叉树的高度为h，则有

2h-1-1＜n

≤2h-1

上面h-1层结点数

包括第h层的最大结点数变形 2h-1＜n+1≤2h

取对数

h-1＜log2(n+1)≤h

有 h=log2(n+1)

23-124-1现在是15页\一共有201页\编辑于星期五23-124-1注意：求高度的另一公式为log2n+1,此公式对于n=0

不适用。若设完全二叉树中叶结点有n0

个,则该二叉树总的结点数为n=2n0,或n=2n0–1。若完全二叉树的结点数为奇数，没有度为1的结点；为偶数，有一个度为1的结点。右图为理想平衡树， 上层都是满的，第

h层结点分布在各 处。现在是16页\一共有201页\编辑于星期五性质5

如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号:0,1,2,…,n-1，则有以下关系：

若i=0,则i无双亲； 若i>0,则i的双亲为(i-1)/2。若2*i+1<n,则

i

的左子女为2*i+1； 若2*i+2<n,则i的右子女为2*i+2。若i

为偶数,且i!=0,则 其左兄弟为i-1； 若i

为 奇数,且i!=n-1,

则其右兄弟为i+1。0123745689现在是17页\一共有201页\编辑于星期五注意：

如果完全二叉树各层次结点从1开始编号：1,2,3,…,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+1。12348567910现在是18页\一共有201页\编辑于星期五完全二叉树一般二叉树的顺序表示的顺序表示00123456789130123567811131378945620126537811491012二叉树的顺序表示现在是19页\一共有201页\编辑于星期五02614300261430极端情形:只有右单支的二叉树对于完全二叉树，因结点编号连续，数据存储密集，适于用顺序表示；对于一般二叉树，用链表表示较好；现在是20页\一共有201页\编辑于星期五lchilddatarchilddatalchildrchild左子女指针右子女指针二叉树的二叉链表表示使用二叉链表，找子女的时间复杂度为O(1)，找双亲的时间复杂度为O(log2i)～O(i)，其中，i

是该结点编号。现在是21页\一共有201页\编辑于星期五lchilddataparentrchildparentdatalchildrchild左子女指针双亲指针右子女指针二叉树的三叉链表表示使用三叉链表，找子女、双亲的时间都是O(1)。现在是22页\一共有201页\编辑于星期五AAABBBCCCDDDFFFEEErootrootroot二叉树二叉链表三叉链表二叉树链表表示的示例现在是23页\一共有201页\编辑于星期五二叉树的定义typedefcharTElemType; //树结点数据类型typedefstructnode{ //树结点定义

TElemType

data; //结点数据域

structnode*lchild,*rchild;

//子女指针域}BiTNode;typedefBiTNode*BinTree;

//树定义，代表树的根指针

现在是24页\一共有201页\编辑于星期五二叉树遍历树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作V，遍历根的左子树记作L，遍历根的右子树记作R，则可能的遍历次序有前序VLR镜像VRL中序LVR镜像RVL后序LRV镜像RLV

现在是25页\一共有201页\编辑于星期五中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果

a+b*c-d-e/f中序遍历(InorderTraversal)--/+*abcdef现在是26页\一共有201页\编辑于星期五二叉树递归的中序遍历算法voidInOrder(BiTNode*T){

if(T!=NULL){InOrder(T->lchild);visit(T->data);InOrder(T->rchild);

}}visit()是输出数据值的操作，在实际使用时可用相应的操作来替换。现在是27页\一共有201页\编辑于星期五前序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。遍历结果

-+a*b-cd/ef前序遍历(PreorderTraversal)--/+*abcdef现在是28页\一共有201页\编辑于星期五二叉树递归的前序遍历算法voidPreOrder(BiTNode*T){

if(T!=NULL){visit(T->data);PreOrder(T->lchild);PreOrder(T->rchild);

}}与中序遍历算法相比，visit()

操作放在两个子树递归前序遍历的最前面。现在是29页\一共有201页\编辑于星期五后序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果

abcd-*+ef/-后序遍历(PostorderTraversal)d--/+*abcdef现在是30页\一共有201页\编辑于星期五二叉树递归的后序遍历算法voidPostOrder(BiTNode*T){

if(T!=NULL){PostOrder(T->lchild);PostOrder(T->rchild);visit(T->data);

}}与中序遍历算法相比，visit()

操作放在两个子树递归前序遍历的最后面。现在是31页\一共有201页\编辑于星期五计算二叉树结点个数的递归算法应用二叉树遍历的事例intCount(BiTNode*T){

if(T==NULL)return0;

else

return1+Count(T->lchild)+Count(T->rchild);}空二叉树的结点个数为0，可直接计算；否则可分别计算左、右子树的结点个数，再相加得到总结点个数。现在是32页\一共有201页\编辑于星期五求二叉树高度的递归算法intHeight(BiTNode*T){if(T==NULL)return0;

else{intm=

Height(T->lchild);intn=

Height(T->rchild));return(m>n)?m+1:n+1;

}空树的高度为0；非空树情形，先计算根结点左右子树的高度，取大者再加一得到二叉树高度。现在是33页\一共有201页\编辑于星期五abcecdcc访问a进栈c左进b访问b进栈d左进空退栈d访问d左进空退栈c访问c左进e访问e左进空退栈结束利用栈的前序遍历的非递归算法ddc现在是34页\一共有201页\编辑于星期五voidPreOrder(BinTreeT){stackS;InitStack(S);

//递归工作栈

BiTNode*p=T;Push(S,NULL);

while(p!=NULL){visit(p->data);if(p->rchild!=NULL)Push(S,p->rchild);if(p->lchild!=NULL)p=p->lchild; //进左子树

elsePop(S,p); //左子树空,进右子树

}}

现在是35页\一共有201页\编辑于星期五abcdebaadaa左空退栈访问左空退栈访问退栈访问左空ec退栈访问cc右空退栈访问栈空结束利用栈的中序遍历的非递归算法现在是36页\一共有201页\编辑于星期五

voidInOrder(BinTreeT){stackS;InitStack(S);//递归工作栈

BiTNode*p=

T;

//初始化

do{

while(p!=NULL) //子树非空找中序第一个

{Push(S,p);p=p->lchild;}//边找边进栈

if(!StackEmpty(S)){

//栈非空

Pop(S,p);//子树中序第一个退栈

visit(p->data);

//访问之

p=p->rchild; //向右子树走

}

}while(p!=NULL||!StackEmpty(S));}现在是37页\一共有201页\编辑于星期五后序遍历时使用的栈的结点定义

typedefstruct

{ BiTNode*ptr; //结点指针

enumtag{L,R};//该结点退栈标记 }StackNode;

根结点的tag=L，表示从左子树退出,访问右子树。tag=R,表示从右子树退出,访问根。ptrtag{L,R}

利用栈的后序遍历的非递归算法现在是38页\一共有201页\编辑于星期五abcdeaLbLaLbRaLdLbRaLdRbRaLbRaLaLaReLcLaReRcLaRcLaRcRaRaR现在是39页\一共有201页\编辑于星期五利用栈的后序遍历的非递归算法voidPostOrder(BinTreeT){stackS;InitStack(S);StackNode

w;BiTNode*p=T;

do{

while(p!=NULL){ //向左子树走

w.ptr=p;w.tag=L;Push(S,w);

p=p->lchild; }

intsucc=1; //继续循环标记现在是40页\一共有201页\编辑于星期五

while(succ&&!StackEmpty(S)){Pop(S,w);p=w.ptr;

switch(w.tag){

//判断栈顶tag标记

caseL:w.tag=R;Push(S,w); succ=0;

p=p->rchild;break; caseR:visit(p->data);

}}}

while(!StackEmpty(S));}现在是41页\一共有201页\编辑于星期五二叉树的计数由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例,前序序列

{ABHFDECKG}和中序序列

{HBDFAEKCG},构造二叉树过程如下：HBDFEKCGAEKCGABHDF现在是42页\一共有201页\编辑于星期五KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG现在是43页\一共有201页\编辑于星期五612345789612375849如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。问题是：固定前序排列，选择所有可能的中序排列，可以构造出多少种不同的二叉树？现在是44页\一共有201页\编辑于星期五123123123123123例如,有3个数据{1,2,3}，可得5种不同的二叉树。它们的前序排列均为123，中序序列可能是123，132，213，231，321。那么，如何推广到一般情形呢？首先，只有一个结点的不同二叉树只有一个；有2个结点的不同二叉树只有2种，其他情况呢？现在是45页\一共有201页\编辑于星期五b0=1b1=1b2=2b3=5

b4=14有0个,1个,2个,3个结点的不同二叉树如下现在是46页\一共有201页\编辑于星期五bibn-i-11计算具有n个结点的不同二叉树的棵数Catalan函数例现在是47页\一共有201页\编辑于星期五线索二叉树(ThreadedBinaryTree)又称为穿线树。通过二叉树遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。为此，在二叉树存储结点中增加线索信息。现在是48页\一共有201页\编辑于星期五线索(Thread)增加前驱Pred指针和后继Succ指针的二叉树predlchilddatarchildsuccabcdepredpredpredsuccsuccsuccD∧∧AE∧∧B∧∧C∧∧rootpredpredpredpredsuccsuccsuccsucc现在是49页\一共有201页\编辑于星期五这种设计的缺点是每个结点增加两个指针，当结点数很大时存储消耗较大。改造树结点，将pred指针和succ指针压缩到lchild和rchild的空闲指针中，并增设两个标志ltag和rtag，指明指针是指示子女还是前驱／后继。后者称为线索。ltag(或rtag)=0，表示相应指针指示左子女（或右子女结点）；ltag(或rtag)=1,表示相应指针为前驱（或后继）线索。lchildltagdatartagrchild

现在是50页\一共有201页\编辑于星期五中序线索二叉树及其链表表示lchildltagdatartagrchild

abcdepredpredpredsuccsuccsuccDAEB∧C∧rootpredpredsuccsucc0000111111现在是51页\一共有201页\编辑于星期五typedefintTTElemType;typedefstructnode{

intltag,rtag;

structnode*lchild,*rchild;

TTElemTypedata;}ThreadNode,*ThreadTree;注意，线索二叉树在树结点中增加了ltag和rtag，改变了二叉树的结构。线索二叉树的结构定义现在是52页\一共有201页\编辑于星期五通过中序遍历建立中序线索二叉树voidInThread(ThreadNode*t,

ThreadNode*&pre){

//预设了一个pre指针，指示t的中序前驱，在主

//程序中预置为NULL

if(t!=NULL){ InThread(t->lchild,pre);

//递归,左子树线索化

if(t->lchild==NULL){ t->lchild=pre;t->ltag=1;}

//建立当前结点t的前驱线索

现在是53页\一共有201页\编辑于星期五

if(pre&&pre->rchild==NULL){pre->rchild=t;pre->rtag=1;

}

//建立前驱结点pre的后继线索

pre=t; //前驱跟上当前指针

InThread(t->rchild,pre);

//递归,右子树线索化

}}使用此函数可以把以t为根的子树一次中序线索化，但中序下最后一个结点的后继线索没有加上，指针

pre

在退出时正在指示这一结点。现在是54页\一共有201页\编辑于星期五voidCreateInThread(ThreadTreeT){ThreadNode*pre=NULL; //前驱指针

if(T!=NULL){

//树非空,线索化

InThread(T,pre); //中序遍历线索二叉树

pre->rchild=NULL;pre->rtag=1;

//后处理,中序最后一个结点

}}通过该主程序实现了对二叉树的中序线索化。它是基于二叉树的中序遍历实现的。现在是55页\一共有201页\编辑于星期五0A00B0

0C00D00E0Tpre==NULLt现在是56页\一共有201页\编辑于星期五0A0

1B0

0C00D00E0Tpre==NULLt现在是57页\一共有201页\编辑于星期五0A0

1B0

0C0

1D00E0Tpret现在是58页\一共有201页\编辑于星期五0A0

1B0

0C0

1D1

0E0Tpret现在是59页\一共有201页\编辑于星期五0A0

1B0

0C0

1D1

1E0Tpret现在是60页\一共有201页\编辑于星期五0A0

1B0

0C0

1D1

1E1

Tpret现在是61页\一共有201页\编辑于星期五0A0

1B0

0C1

1D1

1E1

Tpre后处理现在是62页\一共有201页\编辑于星期五寻找结点p在中序下的后继if(p->rtag==1)

后继为

p->rchildelse

//p->rtag!=1

后继为结点

p右子树

q中的中序下的第一个结点ABDECFHIKGJ现在是63页\一共有201页\编辑于星期五ThreadNode

*First(ThreadNode

*t){//函数返回以*t为根的线索二叉树中的中序序列下//的第一个结点

ThreadNode*p=t;

while(p->ltag==0)p=p->lchild;

returnp; //最左下的结点}ThreadNode*Next(ThreadNode

*p){//函数返回在线索二叉树中结点*p在中序下的后//继结点现在是64页\一共有201页\编辑于星期五

if(p->rtag==0)returnFirst(p->rchild);

//p->rtag==0,后继为右子树中序第一个结点

else

returnp->rchild;

//p->rtag==1,直接返回后继线索}voidInorder(ThreadNode*t){//以t为根的线索二叉树的中序遍历

ThreadNode*p;for(p=First(t);p!=NULL;p=Next(p))

cout<<p->data<<endl;}

现在是65页\一共有201页\编辑于星期五寻找结点p在中序下的前驱if(p->ltag==1)

前驱为

p->lchildelse

//p->leftThread==0

前驱为结点

p

左子树中序下的最后一个结点ABDECFHIKGJL现在是66页\一共有201页\编辑于星期五前序序列

ABDCEp->ltag==1?前驱线索

=左子女p->rchild==NULL后继为p->lchild=无后继

后继为p->rchildABCED前序线索二叉树在前序线索二叉树中寻找当前结点的后继现在是67页\一共有201页\编辑于星期五后序序列

DBECAp->rtag==1?后继线索

=右子女后继为q的右子树中后序下第一个结点

后继为p->rchild=无后继

后继为qABCEDq=p->parentq==NULL?q->rtag==1||q->rchild==p?=后序线索二叉树在后序线索二 叉树中寻找当 前结点的后继现在是68页\一共有201页\编辑于星期五树的存储表示

双亲表示为了操作实现的方便，有时会规定结点的存放顺序。例如，可以按树的前序次序存放树中的各个结点，或按树的层次次序安排所有结点。树与树的遍历ABCDEFGdataparentABCDEFG-10001130123456现在是69页\一共有201页\编辑于星期五子女链表表示无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG0123456现在是70页\一共有201页\编辑于星期五子女指针表示一个合理的想法是在结点中存放指向每一个子女结点的指针。但由于各个结点的子女数不同，每个结点设置数目不等的指针，将很难管理。为此，设置等长的结点，每个结点包含的指针个数相等，等于树的度（degree）。这保证结点有足够的指针指向它的所有子女结点。但可能产生很多空闲指针，造成存储浪费。现在是71页\一共有201页\编辑于星期五等数量的链域ABCDEFG

datachild1child2child3childdABCDEFG空链域2n+1个现在是72页\一共有201页\编辑于星期五子女-兄弟表示也称为树的二叉树表示。结点构造为：firstChild指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。nextSibling指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。若想找某结点的所有子女，可先找firstChild,再反复用nextSibling沿链扫描。

datafirstChildnextSibling现在是73页\一共有201页\编辑于星期五树的左子女-

右兄弟表示

datafchildnsiblingABCDEFGABCDGFE现在是74页\一共有201页\编辑于星期五左子女-右兄弟表示的树的结构定义typedefintTElemType;typedefstructnode{

TElemTypedata;

structnode*fchild,*nsibling;}CSNode,*CSTree;注意，虽然此定义与二叉树的类似，操作也类似，但语义是不同的。树结构是递归的，可用递归函数实现相应操作。现在是75页\一共有201页\编辑于星期五寻找双亲子女兄弟的操作TreeNode*FindParent(CSNode*T,CSNode*p){//在以T为根的树中找结点p的双亲

if(T==NULL||p==NULL)returnNULL;CSNode*q=T->fchild,*s;

while(q!=NULL&&q!=p){

//循根的长子的兄弟链,递归在子树中搜索

if((s=FindParent(q,p))!=NULL)returns;

//在以q为根的子树找到p的双亲，返回

q=q->nsibling;

}现在是76页\一共有201页\编辑于星期五

if(q!=NULL&&q==p)returnT;//找到双亲

elsereturnNULL;//未找到双亲}TreeNode*FindfirstChild(CSNode*p){//在树中找结点p的第一个子女

if(p!=NULL)returnp->fchild;

else

returnNULL;};TreeNode*FindnextSibling(CSNode*p){//在树中找结点p的兄弟现在是77页\一共有201页\编辑于星期五

if(p!=NULL

)returnp->nsibling;

elsereturnNULL;}深度优先遍历先根次序遍历后根次序遍历广度优先遍历树的遍历ABCDEFGABCEDGF二叉树表示现在是78页\一共有201页\编辑于星期五当树非空时访问根结点依次先根遍历根的各棵子树树先根遍历ABEFCDG 对应二叉树前序遍历ABEFCDG树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同树的先根遍历可以借助对应二叉树的前序遍历算法实现ABCEDGF树的先根次序遍历ABCDEFG现在是79页\一共有201页\编辑于星期五树的先根次序遍历的递归算法voidPreOrder

(CSNode*t){ //以指针t为根,先根次序遍历

if(t!=NULL){visit(t->data);

//访问根结点

CSNode*p

=t->fchild;

//第一棵子树

while(p!=NULL){

PreOrder(p); //递归先根遍历子树

p=p->nsibling;}}}现在是80页\一共有201页\编辑于星期五当树非空时依次后根遍历根的各棵子树访问根结点树后根遍历EFBCGDA 对应二叉树中序遍历EFBCGDA树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同树的后根遍历可以借助对应二叉树的中序遍历算法实现ABCEDGF树的后根次序遍历ABCDEFG现在是81页\一共有201页\编辑于星期五树的后根次序遍历的递归算法voidPostOrder(CSNode*t){//以指针t为根,按后根次序遍历树

if(t!=NULL){CSNode

*p=t->fchild;while(p!=NULL){ PostOrder(p);

p=p->nsibling;

}visit(t->data); //最后访问根结点

}}现在是82页\一共有201页\编辑于星期五按广度优先次序遍历树的结果

ABCDEFG广度优先遍历算法 voidLevelOrder(CSTreeT){

//分层遍历树，算法用到一个队列

QueueQ;InitQueue(Q);

CSNode*p; if(T!=NULL){ //树不空

EnQueue(Q,T); //根结点进队列广度优先(层次次序)遍历ABCEDGFABCDEFG现在是83页\一共有201页\编辑于星期五

while(!QueueEmpty(Q)){

DeQueue(Q,p);visit(p->data);

//队列中取一个并访问之

p=p->fchild;

//待访问结点的子女结点进队列

while(p!=NULL){

EnQueue(Q,p);p=p->nsibling;

}}

}}现在是84页\一共有201页\编辑于星期五森林与二叉树的转换将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。森林与二叉树表示的转换可以借助树的二叉树表示来实现。现在是85页\一共有201页\编辑于星期五T1T2T3AFHT1T2T3ABCDGIJEKFBCDEGHIKJABCEDHIKJFG3

棵树的森林各棵树的二叉树表示森林的二叉树表示现在是86页\一共有201页\编辑于星期五森林转化成二叉树的规则若F为空，即n=0，则对应的二叉树B为空树。若F不空，则二叉树B的根是F第一棵树T1

的根；其左子树为B(T11,T12,…,T1m)，其中，T11,T12,…,T1m

是T1的根的子树；其右子树为B(T2,T3,…,Tn)，其中，T2,T3,…,Tn

是除

T1

外其它树构成的森林。现在是87页\一共有201页\编辑于星期五二叉树转换为森林的规则如果B为空，则对应的森林F也为空。如果B非空，则F中第一棵树T1

的根为B的根；T1的根的子树森林{T11,T12,…,T1m}

是由B的根的左子树LB转换而来；F中除了T1

之外其余的树组成的森林{T2,T3,…,Tn}

是由B的根的右子树RB转换而成的森林。现在是88页\一共有201页\编辑于星期五例题设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为m1，m2和m3。那么在由该森林转化成的二叉树中根结点的右子树上有（）个结点。 A.m1+m2 B.m2+m3 C.m3+m1 D.m1+m2+m3【解答】在由森林转化成的二叉树中根结点的右子树上的结点是除第一棵外其他树上的结点，应有m2+m3个，故选择B。

现在是89页\一共有201页\编辑于星期五森林的遍历森林的遍历也分为深度优先遍历（包括先根次序遍历和中根次序遍历）和广度优先遍历。深度优先遍历给定森林F，若F=Ø，则遍历结束。否则若F={{T1={r1,T11,…,T1k},T2,...,Tm}，则可以导出先根遍历、中根遍历两种方法。其中，r1是第一棵树的根结点，{T11,…,T1k}是第一棵树的子树森林，{T2,...,Tm}是除去第一棵树之后剩余的树构成的森林。现在是90页\一共有201页\编辑于星期五若森林F=Ø，返回；否则访问森林的根（也是第一棵树的根）r1；先根遍历森林第一棵树的根的子树森林{T11,…,T1k}；先根遍历森林中除第一棵树外其他树组成的森林{T2,...,Tm}。注意，②是一个循环，对于每一个T1i，执行树的先根次序遍历；③

是一个递归过程，重新执行T2

为第一棵树的森林的先根次序遍历。森林的先根次序遍历现在是91页\一共有201页\编辑于星期五森林的先根次序遍历的结果序列

ABCDEFGHIKJ这相当于对应二叉树的前序遍历结果。T1T2T3AFHBCDGIJEKBAEDHIKJFGC现在是92页\一共有201页\编辑于星期五森林的中根次序遍历若森林F=Ø，返回；否则中根遍历森林

F

第一棵树的根结点的子树森林{T11,…,T1k}；访问森林的根结点r1；中根遍历森林中除第一棵树外其他树组成的森林{T2,...,Tm}。注意，与先根次序遍历相比，访问根结点的时机不同。所以在③的情形，对以T2为第一棵树的森林遍历时，重复执行①②③的操作。现在是93页\一共有201页\编辑于星期五森林的中根次序遍历的结果序列

BCEDAGFKIJH这相当于对应二叉树中序遍历的结果。T1T2T3AFHBCDGIJEKBAEDHIKJFGC现在是94页\一共有201页\编辑于星期五广度优先遍历（层次序遍历）AFHBCDGIJEKABCEDHIKJFG若森林F

为空，返回； 否则依次遍历各棵树的 根结点；依次遍历各棵树根 结点的所有子女；依次遍历这些子女 结点的子女结点；现在是95页\一共有201页\编辑于星期五树的应用二叉排序树平衡二叉树Huffman树堆并查集现在是96页\一共有201页\编辑于星期五二叉排序树(BinarySearchTree)定义

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：每个结点都有一个作为查找依据的关键字(key)，所有结点的关键字互不相同。左子树（如果非空）上所有结点的关键字都小于根结点的关键字。右子树（如果非空）上所有结点的关键字都大于根结点的关键字。左子树和右子树也是二叉排序树。现在是97页\一共有201页\编辑于星期五351545504025102030二叉排序树例结点左子树上所有关键 字小于结点关键字；结点右子树上所有关键 字大于结点关键字；如果对一棵二叉排序树 进行中序遍历，可以按 从小到大的顺序将各结 点关键字排列起来。注意，国外教材统称为二叉搜索树或二叉查找树。现在是98页\一共有201页\编辑于星期五例题一棵二叉树是二叉排序树的（）条件是树中任一结点的关键字值都大于左子女的关键字值，小于右子女的关键字值。 A.充分但不必要B.必要但不充分C.充分且必要D.既不充分也不必要【解答】B。 通俗来讲，必要条件是指符合定义则必具有后续讲的特性。显然一棵二叉树是二叉排序树，则树中任一结点的关键字值一定大于左子女的关键字值，小于右子女的关键字值。充分条件是指满足现在是99页\一共有201页\编辑于星期五

后续讲的特性则定义一定成立。就是说，如果一棵二叉树任一结点的关键字值都大于左子女的关键字值，小于右子女的关键字值，则它一定是二叉排序树。这就不一定了。

右图描述的二叉树满足树中 任一结点的关键字值一定大 于左子女的关键字值，小于 右子女的 关键字值，但它不 是二叉排序树。2515353045102050现在是100页\一共有201页\编辑于星期五

二叉排序树的结构定义typedefcharBSTElemType; //树结点数据类型typedefstructnode{ //二叉排序树结点

BSTElemType

data;

structnode*lchild,*rchild;}BSTNode,*BSTree; //二叉排序树定义从面向对象观点来看，二叉排序树是二叉树的特殊情形，它继承了二叉树的结构，增加了自己的特性，对数据的存放增加了约束。现在是101页\一共有201页\编辑于星期五二叉排序树上的查找查找45

查找成功

查找28查找失败351545504025102030在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。现在是102页\一共有201页\编辑于星期五假设想要在二叉排序树中查找关键字为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键字进行比较：如果给定值等于根结点的关键字值，则查找成功。如果给定值小于根结点的关键字值，则继续递归查找根结点的左子树；否则。递归查找根结点的右子树。查找成功时检测指针停留在树中某个结点。现在是103页\一共有201页\编辑于星期五可用判定树描述查找过程。内结点是树中原有结点，外结点是失败结点，代表树中没有的数据。查找不成功时检测指针停留在某个失败结点。3515455025102030查找22查找45现在是104页\一共有201页\编辑于星期五二叉排序树的查找算法voidFind(BSTNode*t,BSTElemTypex,BSTNode*&p,BSTNode*&pr){//在二叉排序树t中查找关键字等于x的结点，成功//时p返回找到结点地址,pr是其双亲结点.不成功//时p为空,pr返回最后走到的结点地址.

p=t;pr=NULL; //从根查找if(p!=NULL){

while(p!=NULL&&p->data!=x){pr=p;if(p->data<x)p=p->rchild;

elsep=p->lchild;现在是105页\一共有201页\编辑于星期五

}}}查找的关键字比较次数最多不超过树的高度。每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。为了向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。二叉排序树的插入现在是106页\一共有201页\编辑于星期五为此，在插入之前先使用查找算法在树中检查要插入元素有还是没有。查找成功：树中已有 这个元素,不再插入。查找不成功：树中原 来没有关键字等于给 定值的结点，把新元 素加到查找操作停止 的地方。35154550402510203028插入新结点28现在是107页\一共有201页\编辑于星期五voidInsert

(BSTNode*&t,BSTElemTypex){//将新元素x插到以*t为根的二叉排序树中

BstNode*pt,*prt,*q;

Find(t,x,pt,prt); //查找结点插入位置

if(pt==NULL){ //查找失败时可插入

q=newBstNode;q->data=x; //创建结点

q->lchild=q->rchild=NULL;

if(prt==NULL)t=q;//空树

else

if(x<prt->data)ptr->lchild=q;elseptr->rchild=q;}}现在是108页\一共有201页\编辑于星期五535378537865537865175378658717537865091787537865811787095378651517870981输入数据，建立二叉排序树的过程输入数据{53,78,65,17,87,09,81,15}现在是109页\一共有201页\编辑于星期五123111132223323同样3个数据{1,2,3

}，输入顺序不同，建立起来的二叉排序树的形态也不同。这直接影响到二叉排序树的查找性能。如果输入序列选得不好，会建立起一棵单支树，使得二叉排序树的高度达到最大。

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}现在是110页\一共有201页\编辑于星期五二叉排序树的删除在二叉排序树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会失去。为保证在删除后树的查找性能不至于降低，还需要防止重新链接后树的高度增加。被删结点的右子树为空，可以拿它的左子女结点顶替它的位置，再释放它。被删结点的左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。被删结点的左、右子树都不为空，可以在它现在是111页\一共有201页\编辑于星期五 的右子树中寻找中序下的第一个结点(所有比被删关键字大的关键字中它的值最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。当然，也可以到它的左子树中寻找中序下的最后一个结点。右子树空,用左子女顶替5378651787092345删除4553786517870923现在是112页\一共有201页\编辑于星期五左子树空,用右子女顶替在右子树上找中序下第一个结点填补8853788817940923删除7853948817092353788117940945删除782365538188179409452365现在是113页\一共有201页\编辑于星期五

二叉排序树性能分析对于有n个关键字的集合，其关键字有n!

种不同排列，可构成不同二叉排序树有

(棵)用树的查找效率来评价这些二叉排序树。用判定树来描述查找过程，在判定树中，○表示内结点，它包含关键字集合中的某一个关键字；□表示外结点，代表各关键字间隔中的不在关键字集合中的关键字。它们是查找失败时到达的结点,物理上实际不存在。现在是114页\一共有201页\编辑于星期五在每两个外部结点间必存在一个内部结点。例，已知关键字集合

{a1,a2,a3}

=

{do,if,to

}，对应查找概率

p1,p2,p3,在各查找不成功间隔内查找概率分别为

q0,q1,q2,q3。可能的判定树如下所示。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)现在是115页\一共有201页\编辑于星期五doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)现在是116页\一共有201页\编辑于星期五一棵判定树的查找成功的平均查找长度ASLsucc定义为该树所有内结点上的权值p[i]与查找该结点时所需的关键字比较次数c[i](=l[i])乘积之和：查找不成功的平均查找长度ASLunsucc为树中所有外结点上权值q[j]与到达该外结点所需关键字比较次数c'[j](=l'[j]-1)乘积之和：现在是117页\一共有201页\编辑于星期五相等查找概率的情形设树中所有内、外结点的查找概率都相等：

p[i]=1/3,1≤i≤3q[j]=1/4,0≤j≤3图(a):

ASLsucc=1/3*(3+2+1)=6/3=2ASLunsucc=1/4*(3+3+2+1)=9/4图(b):

ASLsucc=1/3*(2+1+2)=5/3ASLunsucc=1/4*(2+2+2+2)=8/4图(c):ASLsucc=2,ASLunsucc=9/4图(d):ASLsucc=2,ASLunsucc=9/4图(e):ASLsucc=2,ASLunsucc=9/4现在是118页\一共有201页\编辑于星期五图(b)的情形所得的平均查找长度最小。一般把平均查找长度达到最小的判定树称作最优二叉排序树。在相等查找概率的情形下，最优二叉排序树的上面h-1（h是高度）层都是满的，只有第h

层不满。如果结点集中在该层的左边，则它是完全二叉树；如果结点散落在该层各个地方，则有人称之为理想平衡树。现在是119页\一共有201页\编辑于星期五平衡二叉树

高度不平衡高度平衡ABCABCDEDE平衡二叉树的定义一棵AVL树或者是空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。现在是120页\一共有201页\编辑于星期五

结点的平衡因子balancefactor每个结点附加一个数字，给出该结点左子树的高度减去右子树的高度所得的高度差，这个数字即为结点的平衡因子bf（balancefactor）。平衡二叉树任一结点平衡因子只能取-1,0,1。如果一个结点的平衡因子的绝对值大于1，则这棵二叉排序树就失去了平衡，不再是平衡二叉树。如果一棵二叉排序树是高度平衡的,且有n个结点，其高度可保持在O(log2n),平均查找长度也可保持在O(log2n)。现在是121页\一共有201页\编辑于星期五平衡化旋转如果在一棵平衡二叉树中插入一个新结点，造成了不平衡。必须调整树的结构，使之平衡化。平衡化旋转有两类：

单旋转

(LL旋转和RR旋转)

双旋转

(LR旋转和RL旋转)每插入一个新结点时，平衡二叉树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子。现在是122页\一共有201页\编辑于星期五如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才