数据结构第五章

数据结构第五章第1页，课件共67页，创作于2023年2月树的基本概念二叉树遍历二叉树线索二叉树树的应用特点：非线性结构，一个直接前驱，但可能有多个直接后继。（一对多或1:n）二叉树的定义、性质和存储结构二叉树的运算第2页，课件共67页，创作于2023年2月树适于反应层次关系的数据对象的研究。层次化的数据之间可能有:祖先—后代、上级—下级、整体—部分等其它类似的关系。学院法学院工商学院信息学院金融学院人文学院会计学院财税学院计算机系信息系统计系图5.1.1一棵学院信息的树第3页，课件共67页，创作于2023年2月5.1.1树的定义

由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root）当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。树的定义具有递归性，即“树中还有树”。第4页，课件共67页，创作于2023年2月一棵树至少包含一个树结点，不存在不含树结点的树；树中结点存在着层次关系，但同一层上的树结点之间是无序的。一棵树的每个结点都是某个子树的根。第5页，课件共67页，创作于2023年2月若干术语——（也称父亲）即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点ABCGEIDHFJFLK根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。第6页，课件共67页，创作于2023年2月——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)ABCGEIDHFJFLK——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝1334（有几个直接后继就是几度，亦称“次数”）第7页，课件共67页，创作于2023年2月ABCDEFGHIJKLM结点A的度：?结点B的度：?结点M的度：?叶子：?结点A的孩子：?结点B的孩子：?结点I的双亲：?结点L的双亲：?结点B，C，D为?结点K，L为?树的度：?结点A的层次：?结点M的层次：?树的深度：?结点F，G为?结点A是结点F，G的?320B，C，DE，F314K，L，F，G，M，I，JDE兄弟兄弟4堂兄弟祖先第8页，课件共67页，创作于2023年2月5.2.1二叉树的定义定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空第9页，课件共67页，创作于2023年2月2.

二叉树的定义与树的定义的区别二叉树存在着空树；但树不能为空。二叉树中的每一个结点只可能有0个，1个或2个孩子，也就是说，二叉树不存在度大于2的结点；而树中的每个结点可以有多个子树。二叉树的子树有左右之分，两者不能颠倒；但树的子树一般是无序的。除以上区别外，上一节引入树的有关术语对于二叉树也适用。第10页，课件共67页，创作于2023年2月3.满二叉树的定义 若二叉树中所有分枝结点的度数都为2，且叶子结点都在同一层上，则称这类二叉树为满二叉树。5.完全二叉树的定义若二叉树中所有分枝结点的度数要就为2，要就为0，称这类二叉树为完全二叉树。4.顺序二叉树的定义:

对满二叉树从上至下，从左至右地从1开始编号，结果是每个结点都可以与满二叉树中编号为1至n的结点一一对应6.退化二叉树的定义:

如果一棵非空的二叉树只有一个叶子，且其余结点均只有一个孩子第11页，课件共67页，创作于2023年2月ABCDEFG图5.2.2一棵满二叉树123456789101112图5.2.4一棵顺序二叉树图5.2.5一棵非顺序二叉树12345678912图5.2.8退化的二叉树AIDB12472852(a)(b)第12页，课件共67页，创作于2023年2月5.2.2二叉树的性质

性质1:在二叉树的第i层上最多有2i-1个结点（i≥1）。用归纳法证明它。当i=1时，21-1=1，这时只有一个根结点，显然结论是正确的。假设，对于所有的j（1≤j<i）结论也成立，即第j层上至多有2j-1个结点，那么，我们也可以证明当j=i时结论也成立，证明如下：由归纳法假设知道，第i-1层上至多有2i-2个结点，由于二叉树的每个结点至多有两个孩子，所以第i层上最大结点数应为第i-1层上最大结点数的两倍，即第i层上最多结点数为：2*2i-2=2i-1。故结论得证。第13页，课件共67页，创作于2023年2月5.2.2二叉树的性质

