数据结构与算法教学课件ppt作者王曙燕chapter6树和二叉树.ppt
- 文档编号:18704296
- 上传时间:2023-10-13
- 格式:PPT
- 页数:115
- 大小:3.72MB
数据结构与算法教学课件ppt作者王曙燕chapter6树和二叉树.ppt
《数据结构与算法教学课件ppt作者王曙燕chapter6树和二叉树.ppt》由会员分享,可在线阅读,更多相关《数据结构与算法教学课件ppt作者王曙燕chapter6树和二叉树.ppt(115页珍藏版)》请在冰点文库上搜索。
1,6.2树的概念,第6章树和二叉树,6.3二叉树,6.4二叉树的遍历,6.5线索二叉树,6.6树和森林,6.1应用实例,6.7哈夫曼树及其应用,6.8实例分析与实现,6.9算法总结,2,第6章树和二叉树,实例一:
数据压缩问题在信息传输、数据压缩问题中,我们总是希望找到一种编码能将待处理数据压缩得尽可能的短。
6.1应用实例,实例二:
表达式的树形表示任意一个表达式,均可以用树形结构来表示,由于大部分的算术运算符有两个操作数,所以可用二叉树来表示一个算术表达式,表达式树中并无括号,但其结构却有效地表达了其运算符间的运算次序。
另外,利用二叉树的遍历等操作,还可得到表达式的三种不同的表示形式:
前缀表达式、中缀表达式、后缀表达式,并可以实现表达式的求值运算。
3,实例三:
等价类划分问题等价关系是现实世界中广泛存在的一种关系,许多应用问题可归结为按给定的等价关系将集合划分为等价类的问题。
问题可描述为:
若R是集合S上的一个等价关系,则由R可得到集合S的唯一划分,即可以按R将S划分为若干个不相交的子集S1,S2,这些子集的并集等于S,子集Si称为S的R等价类。
第6章树和二叉树,6.1应用实例,实例四:
N皇后问题N皇后问题要求在一个NN格的棋盘上放置N个皇后,使其互不攻击。
按规则,互不攻击的约束条件为:
任意两个皇后不能处于同一行、同一列或同一对角线上,现要求给出满足约束条件的所有棋盘布局。
4,6.2树的概念,定义:
数据关系R:
若D为空集,则称为空树。
否则:
(1)在D中存在唯一的称为根的数据元素root;
(2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每一个子集本身又是一棵符合本定义的树,称为根root的子树。
第6章树和二叉树,数据对象D:
D是具有相同特性的数据元素的集合。
5,例如:
第6章树和二叉树,A(B(E,F(K,L),C(G),D(H,I,J(M),T1,T3,T2,根,6.2树的概念,6,表示方法:
第6章树和二叉树,树型表示,6.2树的概念,7,表示方法:
第6章树和二叉树,文氏图表示,6.2树的概念,8,表示方法:
第6章树和二叉树,凹入表示,6.2树的概念,9,表示方法:
第6章树和二叉树,嵌套括号表示,a(b(d,e(i,j),c(g,h),6.2树的概念,10,有向树:
第6章树和二叉树,有确定的根;树根和子树根之间为有向关系。
有序树:
子树之间存在确定的次序关系。
无序树:
子树之间不存在确定的次序关系。
6.2树的概念,11,树型结构和线性结构的结构特点,第6章树和二叉树,第一个数据元素(无前驱),根结点(无前驱),最后一个元素(无后继)。
多个叶子结点(无后继),其它数据元素(一个前驱、一个后继),其它数据元素(一个前驱、多个后继),6.2树的概念,12,第6章树和二叉树,基本术语,结点:
数据元素+若干指向子树的分支,结点的度:
分支的个数,树的度:
树中所有结点的度的最大值,叶子结点:
度为零的结点,分支结点:
度大于零的结点,(从根到结点的)路径:
由从根到该结点所经分支和结点构成。
6.2树的概念,13,数据结构,第6章树和二叉树,基本术语,孩子结点:
一个结点的直接后继,双亲结点:
一个结点的直接前驱,兄弟结点:
同一双亲结点的孩子结点之间互称。
堂兄弟、祖先结点、子孙结点,结点的层次:
假设根结点的层次为1,依次累加。
树的深度:
树中叶子结点所在的最大层次,森林:
是m(m0)棵互不相交的树的集合,6.2树的概念,14,第6章树和二叉树,基本操作,InitTree(Tree);DestoryTree(Tree);CreatTree(Tree);TreeEmpty(Tree);Root(Tree);Parent(Tree,x);FirstChild(Tree,x);NextSibling(Tree,x);InsertChild(Tree,p,Child);DeleteChild(Tree,p,i);,6.2树的概念,15,第6章树和二叉树,定义:
满足以上两个条件的树型结构为二叉树。
每个结点的度都不大于2;,每个结点的孩子结点次序不能任意颠倒。
二叉树或为空树,或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
A,根结点,左子树,右子树,6.2树的概念,16,6.3二叉树,第6章树和二叉树,形态:
5种,17,6.3二叉树,第6章树和二叉树,基本操作:
Initiate(bt);Destory(bt);Creat(bt);Empty(bt);Root(bt);Parent(bt,x);LeftChild(bt,x);RithtChild(bt,x);Traverse(bt);Clear(bt);,18,6.3二叉树,第6章树和二叉树,重要性质:
在二叉树的第i层上至多有2i-1个结点。
用归纳法证明:
.当i=1层时,只有一个根结点:
2i-1=20=1;,.假设i=k时成立,即第k层上至多有2k-1个结点;,.那么第k+1层上最多有2k-12个,即2k个。
结论成立,证毕。
19,6.3二叉树,第6章树和二叉树,重要性质:
深度为k的二叉树上至多含2k-1个结点(k1)。
证明:
基于上一条性质,深度为k的二叉树上的结点数至多为,20+21+2k-1,=2k-1,20,6.3二叉树,第6章树和二叉树,重要性质:
对任何一棵二叉树,若它含有n0个叶子结点、n2个度为2的结点,则必存在关系式:
n0=n2+1。
证明:
设二叉树上结点总数n=n0+n1+n2,又二叉树上分支总数b=n1+2n2,而b=n-1=n0+n1+n2-1,由此,n0=n2+1,21,6.3二叉树,第6章树和二叉树,特殊的二叉树,满二叉树,完全二叉树,深度为k且含有2k-1个结点的二叉树。
树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。
关系:
满二叉树必为完全二叉树,而完全二叉树不一定是满二叉树。
22,6.3二叉树,第6章树和二叉树,重要性质:
具有n个结点的完全二叉树的深度为log2n+1。
证明:
设完全二叉树的深度为k,则根据第二条性质得2k-1-1n2k-1,则2k-1n2k,即k-1log2nk,因为k只能是整数,因此,k=log2n+1。
23,6.3二叉树,第6章树和二叉树,重要性质:
若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号,则对完全二叉树中任意一个编号为i的结点:
(1)若i=1,则该结点是二叉树的根,无双亲,否则,编号为i/2的结点为其双亲结点;,
(2)若2in,则该结点无左孩子,否则,编号为2i的结点为其左孩子结点;,(3)若2i+1n,则该结点无右孩子结点,否则,编号为2i+1的结点为其右孩子结点。
24,6.3二叉树,第6章树和二叉树,存储结构:
顺序存储结构,链式存储结构,25,6.3二叉树,第6章树和二叉树,存储结构:
顺序存储结构,是用一组连续的存储单元来存放二叉树的数据元素。
一维数组btn,数据结构与算法,26,root,6.3二叉树,第6章树和二叉树,存储结构:
链式存储结构:
二叉链表,结点结构:
typedefstructNodeDataTypedata;structNode*lchild;structNode*rchild;BiTNode,*BiTree;,含有n个结点的二叉链表中有2n个指针域,n+1个空域。
27,6.3二叉树,第6章树和二叉树,存储结构:
链式存储结构:
三叉链表,结点结构:
root,28,6.4二叉树的遍历,第6章树和二叉树,遍历二叉树:
顺着某一条搜索路径访问二叉树中的结点,使得每个结点均被访问一次,而且仅被访问一次。
“遍历”是任何类型均有的操作,对线性结构而言,只有一条搜索路径(因为每个结点均只有一个后继),故不需要另加讨论。
二叉树是非线性结构,每个结点有两个后继,存在如何遍历即按什么样的搜索路径遍历的问题,29,第6章树和二叉树,“二叉树”由三个基本单元组成:
根结点、左子树和右子树。
若能依次遍历这三部分,就遍历了整个二叉树。
DLR,DRL,LDR,RDL,LRD,RLD,先左后右,先右后左,设用L、D、R分别表示遍历左子树、访问根结点、遍历右子树,对“二叉树”而言,可以有?
种搜索路径:
6,6.4二叉树的遍历,30,第6章树和二叉树,先(根)序遍历的递归定义:
若二叉树为空树,则空操作;否则,
(1)访问根结点;
(2)先序遍历左子树;(3)先序遍历右子树。
A,B,D,G,C,E,F,先序遍历结果:
A,B,D,G,C,E,F,voidPreOrder(BiTreeroot)if(root!
=NULL)Visit(root-data);PreOrder(root-LChild);PreOrder(root-RChild);,6.4二叉树的遍历,31,第6章树和二叉树,中(根)序遍历的递归定义:
若二叉树为空树,则空操作;否则,
(1)中序遍历左子树;
(2)访问根结点;(3)中序遍历右子树。
A,B,D,G,C,E,F,中序遍历结果:
A,B,D,G,C,E,F,voidInOrder(BiTreeroot)if(root!
=NULL)InOrder(root-LChild);Visit(root-data);InOrder(root-RChild);,6.4二叉树的遍历,32,6.3二叉树的遍历与线索化,第6章树和二叉树,后(根)序遍历的递归定义:
若二叉树为空树,则空操作;否则,
(1)后序遍历左子树;
(2)后序遍历右子树;(3)访问根结点。
A,B,D,G,C,E,F,后序遍历结果:
A,B,D,G,C,E,F,voidPostOrder(BiTreeroot)if(root!
=NULL)PostOrder(root-LChild);PostOrder(root-RChild);Visit(root-data);,33,第6章树和二叉树,练习,先序:
ABDEHICFJGK,中序:
DBEHIAFJCGK,后序:
DIHEBJFKGCA,6.4二叉树的遍历,34,第6章树和二叉树,举例:
先序:
-,+,a,*,b,-,c,d,/,e,f,中序:
a,+,b,*,c,-,d,-,e,/,f,后序:
a,b,c,d,-,*,+,e,f,/,-,前缀式(波兰式),中缀式(表达式),后缀式(逆波兰式),6.4二叉树的遍历,35,第6章树和二叉树,由遍历序列确定二叉树,由先序和中序序列恢复二叉树举例,先序序列:
ABCDEFG,中序序列:
CBDAEGF,A,A,左子树,右子树,A,B,B,B,C,C,C,D,D,D,E,E,E,F,F,F,G,G,G,6.4二叉树的遍历,36,6.3二叉树的遍历与线索化,第6章树和二叉树,由遍历序列确定二叉树,由中序和后序序列恢复二叉树,中序序列:
DCBGEAHFIJK,后序序列:
DCEGBFHKJIA,A,练习:
I,J,K,H,F,B,G,E,C,D,37,第6章树和二叉树,遍历算法应用:
遍历算法将走遍二叉树中的每一个结点,故输出二叉树中结点并无次序要求,因此可用任一种算法来完成。
voidPreOrder(BiTreeroot)if(root!
=NULL)printf(root-data);PreOrder(root-LChild);PreOrder(root-RChild);,输出二叉树中的结点,6.4二叉树的遍历,38,6.3二叉树的遍历与线索化,第6章树和二叉树,遍历算法应用:
条件:
判断结点既没有左孩子,又没有右孩子时,则输出该结点。
voidPreOrder(BiTreeroot)if(root!
=NULL)if(root-LChild=NULL,输出二叉树中的叶子结点,39,第6章树和二叉树,遍历算法应用:
voidleaf(BiTreeroot)if(root!
=NULL)leaf(root-LChild);leaf(root-RChild);if(root-LChild=NULL,统计叶子结点数目,方法1:
intLeafCount=0;/为全局变量,调用之前初始化值为0,6.4二叉树的遍历,40,第6章树和二叉树,遍历算法应用:
intleaf(BiTreeroot)intLeafCount;if(root=NULL)LeafCount=0;elseif(root-LChild=NULL),统计叶子结点数目,方法2:
6.4二叉树的遍历,41,6.3二叉树的遍历与线索化,第6章树和二叉树,建立二叉链表方式存储的二叉树,给定一棵二叉树,可以得到它的遍历序列;反过来,给定一个遍历序列,也可以创建相应的二叉链表。
在这里所说的遍历序列是一种“扩展的遍历序列”,通常用特定的元素表示空子树。
例如.有先序序列:
ABDFGCEH,A,B,D,F,G,C,E,H,遍历算法应用:
voidCreateBiTree(BiTree*bt)charch;ch=getchar();if(ch=)*bt=NULL;else*bt=(BiTree)malloc(sizeof(BiTNode);(*bt)-data=ch;CreateBiTree(,BiTreeCreateBiTree()charch;BiTreeNode*p;ch=getchar();if(ch=)returnNULL;elsep=(BiTreeNode*)malloc(sizeof(BiTreeNode);p-data=ch;p-LChild=CreateBiTree();p-RChild=CreateBiTree();return(p);,42,第6章树和二叉树,求二叉树的高度,设函数表示二叉树bt的高度,则递归定义如下:
若bt为空,则高度为0若bt非空,其高度应为其左右子树高度的最大值加1,遍历算法应用:
hl,hr,High=max(hl,hr)+1,intPostTreeDepth(BiTreebt)inthl,hr,max;if(bt!
=NULL)hl=PostTreeDepth(bt-LChild);hr=PostTreeDepth(bt-RChild);max=hlhr?
hl:
hr;return(max+1);elsereturn(0);,方法1:
6.4二叉树的遍历,43,第6章树和二叉树,求二叉树的高度,遍历算法应用:
intPreTreeDepth(BiTreebt,inth)if(bt!
=NULL)if(hdepth)depth=h;PreTreeDepth(bt-LChild,h+1);PreTreeDepth(bt-RChild,h+1);,intdepth=0;/为全局变量,方法2:
6.4二叉树的遍历,44,第6章树和二叉树,按树状打印的二叉树,假设以二叉链表存储的二叉树中,每个结点所含数据元素均为单字母,要求实现如下图的打印结果。
遍历算法应用:
遍历方案:
RDL(逆中序遍历),层数:
1234(决定左右位置),voidPrintTree(TreeNodebt,intnLayer)if(bt=NULL)return;PrintTree(bt-Rchild,nLayer+1);Visit(bt-data);PrintTree(bt-Lchild,nLayer+1);,for(inti=0;idata);,6.4二叉树的遍历,45,第6章树和二叉树,求结点的双亲,遍历算法应用:
BiTreeparent(BiTreeroot,BiTreecurrent)/在以root为根的二叉树中找结点current的双亲BiTree*p;if(root=NULL)returnNULL;if(root-lchild=current|root-rchild=current)returnroot;/root即为current的双亲p=parent(root-lchild,current);/递归在左子树中找if(p!
=NULL)returnp;elsereturn(parent(root-rchild,current);/递归在右子树中找,6.4二叉树的遍历,46,第6章树和二叉树,二叉树相似性判定,遍历算法应用:
intlike(BiTreet1,BiTreet2)intlike1,like2;if(t1=NULL,6.4二叉树的遍历,47,6.3二叉树的遍历与线索化,第6章树和二叉树,按层次遍历二叉树,voidLayerOrder(BiTreeroot)SqQueueQ;InitQueue(Q);BiTNode*p;p=root;if(p=NULL)return;EnterQueue(Q,p);while(!
IsEmpty(Q)DeleteQueue(Q,p);printf(“%c”,p-data);if(p-lchild)EnterQueue(Q,p-lchild);if(p-rchild)EnterQueue(Q,p-rchild);,48,第6章树和二叉树,递归算法的两个基本特征递推归纳将问题转化为比原问题小的同类规模,归纳出一般递推公式.故所处理的对象要有规律地递增或递减递归终止当规模小到一定的程度应该结束递归调用,逐层返回,常用条件语句来控制何时结束递归。
6.4二叉树的遍历,49,第6章树和二叉树,执行过程(两个阶段)第一阶段:
逐层调用,调用函数自身第二阶段:
逐层返回,返回到调用该层的位置继续执行后。
递归调用是多重嵌套调用的一种特殊情况调用的深度:
调用的层数,6.4二叉树的遍历,50,第6章树和二叉树,设计递归算法的方法,前提:
1.原问题可以层层分解为类似的子问题,且子问题比原问题规模更小;2.规模最小的问题具有直接解。
方法:
寻找分解方法:
将原问题转化为子问题求解;设计递归出口:
根据规模最小的子问题确定递归终止条件。
6.4二叉树的遍历,51,第6章树和二叉树,1.将所有的实际参数、返回地址等信息传递给被调用函数保存;2.为被调用函数的局部变量分配存储区;3.将控制转移到被调用函数的入口。
当在一个函数的运行期间调用另一个函数时,在运行该被调用函数之前,需先完成三项任务:
函数调用实现内幕,6.4二叉树的遍历,52,第6章树和二叉树,1.保存被调函数的计算结果;2.释放被调函数的数据区;3.依照被调函数保存的返回地址将控制转移到调用函数。
从被调用函数返回调用函数之前,应该完成下列三项任务:
6.4二叉树的遍历,53,第6章树和二叉树,多个函数嵌套调用的规则是:
此时的内存管理实行“栈式管理”,后调用先返回!
例如:
voidmain()a();/main,Main的数据区,函数a的数据区,函数b的数据区,voida()b();/a,voidb()/b,6.4二叉树的遍历,54,先序遍历二叉树的非递归算法,基于栈的递归消除:
6.3二叉树的遍历与线索化,第6章树和二叉树,voidPreOrder(BiTreeroot)InitStack(/*遍历右子树*/,55,中序遍历二叉树的非递归算法,基于栈的递归消除:
6.3二叉树的遍历与线索化,第6章树和二叉树,voidInOrder(BiTreeroot)InitStack(/*遍历右子树*/,56,要求左、右子树都访问完后,最后访问根结点。
如何判断当前栈顶结点的左右子树都已访问过?
2)如p的右孩子是刚被访问过的结点;,6.3二叉树的遍历与线索化,第6章树和二叉树,后序遍历二叉树的非递归算法,基于栈的递归消除:
1)p无右孩子,即p-Rchild为空;,访问根结点两个条件:
需要一个记录被访问过结点的指针q。
voidPostOrder(BiTreeroot)BiTNode*p,*q;BiTreesStack_Size;inttop=0;q=NULL;p=root;while(p!
=NULL|top!
=0)if(p!
=NULL)Push(,57,6.5线索二叉树,第6章树和二叉树,遍历二叉树的结果是,求得结点的一个线性序列。
线索二叉树,先序序列:
A,B,C,D,E,F,G,H,K,中序序列:
B,D,C,A,H,G,K,F,E,后序序列:
D,C,B,H,K,G,F,E,A,58,第6章树和二叉树,结点结构:
线索二叉树,数据结构与算法,6.5线索二叉树,59,第6章树和二叉树,在这种存储结构中,指向前驱和后继结点的指针叫做线索。
线索二叉树,以这种结构组成的二叉链表作为二叉树的存储结构,叫做线索链表。
对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化。
线索化了的二叉树称为线索二叉树。
6.5线索二叉树,60,第6章树和二叉树,线索化实质上是将二叉链表中的空指针域填上相应结点的遍历前驱或后继结点的地址,而前驱和后继的地址只能在动态的遍历过程中才能得到。
因此线索化的过程是在遍历过程中修改空指针域的过程。
对二叉树按照不同的遍历次序进行线索化,可以得到不同的线索二叉树(先序线索二叉树、中序线索二叉树和后序线索二叉树)。
二叉树的线索化,6.5线索二叉树,61,第6章树和二叉树,举例:
先序序列:
ABDGCEHF,NULL,中序序列:
DGBAEHCF,NULL,NULL,后序序列:
GDBHEFCA,NULL,转向,6.5线索二叉树,62,第6章树和二叉树,在中序遍历过程中修改结点的左、右指针域,以保存当前访问结点的“前驱”和“后继”信息。
遍历过程中,附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。
建立线索链表,6.5线索二叉树,63,第6章树和二叉树,中序线索化算法,voidInthread(BiTreeroot)if(root!
=NULL)Inthread(root-LChild);/*线索化左子树*/if(root-LChild=NULL)root-Ltag=1;root-LChild=pre;if(pre!
=NULL/*线索化右子树*/,6.5线索二叉树,64,第6章树和二叉树,在线索二叉树中找前驱、后继结点,(以中序为例),在中序线索树中找结点前驱:
左子树的“最右下端”结点,BiTNode*InPre(BiTNode*p)if(p-Ltag=1)pre=p-LChild;elsefor(q=p-LChild;qRtag=0;q=q-RChild);pre=q;return(pre);,6.5线索二叉树,65,第6章树和二叉树,在线索二叉树中找前驱、后继结点,(以中序为例),在中序线索树中找结点后继:
右子树的“最左下端”结点,BiTNode*InNext(BiTNode*p)if(p-Rtag=1)Next=p-RChild;elsefor(q=p-RChild;q-Ltag=0;q=q-LChild);Next=q;return(Next);,如何找“先序”和“后序”遍历的第一个结点?
6.5线索二叉树,66,第6章树和二叉树,遍历中序线索树,中序遍历的第一个结点;,在中序线索化链表中结点的后继。
6.5线索二叉树,67,第6
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 教学 课件 ppt 作者 王曙燕 chapter6 二叉