第四章树与树的表示(一)

4.1树与树的表示树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。本章将详细讨论树和二叉树数据结构，主要介绍树和二叉树的概念、术语，二叉树的遍历算法。树和二叉树的各种存储结构以及建立在各种存储结构上的操作及应用等。什么是树客观世界中许多事物存在层次关系人类社会家谱社会组织结构图书信息管理什么是树分层次组织在管理上具有更高的效率!数据管理的基本操作之一：查找如何实现有效率的查找？查找（Searching）查找：根据某个给定关键字K，从集合R中找出关键字与K相同的记录静态查找：集合中记录是固定的没有插入和删除操作，只有查找动态查找：集合中记录是动态变化的除查找，还可能发生插入和删除45689静态查找0K方法1：顺序查找(数组存储）Tbl10123intSequentialSearch(StaticTable*Tbl,ElementTypeK){/*在表Tbl[1]~Tbl[n]中查找关键字为K的数据元素*/}inti;Tbl-Element[0]=K;/*建立哨兵*/for(i=Tbl-Length;Tbl-Element[i]!=K;i--);returni;/*查找成功返回所在单元下标；不成功返回0*/顺序查找算法的时间复杂度为O(n)。710方法2：二分查找（BinarySearch)假设n个数据元素的关键字满足有序（比如：小到大）并且是连续存放（数组），那么可以进行二分查找。[例]假设有13个数据元素，按关键字由小到大顺序存放.二分查找关健字为444的数据元素过程如下：51639455198100202226321368444501123456789101112131、left=1,right=13;mid=(1+13)/2=7:2、left=mid+1=8,right=13;mid=(8+13)/2=10:100444;321444;3、left=mid+1=11,right=13;mid=(11+13)/2=12:查找结束;二分查找算法intBinarySearch(StaticTable*Tbl,ElementTypeK){/*在表Tbl中查找关键字为K的数据元素*/intleft,right,mid,NoFound=-1;left=1;right=Tbl-Length;/*初始左边界*//*初始右边界*/while(left=right){mid=(left+right)/2;/*计算中间元素坐标*/if(KTbl-Element[mid])right=mid-1;/*调整右边界*/elseif(KTbl-Element[mid])left=mid+1;/*调整左边界*/elsereturnmid;}returnNotFound;/*查找成功，返回数据元素的下标*//*查找不成功，返回-1*/}二分查找算法具有对数的时间复杂度O(logN)[例]仍然以上面13个数据元素构成的有序线性表为例二分查找关健字为43的数据元素如下：51639455198100202226321368444501123456789101112131、left=1,right=13;mid=(1+13)/2=7:10043;2、left=1,right=mid-1=6;mid=(1+6)/2=3:3943;3、left=mid+1=4,right=6;mid=(4+6)/2=5:5143;4、left=4,right=mid-1=4;mid=(4+4)/2=4:4543;5、left=4,right=mid-1=3;leftright?查找失败，结束;611个元素的二分查找判定树判定树上每个结点需要的查找次数刚好为该结点所在的层数;查找成功时查找次数不会超过判39定树的深度n个结点的判定树的深度14710为[log2n]+1.ASL=(4*4+4*3+2*2+1)/11=325811二分查找的启示？LM4.2树的定义树（Tree）:n（n≥0）个结点构成的有限集合。当n=0时，称为空树；对于任一棵非空树（n0），它具备以下性质：树中有一个称为“根（Root）”的特殊结点，用r表示；其余结点可分为m(m0)个互不相交的有限集T1，T2，...，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”ABCDEFBGCHIDJKEFGLHIMJK(b)子树TA1(c)子树TA2(d)子树TA3(e)子树TA4(a)树TD树与非树?AAABCDBCDBCDEFGHEFGHEFGH子树是不相交的；除了根结点外，每个结点有且仅有一个父结点；一棵N个结点的树有N-1条边。IJKMA树的一些基本术语1.结点的度（Degree）：结点的子树个数2.树的度：树的所有结点中最大的度数3.叶结点（Leaf）：度为0的结点4.父结点（Parent）：有子树的结点是其子树BCD的根结点的父结点FGHIJK5.子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。6.兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。LMA树的一些基本术语7.路径和路径长度：从结点n1到nk的路径为一个结点序列n1,n2,…,nk,ni是ni+1的父结点。路径所包含边的个数为路径的长度。8.祖先结点(Ancestor)：沿树根到某一结点路BCD径上的所有结点都是这个结点的祖先结点。9.子孙结点(Descendant)：某一结点的子树FGHIJK中的所有结点是这个结点的子孙。10.结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。11.树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度。LM12.有序树和无序树：对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为有序树，否则称为无序树。13.森林(forest)：是m(m≧0)棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。树的表示ABCDEFGHIJKLMBEFKLACDGHIJM儿子-兄弟表示法ElementFirstChildNextSiblingAANBCDEFGHIJBCDNKLMEFNNGNNHNIJNNKNLNNMNNAN45BCDNEFNNGNNHINJNNKNLNNElementMNNLeftLeftRight二叉树Right4.2二叉树及存储结构二叉树(Binarytree)是n(n≥0)个结点的有限集合。若n=0时称为空树，否则：⑴有且只有一个特殊的称为树的根(Root)结点；⑵若n1时，其余的结点被分成为二个互不相交的子集T1,T2，分别称之为左、右子树，并且左、右子树又都是二叉树。由此可知，二叉树的定义是递归的。二叉树具体五种基本形态ФTLTRTLTR(a)(b)(c)(d)(e)二叉树的子树有左右顺序之分空树只含根结点右子树为空树左子树为空树左右子树均不为空树特殊二叉树斜二叉树(SkewedBinaryTree)A完美二叉树(PerfectBinaryTree)满二叉树(FullBinaryTree）1AB23C4B56C7DEFGD89101112131415完全二叉树(CompleteBinaryTree)有n个结点的二叉树，对树中结点按HIJ2KL1AMN3O从上至下、从左到右顺序进行编号，编号为i（1≤i≤n）结点与满二叉树中编号为i结点在二叉树中位置相同84DB95E106FC7GHJK894101151213614157213894101152112673(a)满二叉树(b)完全二叉树1362455674213(c)非完全二叉树图6-4特殊形态的二叉树二叉树几个重要性质性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)性质2：深度为k的二叉树上至多含2k-1个结点。(k≥1)性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，A则必存在关系式：n0=n2+1。BCDJEKFHn0=4，n1=2n2=3；n0=n2+1满二叉树的特点：◆基本特点是每一层上的结点数总是最大结点数。◆满二叉树的所有的支结点都有左、右子树。◆可对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。完全二叉树(CompleteBinaryTree)：如果深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树。其中2k-1≦n≦2k-1。完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。完全二叉树的特点：若完全二叉树的深度为k，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。性质4：n个结点的完全二叉树深度为：㏒2n+1。其中符号：x表示不大于x的最大整数。x表示不小于x的最小整数。,二叉树的抽象数据类型定义类型名称：二叉树数据对象集：一个有穷的结点集合。若不为空，则由根结点和其左、右二叉子树组成。操作集：BTBinTree,ItemElementType，重要操作有：1、BooleanIsEmpty(BinTreeBT)：判别BT是否为空；2、voidTraversal(BinTreeBT)：遍历，按某顺序访问每个结点；3、BinTreeCreatBinTree()：创建一个二叉树。常用的遍历方法有：voidPreOrderTraversal(BinTreeBT)：先序----根、左子树、右子树；voidInOrderTraversal(BinTreeBT)：中序---左子树、根、右子树；voidPostOrderTraversal(BinTreeBT)：后序---左子树、右子树、根voidLevelOrderTraversal(BinTreeBT)：层次遍历，从上到下、从左到右5/25二叉树的存储结构1.顺序存储结构用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i的分量中。结点序号A1B2O3C4S5M6Q7W8K9n个结点的完全二叉树的结点父子关系：非根结点（序号i≥1）的父结点的序号是i/2;当i/2=0时，该结点是树的根结点。结点（序号为i）的左孩子结点的序号是2i，（若2in，没有左孩子）;结点（序号为i）的右孩子结点的序号是2i+1，（若2i+1n，没有右孩子）;一般二叉树也可以采用这种结构，但会造成空间浪费……1A2A3BO4B56O7MMC8910111213C(a)一般二叉树(b)对应的完全二叉树结点ABO∧∧M∧∧∧∧∧∧C序号12345678910111213造成空间浪费！I2.链表存储typedefstructTreeNode*BinTree;LeftDataRighttypedefBinTreePosition;structTreeNode{ElementTypeData;BinTreeLeft;BinTreeRight;data}ALeftARightBCBCDFGDFGIEHEH