性质2:深度为h的二叉树至多有2h-1个结点。可以由性质1推出上述结论。显然，深度为h的二叉树的最大结点应为各层最大结点之和即为：（第i层上的最大结点数）=2i-1=2h-1第14页，课件共67页，创作于2023年2月5.2.2二叉树的性质

性质3:包括n（n>0）个元素的二叉树的边数为n-1。证明：二叉树中每个元素（除根结点外）有且仅有一个双亲结点。而孩子结点与双亲结点之间有且仅有一条边，因此包含n个元素的二叉树的边数是n-1。第15页，课件共67页，创作于2023年2月5.2.2二叉树的性质

1. 性质1:在二叉树的第i层上最多有2i-1个结点（i≥1）。性质2:深度为h的二叉树至多有2h-1个结点。性质3:包括n（n>0）个元素的二叉树的边数为n-1。性质4:对于任何一棵二叉树，若其终端结点数为n0，其度为2的结点数为n2，则有：n0=n2+1。5.性质5:若一棵满二叉树有n个结点,则深度h第16页，课件共67页，创作于2023年2月性质6 一棵有n个结点的顺序二叉树，如从左至右、从上至下的，对每个结点从1开始编号，对于其中任意编号为i的结点（1≤i≤n）有：(1)若i1,则i的父亲是i/2；若i=1，则i是根结点，无父亲。(2)若2i≤n，则i的左孩子是2i；若2i>n，则i无左孩子。(3)若2i+1≤n，则i的右孩子是2i+1；若2i+1>n，则i无右孩子。第17页，课件共67页，创作于2023年2月123114589126710图5.2.9顺序二叉树父子关系152178525777ii+12i2i+12i+2i/2第18页，课件共67页，创作于2023年2月3.深度为9的二叉树中至少有

个结点。Ａ)２9

Ｂ)２8

Ｃ)９Ｄ)２9－12.深度为Ｋ的二叉树的结点总数，最多为

个。Ａ)２k-1

Ｂ)log2kＣ)２k－１Ｄ)２k1.树Ｔ中各结点的度的最大值称为树Ｔ的

。Ａ)高度Ｂ)层次Ｃ)深度Ｄ)度DCC课堂练习：第19页，课件共67页，创作于2023年2月

4：具有3个结点的二叉树可能有几种不同形态？

第20页，课件共67页，创作于2023年2月二叉树的抽象数据类型Dset： 有限元素集合。Rset： 如果不空，被分为根结点、左子树和右子树；每个子树仍然是一个二叉树。OPSet：PreOrder(*BT)二叉树的前序遍历递归算法PreOrderN(*BT)二叉树的前序遍历非递归算法InOrder(*BT)二叉树的中序遍历递归算法InOrderN(*BT)二叉树的中序遍历非递归算法第21页，课件共67页，创作于2023年2月二叉树的抽象数据类型PostOrder(*BT)二叉树的后序遍历递归算法PostOrderN(*BT)二叉树的后序遍历非递归算法LevelOrderTL(*BT)左至右，上至下层次遍历LevelOrderTR(*BT))右至左，上至下层次遍历MakeNode(&x)构造结点MakeBinaryTree(*root,*left,*right)联接三个结点为二叉树BinaryHeight(*BT)求二叉树的高度BinaryDelete(*BT)二叉树的删除算法第22页，课件共67页，创作于2023年2月5.3.1二叉树的存储结构一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。ABCDEFGHI[0][1][2][3][4][5][6][7][8]问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2(i+1)-1，其右孩子的下标值必为2(i＋1)

例如，对应[2]C的两个孩子必为[5]和[6],即B的左孩子必是F,右孩子必为G。ABCGEIDHF012第23页，课件共67页，创作于2023年2月讨论：不是完全二叉树怎么办？答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。AB^C^^^D^…E[0][1][2][3][4][5][6][7][8].[15]ABECD缺点：①浪费空间；②插入、删除不便

第24页，课件共67页，创作于2023年2月二、链式存储结构

用二叉链表即可方便表示。dataleft_childright_childdataleft_childright_childtypedefstruct

