《软件技术基础：树与叉树》由会员分享，可在线阅读，更多相关《软件技术基础：树与叉树（24页珍藏版）》请在金锄头文库上搜索。
1、2.5树与二叉树树型结构是一类很重要的非线性数据结构，在这类结构中，元素结点之间 存在明显的分支和层次关系。2.5.1 树的定义及其存储结构1. 树的定义和术语树是由n个(n 0)结点组成的有限集合T,其中有且仅有一个结点称 为根结点(root)，其余结点可以分为m(m0)个互不相交的有限集合Ti, T2，Tm其中每个集合Ti本身又是一棵树，称为根结点root的子树。 当n=0时称为空树 。矚慫润厲钐瘗睞枥庑赖。这是一个递归的描述，即在买偶数树时又用到树本身这个术语。图 2.33所示为一棵树，A为根结点，期于结点分为三个不相交的子集Ti, T2, T3,它们均为根结点A下的三棵树，而这三棵树本
2、身也是树 。聞創沟燴鐺險爱氇谴争。图2.33树用二元组关系来定义树为Tree=(T,R)数据结构树(Tree)由数据元素集合T及各种R组成，其中T是具有相同 类型的数据元素集合T =x 1, X2，Xn。若T为空集(T二?)，则R二？, 称为空树，否则R是T上某个二元关系H的集合，即R=H。H的描述如 下： 残骛楼諍锩瀨濟溆塹籟。(1) 在T中存在唯一的称为根的元素root，它在H关系下无前趋。 若root工？，则存在m个子集Ti, T2，T(m0),对任意 的j zk(1 j,k m), 有Tj ATk= ?，则存在唯一的数据元素Xi Ti(1 i m),满足 H。 酽锕极額閉镇桧猪訣锥。
3、对应于 Ti, T2，Tm, H-,，满 足vroot , Xi H, H2,，Hm(m0)，对任意的 j k(1 j,k 0)棵互不相交的树的集合。.有序树：树中结点在同层中按从左至右有序排列、不能互换的称为 有序树，反之称为无序树。2. 树的存储结构仅讨论链式存储结构。异构型：节省存储空间，运算不便。同构型：运算方便，浪费空间。假设有一棵具有n个结点的k叉树，则有nk个指针域，其中有用的指针 域为n-1个，因此空链域个数为nk-(n-1)=n( k-1)+1个 。鹅娅尽損鹤惨歷茏鴛賴。图234树的链式结构不同的k值进行比较比喘）T =12n+l3nn+12nk越大，空链域比例越高，k=2时
4、比例最低，因此着重讨论二叉树结构。2.5.2二叉树及其性质1. 二叉树定义及其存储结构二叉树是n(n 0)个结点的有限集合，它或为空树n=0)，或由一个 根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成籟丛妈 羥为贍贲蛏练淨。通常用具有两个指针域的链表作为二叉树的存储结构其中每个结点由 数据域(data)、左指针域(L child)和右指针域(R child) 组成，即預頌圣鉉儐歲龈讶骅籴L childdataR child二叉树的链表结构如图2.35(b)所示心)(b)图2.3 5二叉树2. 二叉树的基本性质(1) 二叉树的第I层上至多有2i-1 (i 1)个结点。1 , 21-1
5、. 2, 22-1 :(2) 深度为h的二叉树中至多含有2h-1个结点。1, 21-1 . 2, 22-1 20+21+22+23+2h-1 =1+2 0+21+22+23+2h-1 -1(3) 在任意二叉树中，若有n个叶子结点，n2个度为2的结点，则必有：no=n2+1。每增加一个度为2的结点，叶子结点就增加一个。3. 几种特殊形式的二叉树(1) 满二叉树：深度为h含有2h-1个结点的二叉树为满二叉树。图2.36所示为一棵深度为4的满二叉树。完全二叉树如果一棵n个结点的二叉树，按与满二叉树相同的编号方式对结点进行编号，若树中n个结点和满二叉树1n编号完全一致, 则称该树 为完全二叉树，如图2
6、.37(a)所示；而图2.37(b) 就不是完全二叉树。 渗釤呛俨匀谔鱉调硯錦。6(710) (11砂 Q2)(时图2.37完全二叉厠与非完全二丈树(3)平衡二叉树平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树:它 的左子树和右子树都是平衡二叉树，且左子树和右子树的深度 之差的绝对值不超过1。图2.38(a)为平衡二叉树，(b)为不N2 3S平街二叉树与非平衡二叉柳4. 一般树转换为二叉树(1) 在兄弟结点之间加一连线；(2) 对每个结点，除了与它的第一个孩子保持联系外去除与其它孩 子的联系；以树根为轴心，将整棵树顺时针旋转45 。图29 F树海换为二叉拥D)ABCDEFGCBDAEGF
7、图2-40遍历二叉树二叉树的遍历遍历是指遵循某条搜索路线，依次访问某数据结构中的全部结点，而且每 个结点只被访问一次。1. 遍历二叉树的定义DLR, LDR LRD, DRL，RDL，RLD六种遍历形式。若规定先左后右，则归并成下述三种形式：DLR:先序遍历LDR:中序遍历LRD:后序遍历以图2.40中的二叉树为例，三种遍历结果为: 先序：中序： 后序：GG1CC1DD1FFFFFF1BBBBBB1B1B1B1EE1E1E1E1E1E1E1E1E1AAAAAAAAAAAA1A1A1A1A1A1A1A1A1A1A1A1A1ABCDEFG先CBDAEGF中CDBGFEA后2. 遍历算法PROORD
8、ER(p)/ 先序遍历/1.if (pnil) then2. write(data(p); /访问根结点/遍历左子树遍历右子树3. PROORDER (L child(p);/4. PROORDER (R child(p);/FRFR1BRBR1ERER1ER1ER1ER1ER1ARARARARARAR1AR1AR1AR1AR1AR1AR1AR1AR1ABC顎轮烂蔷。G擁締凤袜备訊INORDER(p)/ 中序遍历1.if (pnil) then2. INORDER(L,child(p); /遍历左子树3. write (data(p); /访问根结点7/5. ReturnFRFR1BRBR1E
9、RER1ER1ER1ER1ER1ARARParARARAR1AR1AR1AR1AR1:AR1:AR1AR1AR1C B D AEGFPOSTORDER(p)/ 后序遍历1.if (pnil) then2. POSTORDER(L,child(p); /遍历左子树/3. POSTORDER(R,child(p); /遍历右子树/4. write (data(p); /访问根结点7/5. ReturnFRFR1BRBR1ERER1ER1ER1ER1ER1ARARARARARAR1:AR1AR1AR1AR1AR1AR1:AR1AR1CDBG F E A 贓熱俣阃歲匱阊邺镓騷。统计二叉树中的叶子结点数
10、/p指向根结点count为计数器，初值为01.if (pnil) then2. if (Lchild(p)=nil) and (R child=nil)3. the n count co unt +14. COUNTLEFT(L,child(p);5. COUNTLEFT(R,child(p);6. return(co unt)2.5.4二叉树的应用1. 二叉排序树(1)定义二叉排序树或是空树，或是具有下述性质的二叉树：其左子树上所有结点的数据均小于根结点的数据值；右子树上所有结点的数据值均大于或 等于根结点的数据值。左子树和右子树又各是一棵二叉排序树。图2.41在二叉排序树中，若按中序遍历就可以得到由小到大的有序序列，如 图2.41 中的二叉排序树，中序遍历可得到有序序列 2,3,4,8,9,9,10,13,15,18,21。蜡變黲癟報伥铉锚鈰赘。(2) 二叉排序树的生成二叉排序树是一种动态表结构，即二叉排序树的生成过程是不断地向 二叉排序树中插入新的结点。对任意的一组数据元素序列R1, R2,，Rn,要生成一棵二叉排序 树的过程为：令R1为二叉排序树的根结点。若RR1,令R2为R1的左子树的根结点；否则R2为R1的右子 树的根结点。R3,，Rn结点的插入方法同上。二叉排序树插入算法如
