《软件技术基础》- 数据结构(树形结构)

讲课人：刘伟电子邮件：[e-mail]@gmail.com电话：[phone]办公室：教二南楼328室软件技术基础数据结构树形结构本章基本内容与要求基本内容树的基本概念及存储结构二叉树概念二叉树的存储结构二叉树的操作二叉排序树树形结构在日常生活和计算机科学中无处不在。日常生活：家谱、机关结构图……计算机科学：目录树、计算机游戏（如DOOM等射击类游戏）……一、树的基本概念1.1树的定义1．定义树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n0，则：（1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；（2）除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。树的基本概念及存储结构西汉皇帝谱系树程序调用自身的编程技巧称为递归（recursion）。一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。注意：(1)递归就是在过程或函数里调用自身;(2)在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。AABCDIHGFEJKLMa）空树b）仅含有根结点的树c）含有多个结点的树图4-1树的示意图Ø树的基本概念及存储结构在图4-1c中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图4-2，并且可以进一步分解T0，T1，T2。CGBEFJKLDHIMa)T0子树b)T1子树c)T2子树图4-2图4-1c的树的三个子树2．树的逻辑结构描述一棵树的逻辑结构可以用二元组描述为：tree=(T,R)T={Ti∣1≤i≤n;n≥0,Tielemtype}R={r}其中，n为树中结点个数，若n=0，则为一棵空树，n0时称为一棵非空树，而关系r应满足下列条件：（1）有且仅有一个结点没有前驱,称该结点为树根;（2）除根结点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继(孩子结点)。例如，对图4-1(c)的树结构,可以二元组表示为：T={A，B，C，D，E，F，G，H，I，J，K，L，M}R={r}r={(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M)}1.2基本术语1.结点指树中的一个数据元素，一般用一个字母表示。A,B,C…2.度一个结点包含子树的数目，称为该结点的度。A节点的度为33.树叶（叶子）度为0的结点，称为叶子结点或树叶，也叫终端结点。图中4-1C中：J,K,L,F,G,M…4.孩子结点若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。B、C、D是A节点孩子5.双亲结点若结点X有子女Y，则X为Y的双亲结点。A是节点B、C、D双亲6.祖先结点从根结点到该结点所经过分枝上的所有结点为该结点的祖先。M的祖先有A，D，H。7.子孙结点某一结点的子女及子女的子女都为该结点子孙。8.兄弟结点具有同一个双亲的结点，称为兄弟结点。B、C、D为兄弟9.分枝结点除叶子结点外的所有结点，为分枝结点，也叫非终端结点。B,C,D,E,H为分枝节点10．层数根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。11.树的高度（深度）树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。12.树的度树中结点度的最大值称为树的度。13.有序树若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。14.无序树若一棵树中所有子树的次序无关紧要，则称为无序树。15．森林（树林）若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。森林示例图例A根结点B是D和E双亲C、B为兄弟D、E是B的孩子D,E,F,G,I叶结点A,B,C,H分枝结点E的层数为3树的高度或深度为4B的度为2树的度为3I的祖先A,C,HC的子孙F,G,H,IABCHIDEFG层数1234Property:(边数)=(结点数)-1为什么？树中除了根结点外每个结点有且仅有一个父结点，子结点和父结点间有且仅有一条边。1.3树的存储结构AB^C^^D^EF^^G^^^H^^I^^^J^^^K^^^L^^^M^^^通常采用链式存储eg.采用同构型存储，每个节点按照树的度定义指针域个数二、二叉树2.1二叉树的定义1．二叉树的定义和树结构定义类似，二叉树的定义也可以递归形式给出：二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有五种不同的形态，参见图4-5。二叉树概念(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树图4.5二叉树的5种形式二叉树的5种基本形态，图(c)和图（d）是不同的两棵二叉树。1.满二叉树：二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。2.完全二叉树如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，则称这棵二叉树为完全二叉树。从完全二叉树定义可知：2.2两种特殊的二叉树结点的排列顺序遵循从上到下、从左到右的规律。满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。深度为4的满二叉树和完全二叉树如图4-6所示。ABCDEFGHIJKLMNOABCDEGHF（a）满二叉树(b)完全二叉树图4-6满二叉树和完全二叉树示意图123456(a)非完全二叉树12345(b)非完全二叉树非完全二叉树2.3二叉树的性质性质1若二叉树的层数从1开始，则二叉树的第k层结点数，最多为2k-1个（k0）。可以用数学归纳法证明之。性质2深度（高度）为k的二叉树最大结点数为2k-1（k0）。证明：深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和。既为20+21+…+2k-1=2k-1。性质3对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。证明：设二叉树中度为1的结点个数为n1，根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2。又因为在二叉树中，二叉树的孩子结点数为n0*0+n1*1+n2*2，加上根结点后，总的结点数：n=n0*0+n1*1+n2*2+1，因此,有n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。性质4具有n个结点的完全二叉树高度为[log2（n+1）]。(注意[x]表示对x取整。)证明：可根据性质2推出。性质5如果对一棵有n个结点的满二叉树和完全二叉树按从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，对任一结点j（1=j=n),有：①如果j＝1，则结点j无双亲，是二叉树的根；如果j1，则其双亲是结点[j/2]。（取整是直接取整，舍去小数部分）②如果2j≤n，则结点j为分支结点，其左子结点是2j；否则，该结点为叶子结点，无左子树。③如果2j＋1≤n，则结点j为分支结点，其右子结点是结点2j＋1；否则，该结点为叶子结点，无右子树。[j/2]jj+12j2j+12(j+1)2j+3深度为5的二叉树至多有()个结点。A.16B.32C.31D.10【例题1】【例题2】2.4树、森林和二叉树的转换可以分为三步：（1）连线指相邻兄弟之间连线。（2）抹线指抹掉双亲与除左孩子外其它孩子之间的连线。（3）旋转只需将树作适当的旋转。（顺时针旋转45°）具体实现过程见图４-25。1．树转换成二叉树2．森林转换成二叉树（1）将森林中每一棵树分别转换成二叉树（前2步）（2）将各二叉树的根结点视为兄弟从左至右连在一起(3)顺时针转45度AEGBCDFHIGHIABCDFE左孩子右兄弟【例题3】【例题4】三、二叉树的存贮结构3.1．顺序存贮结构将一棵二叉树按完全二叉树顺序存放到一个一维数组中，若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。如图6-7给出了顺序存贮形式。ABCDEFGABCD...ABCDEFGABCD01234567890123456(a)完全二叉树的存储形式(b)非完全二叉树的存储形式图4-7二叉树的顺序存储形式对于一棵二叉树,若采用顺序存贮时,当它为完全二叉树时,比较方便,若为非完全二叉树,将会浪费大量存贮存贮单元。因此，对于非完全二叉树，宜采用链式存储结构。3.2．二叉链表存贮结构（1）二叉链表表示将一个结点分成三部分,一部分存放结点本身信息,另外两部分为指针,分别存放左、右孩子的地址。二叉链表中一个结点可描述为:LchilddataRchild对于图４-7所示二叉树,用二叉链表形式描述见图4-8。ABC^D^^E^^F^^G^rootA^root^BC^^D^(a)完全二叉树的链表(b)非完全二叉树的二叉链表图4-8二叉树的二叉链表表示法1.概念二叉树的遍历是指按照一定的次序访问树中所有结点，并且每个结点仅被访问一次。它是最基本的运算，是二叉树中其他所有运算的基础。在二叉树中，左子树和右子树是有严格区别的，因此在遍历一棵非空二叉树时，根据访问根结点，遍历左子树和遍历右子树之间的先后关系，可以得到6种遍历方法。若按先左后右的原则，则通常使用下面三种遍历方法，见表4-1。四、二叉树的操作4.1二叉树遍历先序遍历1访问根结点2先序遍历左子树3先序遍历右子树中序遍历1中序遍历左子树2访问根结点3中序遍历右子树后序遍历1后序遍历左子树2后序遍历右子树3访问根结点表4-1遍历方法表层次序遍历：按照结点的层次，依次遍历每一层次的所有结点。ABDCBEACDFGa)b)4-11b：先序遍历：ABCDEFG中序遍历：CBDAEGF后序遍历：CDBGFEA层次遍历：ABECDFG4-11a：先序遍历：ABDC中序遍历：BDAC后序遍历：DBCA层次遍历：ABCD4.2.2二叉树遍历算法的实现2.算法实现链式存储结构二叉树的定义：structbitree{elemtypedata;//elemtype：结点数据类型bitree*lchild;bitree*rchild;};voidpreorde(bitree*root){if(root!=NULL){coutroot-data;preorde(root-lchild);preorde(root-rchild);}}（1）先序遍历二叉树算法中序遍历也是一个递归过程，对于一棵二叉树，其过程为：1）中序遍历左子树，2）访问根结点，3）中序遍历右子树，直到二叉树为空时退出。算法描述如下：（2）中序遍历二叉树算法voidinorder(bitree*root){if(root!=NULL){inorder(root-lchild);coutroot-data;inorder(root-rchild);}}同样是一个递归过程，对于一棵二叉树，其过程为：1）后序遍历左子树，后序2）后序遍历右子树，3）访问根结点，直到二叉树为空时退出。算法描述如下：(3)后序遍历voidpostor