BinaryTreeNode{ EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;}BinaryTreeNode；一般从根结点开始存储。

（相应地，访问树中结点时也只能从根开始）注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。第25页，课件共67页，创作于2023年2月优点：①不浪费空间；②插入、删除方便

ABCDEFG

AB

C

D

E

F

G^^^^^^^^第26页，课件共67页，创作于2023年2月问：含有n个结点的二叉树中，共有链接域有2n个，空闲的（不用的）链接域有n+1个（为什么？）证明：根据性质4：n0=n2+1,有叶子结点空闲的链接域为2n2+2度为1的结点空闲的链接域为n-n0-n2=n-2n2-1,则总的空闲链接域为2n0+n1=n+1第27页，课件共67页，创作于2023年2月5.4.4二叉树的其它操作

构造一棵二叉树的结点BinaryTreeNode*MakeNode(EType&x) {//构造结点

BinaryTreeNode *ptr; Ptr=newBinaryTreeNode; if(ptr) returnNULL; ptr->data=x; ptr->LChild=NULL; ptr->RChild=NULL; return ptr;}x=‘A’;BinaryTreeNode*Aptr=MakeNode(&x);

第28页，课件共67页，创作于2023年2月2)构造一棵二叉子树（或二叉树）

voidMakeBinaryTree(BinaryTreeNode*root,BinaryTreeNode*left,BinaryTreeNode*right){//联接root，left,right所指的结点指针为二叉树

root->LChild=left; root->RChild=right;}第29页，课件共67页，创作于2023年2月ABCDEFG图5.4.4一棵二叉树

MakeBinaryTree(E,G,NULL); MakeBinaryTree(B,D,E); MakeBinaryTree(C,NULL,F); MakeBinaryTree(A,B,C);用MakeBinaryTree构造下图给出的树。第30页，课件共67页，创作于2023年2月5.4二叉树链式存储结构下的操作5.4.1遍历二叉树遍历定义——遍历用途——遍历方法——指按某条搜索路线遍访每个结点且不重复（又称周游）。它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。对每个结点的查看通常都是“先左后右”。TraversingBinaryTree第31页，课件共67页，创作于2023年2月遍历规则———二叉树由根、左子树、右子树构成，定义为D、L、R以根结点为参照系注：“前、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。D、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，则有三种实现方案：

DLRLDRLRD前序遍历中序遍历后序遍历

第32页，课件共67页，创作于2023年2月ADBCDLRADLRDLR>B>>D>>CDLR前序遍历序列：ABDC前序遍历:第33页，课件共67页，创作于2023年2月ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列：BDAC中序遍历:第34页，课件共67页，创作于2023年2月ADBC

LRDLRDLRD>A>>D>>CLRD后序遍历序列：DBCA后序遍历:B第35页，课件共67页，创作于2023年2月+*A*/EDCB先序遍历结果+**/ABCDE—前缀表示法中序遍历结果A/B*C*D+E—中缀表示法后序遍历结果AB/C*D*E+—后缀表示法例1：用二叉树表示算术表达式先序遍历结果中序遍历结果后序遍历结果层次遍历结果第36页，课件共67页，创作于2023年2月ABCDEFGABCGEIDHF例1先序遍历结果ABDHIECFG中序遍历结果HDIBEAFCG后序遍历结果HIDEBFGCA例1例2例2先序遍历结果ABCDEGF中序遍历结果CBEGDFA后序遍历结果CGEFDBA第37页，课件共67页，创作于2023年2月构造二叉树：一步是先构造结点，第二步是将产生的结点联接在一起。计算二叉树的深度：比较左子树和右子树的高度，取其最大值删除二叉树：从叶子开始，先删除左子树，再删除右子树，最后删除根结点。统计二叉树结点数：在遍历时，每次访问一个结点时，就在统计个数的计数器中加一。插入结点或删除结点：二叉树的操作第38页，课件共67页，创作于2023年2月5.4.2二叉树的前序、中序、后序遍历操作

