第七章 二叉树及其应用.ppt
《第七章 二叉树及其应用.ppt》由会员分享,可在线阅读,更多相关《第七章 二叉树及其应用.ppt(223页珍藏版)》请在三一文库上搜索。
1、7.1 二叉树的概念 7.2 二叉树的存储 7.3 二叉树的遍历 7.4 线索二叉树 7.5 二叉树的应用1基本算法 7.6 二叉树的应用2哈夫曼树 7.7 二叉树的应用3二叉排序树 7.8 二叉树的应用3堆和堆排序,第7章 二叉树及其应用,7.1.1 什么是二叉树 7.1.2 特殊的二叉树 7.1.3 二叉树的性质,7.1 二叉树的概念,二叉树的定义 二叉树是由n(n0)个结点组成的有限集合,其中: 当n0时为空树; 当n0时,有且仅有一个特定的结点,称为二叉树的根,其余结点可分为2个互不相交的子集,其中每一个子集本身又是一棵二叉树,分别称为左子树和右子树。,二叉树的形态,二叉树的基本术语:
2、 父结点:若一个结点有子树,则该结点为父结点(也称 双亲结点)。 孩子结点:若某结点有左子树,则其左子树的根为该结点的左孩子;若其有右子树,则其右子树的根为该结点的右孩子。,结点A为结点B、C的父结点 B为A的左孩子, C是A的右孩子;,兄弟结点:同一个结点的孩子。 延伸父子关系可得到祖先结点和后代结点关系。 层次:根结点的层次为1,其余结点的层次是其父结点 的层次加1。 高度(深度):二叉树中结点的最大层次数。,该二叉树的深度为4;,度:一个结点的孩子数目是这个结点的度。 叶子结点:度为0的结点。 二叉树的度:二叉树中结点的最大的度。,A、B、C的度均为2; E、F、G的度均为1; D、H、
3、I、J的度为0.,注意:对于结点数1的二叉树,有且仅有一个结点为二叉树的根,其余结点均为孩子结点,且有左右之分左孩子、右孩子。,例:具有三个结点的二叉树,总结:二叉树的逻辑结构 (1)二叉树中任一结点(除根结点外)只有一个父结点; (2)二叉树中任一结点(除叶子结点外)最多有2个孩子结点; (3)结点间为非线性关系。,7.1.1 什么是二叉树 7.1.2 两种特殊的二叉树 7.1.3 二叉树的性质,7.1 二叉树的概念,满二叉树 定义:满二叉树是满足如下条件的二叉树: 任一非叶子结点均有两个孩子; 对于二叉树的任一层,若该层上有一个结点有孩子,则该层上所有结点均有孩子。 特点:满二叉树的每层都
4、有最大结点数。,问题:可不可以说,所有非叶子结点均有两个孩子的二叉树为满二叉树?,完全二叉树 定义:在满二叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。 特点: 叶子结点只可能在层次最大的两层上出现; 满二叉树必为完全二叉树, 而完全二叉树不一定是满二叉树。,例:满二叉树和完全二叉树,7.1.1 什么是二叉树 7.1.2 两种特殊的二叉树 7.1.3 二叉树的性质,7.1 二叉树的概念,性质1:在二叉树的第i层上至多有2i-1个结点(i 0) 证明: 用数学归纳法。 归纳基础:当i=1时,整个二叉树只有一根结点,此时2i-1=20=1,结论成立。 归纳假设:假设i=k时结论成立,即第
5、k层上结点总数最多为2k-1个。 现证明当i=k+1时, 结论成立: 因为二叉树中每个结点的度最大为2,则第k+1层的结点总数最多为第k层上结点最大数的2倍,即22k-1=2(k+1)-1,故结论成立。,性质2:深度为k的二叉树至多有2k-1个结点(k 0) 证明:因为深度为k的二叉树,其结点总数的最大值是将二叉树每层上结点的最大值相加,所以深度为k的二叉树的结点总数至多为,故结论成立。,深度为k的满二叉树有2k-1个结点;或者说,深度为k且有2k-1个结点的二叉树为满二叉树。,性质3:对任一棵非空的二叉树T,如果其叶子数为n0,度为2的结点数为n2,则: n0 = n2 +1 证明:设 总结
6、点数为n,度为1的结点数为n1. 则 : n = n1 + n2 + n0 又 度为1的结点有1个孩子,度为2的结点有2个孩子. 故 二叉树中孩子结点的总数为n1 + 2n2 二叉树中只有根结点不是任何结点的孩子 总结点数 n = n1 + 2n2 + 1 即:n1 +2n2 + 1 = n1 + n2 + n0 n0 = n2 +1,例:已知叶子数为20,10个结点有一个左孩子,15个结点有一个右孩子,求该二叉树的总结点数。 解:n0 = 20 n1 = 10 + 15 = 25 由于 n0 = n2 + 1 则:n2 = n0 1= 19 n = n0 + n1 + n2 = 20 + 2
7、5 + 19 = 64,性质4: 有 n 个结点的完全二叉树( n 0 )的高度为 +1 证明:假设一棵高度为h的二叉树有n个结点, 根据性质2,有 n2h1 从而 hlog2(n+1) 所以 h +1,性质5:若对满二叉树或完全二叉树按照“从上到下,每层从左到右,根结点编号为1”的方式编号,则编号为 i 的结点,它的两个孩子结点的编号分别为 2i 和 2i +1,它的父结点的编号为 i /2 。,思考题: 有100个结点的完全二叉树有多少个叶子结点? 解: 第100个结点的编号为100,其父结点的编号为50,且其父结点的右兄弟(编号为51)没有孩子,即为叶子;所以,叶子结点的编号从51至10
8、0,叶子结点有50个。,7.1 二叉树的概念 7.2 二叉树的存储 7.3 二叉树的遍历 7.4 线索二叉树 7.5 二叉树的应用1基本算法 7.6 二叉树的应用2哈夫曼树 7.7 二叉树的应用3二叉排序树 7.8 二叉树的应用3堆和堆排序,第7章 二叉树及其应用,7.2.1 二叉树的顺序存储 7.2.2 二叉树的链接存储 7.2.3 二叉树的建立,7.2 二叉树的存储,顺序存储 将一棵二叉树中的结点,按它们在完全二叉树中的编号顺序,依次存储在一维数组btn+1中;即编号为 i 的结点存储在数组中下标为 i 的元素中。 这样,根据性质5可知编号为 i 的结点,其左孩子下标为2i ,其右孩子下标
9、为2i +1,其父结点的下标为i/2。,例:如下二叉树的顺序存储。,a,先对二叉树中结点进行编号; 将二叉树存储在数组bt12中。,b,c,d,e,f,g,二叉树顺序存储的特点: 结点间关系蕴含在其存储位置中,无需附加任何信息就能在这种顺序存储结构里找到每个结点的双亲和孩子。 浪费空间,适于存储满二叉树和完全二叉树。,7.2.1 二叉树的顺序存储 7.2.2 二叉树的链接存储 7.2.3 二叉树的建立,7.2 二叉树的存储,二叉链表 对于任意的二叉树来说,每个结点只有两个孩子,一个双亲结点。我们可以设计每个结点至少包括三个域:数据域、 左孩子域和右孩子:,其中,lchild域指向该结点的左孩子
10、,data域记录该结点的信息,rchild域指向该结点的右孩子。,结点类型描述为: typedef struct node datatype data ; struct node *lchild , *rchild ; bitree ; 若定义一个 bitree 类型的指针变量 T,存放根结点的地址,则称 T 为根指针。 bitree *T ; 这时,一个二叉链表由根指针 T 唯一确定,称 二叉链表 T,例:右图二叉树的二叉链表,三叉链表 二叉树的链式存储中,有时,为了便于找到父结点,可以增加一个parent域, parent域指向该结点的父结点。 该结点结构如下:,typedef struc
11、t node datatype data; struct node *lchild, *rchild, *parent; JD;,不同的存储结构实现二叉树的操作也不同。 如要找某个结点的父结点,在三叉链表中很容易实现;在二叉链表中则需从根指针出发一一查找。 可见,在具体应用中,需要根据二叉树的形态和需要进行的操作来决定二叉树的存储结构。,7.2.1 二叉树的顺序存储 7.2.2 二叉树的链接存储 7.2.3 二叉树的建立,7.2 二叉树的存储,以建立一个二叉链表的方式生成一个二叉树 按完全二叉树的层次顺序,依次输入结点信息建立二叉链表。 算法思想: 依次输入结点信息,若其不是虚结点,则建立一个
12、新结点。 若新结点是第一个结点,则令其为根结点;否则将新结点作为孩子链接到它的父结点上。 重复 、 ,直至输入信息“”时为止。,具体实现: 为使新结点能正确地与其父结点链接,可设置一个队列,该队列是一个指针类型的数组,保存已输入的结点的地址。 且 front 指向当前与其孩子结点建立链接的父结点,rear 指向当前输入的结点。, 若rear 为偶数,则该结点为父结点的左孩子;若 rear 为奇数,则为父结点的右孩子。若父结点或孩子结点为虚结点,则无需链接。 若父结点与其两个孩子结点链接完毕,则做出队操作:front +1 . 初始值:front = 1; rear = 0 ;,a,b,ch=g
13、etchar( ); s=NULL; if(ch!=) s=malloc( ); s-data=ch; s-lchild=s-rchild=NULL; rear+; Qrear=s; if(rear=1) root=s,if(s,若输入的是虚结点则s为NULL,具体的算法如下: Bitree *Qmaxsize; /队列Q为指针类型 Bitree *creatree( ) /建立二叉树,返回根指针 char ch; int front, rear; bitree *root, *s; root =NULL; /置空二叉树 front = 1; rear = 0; /置空队列 ch = getc
14、har ( ); /输入第一个字符 While ( ch!=#) /不是结束符号时继续 s=NULL; /如果输入的是虚结点,则无需为虚结点申请空间,if ( ch ! =) /表示虚结点,不是虚结点时建立新结点 s = malloc( sizeof ( bitree) ); s-data=ch; s-lchild=s-rchild=NULL; rear+; Qrear=s; /将虚结点指针NULL或新结点地址入队 if (rear = =1) root=s; /输入的第一个结点为根结点 else if (s ,if ( rear %2= =1 ) front+; /结点* Qfront的两个
15、孩子已处理完毕front+1 ch = getchar( ); return root; ,7.1 二叉树的概念 7.2 二叉树的存储 7.3 二叉树的遍历 7.4 线索二叉树 7.5 二叉树的应用1基本算法 7.6 二叉树的应用2哈夫曼树 7.7 二叉树的应用3二叉排序树 7.8 二叉树的应用3堆和堆排序,第7章 二叉树及其应用,7.3 二叉树的遍历 7.3.1 二叉树遍历的概念 7.3.2 二叉树遍历的递归算法 7.3.3 二叉树遍历的非递归算法,二叉树的遍历 对一个二叉树,按某种次序访问其中每个结点一次且仅一次的过程称为二叉树的遍历。 二叉树的遍历算法是二叉树各种运算的基础。,遍历过程的
16、实现分析 1、 若二叉树 T 为空,则遍历结束。 2、 否则,假设二叉树的形态如图所示,且左右子树能分别遍历,则整个二叉树可按如下6种次序分别遍历出来:,(1) 访问根,遍历左子树,遍历右子树(记做DLR)。 (2) 访问根,遍历右子树,遍历左子树(记做DRL)。 (3) 遍历左子树,访问根,遍历右子树(记做LDR)。 (4) 遍历左子树,遍历右子树,访问根(记做LRD)。 (5) 遍历右子树,访问根,遍历左子树(记做RDL)。 (6) 遍历右子树,遍历左子树,访问根(记做RLD)。,我们称 D L R(根左右)、 D R L 为 先(根)序遍历 L D R(左根右)、 R D L 为 中(根
17、)序遍历 L R D(左右根)、 R L D 为 后(根)序遍历 先左后右 先右后左,关于左右子树的遍历,可采取与整个二叉树相同的方式来实现遍历。,下面,我们看具体的例子:,D L R,先序遍历序列:A B D C,先序遍历:,L D R,中序遍历序列:B D A C,中序遍历:,L R D,后序遍历序列: D B C A,后序遍历:,思考题:写出下图二叉树的遍历顺序,先序: A B D G C E H F,中序:DG B A EH C F,后序:GD B HE F C A,例:已知二叉树的先序和中序序列,构造出相应的二叉树 先序:ABCDEFGHIJ 中序:CDBFEAIHGJ 分析:由先序
18、序列确定根;由中序序列确定左右子树。 解:1、由先序知根为A,则由中序知左子树为CDBF, 右子树为IHGJ,先序:ABCDEFGHIJ 中序:CDBFEAIHGJ 2、再分别在左、右子树的序列中找出根、左子树序列、右子树序列。,先序:A BCDEF GHIJ 中序:CDBFE A IHGJ,7.3 二叉树的遍历 7.3.1 二叉树遍历的概念 7.3.2 二叉树遍历的递归算法 7.3.3 二叉树遍历的非递归算法,先序遍历(DLR)递归描述: 若二叉树为空, 则操作结束, 否则依次执行如下3个操作: (1) 访问根结点; (2) 先序遍历左子树; (3) 先序遍历右子树。 这里,若T为根指针,则
19、遍历左右子树时,是分别遍历以T-lchild 和T-rchild 为根指针的子树。 由于各子树的遍历和整个二叉树的遍历方式相同,因此,各子树的遍历可递归调用二叉树的遍历算法。,先序遍历递归算法如下: preorder ( bitree *T) if ( T ) visite ( T ); preorder ( T-lchild ) ; preorder ( T-rchild ) ; ,返回,返回,返回,返回,A,C,B,D,返回,先序序列:A B D C,中序遍历递归算法 inorder ( T ) inorder ( bitree *T) if ( T ) inorder ( T-lchil
20、d ) ; visite ( T ); inorder ( T-rchild ) ; ,后序遍历递归算法 postorder ( T ) postorder ( bitree *T) if ( T ) postorder ( T-lchild ) ; postorder ( T-rchild ) ; visite ( T ); ,7.3 二叉树的遍历 7.3.1 二叉树遍历的概念 7.3.2 二叉树遍历的递归算法 7.3.3 二叉树遍历的非递归算法,讨论:对如图所示的二叉树T,令p=T; (1)访问根,输出p-data;令p=T-lchild,先序遍历的非递归算法:,p,p,(2)访问根的左子
21、树p: 访问*p ,输出p-data 再访问以*p为根的左、右子树 问题:在访问*p的左、右子树时,如何保留*p的父结点 地址,以便在访问完*p的左、右子树后,再访问 其父结点的右子树?,p,解决的方法: 使用一个栈,将遍历过的结点的地址p依次入栈,并同时访问*p(p为栈顶元素)的左孩子;当访问过栈顶元素的右孩子后,将其出栈。 上例的二叉树的非递归先序遍历算法过程描述如下:,p,Visite(p); /访问A Push(p); /A的地址入栈 p=栈顶-lchid; /遍历A的左子树 Visite(p); /访问B Push(p); /B的地址入栈 p=栈顶-lchid; /遍历B的左子树 p
22、=NULL; /B的左子树为空 p=栈顶-rchid; /遍历B的右子树 Pop(top) /若访问到栈顶的右孩子则出栈 Visite(p); /访问D Push(p); /D的地址入栈,栈S,A的地址,p,B的地址,p,p,D的地址,D无左、右孩子,则D的地址出栈; p=栈顶-rchid; /遍历A的右子树 ,p,C的地址,中序遍历的非递归算法:,如何做到:在搜索线经过根时不访问根,而先访问根的左 子树?利用栈结构。 算法思想: 1、将根入栈,若其有左子树,则再将左子树的根入栈。,2、否则,访问该结点,并将栈中结点依次出栈并访问; 3、若栈为空,则访问最后一次出栈的结点的右子树,若其右子树不
23、空,重复1、2、3 。 4、否则,遍历结束。,后序遍历的非递归算法较为复杂, 不仅在搜索线第一次经过根结点时不访问并且进栈, 而且在后根遍历它的左子树之后, 搜索线第二次经根结点时也不能访问。因此, 在搜索线第二次经根结点时不能让栈顶元素(根)出栈, 而是依据栈顶元素所表示的根去后根遍历它的右子树; 直到搜索线第三次经过这个根结点时, 才将其出栈, 并且访问这个根结点。,后序遍历的非递归算法:,该算法中,对栈顶的每一个元素,要访问它的左右孩子后,才将其出栈。 即:要与栈顶元素接触两次后,才访问该元素。这样,可设置一个辅助变量用来记录接触该元素的次数。,7.1 二叉树的概念 7.2 二叉树的存储
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第七章 二叉树及其应用 第七 二叉 及其 应用
链接地址:https://www.31doc.com/p-5030384.html