对于二叉树的遍历，将用递归算法和非递归算法给予讨论。递归算法简单明晰，但由于递归本身的嵌套执行过程，会影响到算法执行的效率；非递归算法相对较复杂，实现中运用栈结构类型，算法的效率相对效高，第39页，课件共67页，创作于2023年2月1）前序遍历的递归算法voidPreOrder(BinaryTreeNode*BT){//二叉树的前序遍历递归算法

if(BT) { cout<<BT->data<<"";//访问二叉树的结点

PreOrder(BT->LChild); PreOrder(BT->RChild); }}第40页，课件共67页，创作于2023年2月主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC第41页，课件共67页，创作于2023年2月前序遍历的非递归算法

DLR#defineMaxStackSize100typedefstruct{ BinaryTreeNode *element; int top; int MaxSize;}Stack；StackS;第42页，课件共67页，创作于2023年2月非递归前序算法遍历思想：A。结点指针非空时或堆栈非空时:如果结点指针非空时，首先访问“根”结点；结点指针为空时，转C步骤；B。然后将访问过的结点指针（一个“根”的指针）进栈，再将指针指向访问过的结点的左子树的根，转A步骤；C。堆栈非空时，退栈，指针指向退栈结点的右子树结点，转A。第43页，课件共67页，创作于2023年2月

ABCDE图5.4.3二叉树表5.4.1二叉树前序遍历非递归过程

步骤访问结点栈S内容P的指向初态

A1AAB2BABC3C

ABC空(C的左孩子)4

AB空(C的右孩子)5

AD6D

AD空(D的左孩子)7

AE8E

AE空(E的左孩子)9

A空(E的右孩子)10

空空(A的右孩子)P第44页，课件共67页，创作于2023年2月二叉树的前序遍历非递归算法while(p||!IsEmpty(&S)){ if(p){ cout<<p->data<<"";//访问“根”结点

Push(&S,p);/根结点指针进栈，以后回朔时再退栈

p=p->LChild;//指针指向访问过的“根”结点左子树.}else //左子树为空时，利用堆栈回朔第45页，课件共67页，创作于2023年2月二叉树的前序遍历非递归算法if(!IsEmpty(&S)){Pop(&S,p);/从堆栈中弹出回朔结点指针（该结点已访问过）

p=p->RChild;//指针指向回朔结点的右子树

} 第46页，课件共67页，创作于2023年2月2.中序遍历的递归算法

LDRvoidInOrder(BinaryTreeNode*BT){//二叉树的中序遍历递归算法

if(BT) { InOrder(BT->LChild); cout<<BT->data<<""; //访问二叉树的结点

InOrder(BT->RChild); }}第47页，课件共67页，创作于2023年2月中序遍历的非递归算法

首先结点指针（一个“根”的指针）进栈，然后将结点指针指向进栈结点的左子树的根，重复A步，直到指针指向空。（最后一个进栈的是最左子树）；堆栈非空时，从堆栈中退出一个指向子树的“根”的指针，访问该指针所指结点，转到C步骤。堆栈为空时，结束算法；然后将指针指向访问过结点的右子树的根，重新从A步骤做起。第48页，课件共67页，创作于2023年2月表5.4.2二叉树中序遍历非递归过程

步骤访问结点栈S内容P的指向初态

A1

AB2

ABC3

ABC空(C的左孩子)4CAB空(C的右孩子)5BAD6

AD空(D的左孩子)7DAE8

AE空(E的左孩子)9EA空(E的右孩子)10A空空(A的右孩子)ABCDE图5.4.3二叉树第49页，课件共67页，创作于2023年2月do{ while(p){ //找最左子树

Push(S,p);//“根”结点（未访问）指针进栈，以后回朔时再退栈

p=p->LChild;//指针指向该“根”结点左子树

} if(!IsEmpty(S)){ //左子树为空时，利用堆栈回朔

Pop(S,p);//从堆栈中弹出回朔结点指针（该结点未访问过）

cout<<p->data<<""; //访问“根”结点

p=p->RChild; //指针指向回朔结点的右子树}}while（（p）||!IsEmpty(S)）;第50页，课件共67页，创作于2023年2月3.二叉树的后序遍历LRDvoidPostOrder(BinaryTreeNode*BT){//二叉树的中序遍历递归算法

if(BT) { PostOrder(BT->LChild); PostOrder(BT->RChild); Cout<<BT->data<<""; //访问二叉树的结点}}第51页，课件共67页，创作于2023年2月后序遍历的非递归算法

后序遍历的非递归算法中结点的进栈不是一次，每个结点要进栈两次。第一次进栈时，是在遍历左子树的过程中将“根”结点进栈，待左子树访问完后，退出这个“根”结点，但不能立即访问.借助于这个“根”去找该“根”的右子树，并遍历这个右子树，直到该右子树全部遍历以后，再退出该“根”结点，访问之。将堆栈数据元素的结构中增加一个数据项，用于记载第几次进栈。

第52页，课件共67页，创作于2023年2月堆栈数据元素struct{ BinaryTreeNode *ptr; boolB;//B为false时，表示第一次进栈；B为true时，表示第二次进栈

}SType;typedefstruct{ SType *element int top; int MaxSize;}Stack；StackS;第53页，课件共67页，创作于2023年2月非递归后序遍历算法思想：A) 当结点非空时或堆栈非空时，执行A步骤，否则，结束算法。B) 当结点指针非空时，结点的进栈标志设为false，结点指针及进栈标志进栈，然后将结点指针指向进栈结点的左子树的根，重复B步，直到指针为空（最后一个进栈的是最左子树）；结点指针为空时，转C步骤。C) 堆栈非空时，从堆栈中退出一个结点的指针；如果退出的结点进栈标志为true，说明该结点是第二次退栈，则访问该结点，并将指针强制设为空，准备下一次退栈，并转C步骤；第54页，课件共67页，创作于2023年2月ABCDE图5.4.3二叉树第55页，课件共67页，创作于2023年2月while（（p）||!IsEmpty(S)）if(p) //找最左子树{ temp.B=false; //准备进栈的结点进栈标志设为第一次进栈

temp.ptr=p; Push(S,temp);//“根”结点（未访问）指针及标志进栈，以后回朔时再退栈

p=p->LChild; //指针指向该“根”结点左子树}else第56页，课件共67页，创作于2023年2月if(!IsEmpty(S)){//左子树为空时，利用堆栈回朔

Pop(S,temp); //从堆栈中弹出回朔结点指针及标志（该结点未访问过）

p=temp.prt; //p指向退栈结点

if(temp.B){ cout<<p->data<<""; //访问该结点

p=NULL; //将p设为空的目的是为强制退栈作准备

}else { temp.B=true;//改变进栈标志，准备重新进栈

Push(S,temp); p=p->RChild;//指针指向“根”的右子树

}}第57页，课件共67页，创作于2023年2月对遍历的分析：从前面的三种遍历算法可以知道： 从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问，是先序遍历第2次经过时访问，是中序遍历第3次经过时访问，是后序遍历2.二叉树遍历的时间效率和空间效率时间效率:O(n)

//每个结点只访问一次空间效率:O(n)

//栈占用的最大辅助空间精确值：树深为k的递归遍历需要k+1个辅助单元第58页，课件共67页，创作于2023年2月5.4.3二叉树的层次遍历操作

介绍从上至下的两种遍历过程层次遍历时，将使用一个队列作为辅助，来完成遍历过程typedefstruct{ BinaryTreeNode *element; int front; int rear; int MaxSize;}Queue；如果一个结点被访问后，则其先准备访问的孩子就应该先进队，后访问的孩子后进队。第59页，课件共67页，创作于2023年2月1.从上至下，

从左至右（Top_Left）ABCDEFG图5.4.4一棵二叉树第60页，课件共67页，创作于2023年2月while(p){ cout<<p->data<<""; //访问该结点

if(p->LChild) Enqueue(&Q,p->LChild); //左子树进队

if(p->RChild) Enqueue(&Q,