数据结构 第七章 树和二叉树VIP免费

第七章树和二叉树7.1树的基本概念7.2二叉树概念和性质7.3二叉树遍历7.4二叉树的基本运算及其实现7.5二叉树与树的转换7.6线索二叉树7.7哈夫曼树7.8并查集问题7.1树的基本概念树的定义树的表示相关术语树的存储树的定义树是由n(n≥0)个结点组成的有限集合(记为T)。其中：如果n=0,它是一棵空树,这是树的特例；如果n>0,这n个结点中存在(有仅存在)一个结点作为树的根结点,简称为根(root),其余结点可分为m(m>0)个互不相交的有限集T1,,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树。树的表示——树型表示法ACGJBEDFIHMKL树形表示法相关术语结点的度与树的度树中某个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度,通常将度为m的树称为m叉树。相关术语分支结点与叶结点度不为零的结点称为非终端结点,又叫分支结点度为零的结点称为终端结点或叶结点在分支结点中,每个结点的分支数就是该结点的度如对于度为1的结点,其分支数为1,被称为单分支结点；对于度为2的结点,其分支数为2,被称为双分支结点相关术语孩子结点、双亲结点和兄弟结点在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女结点)该结点被称作孩子结点的双亲结点(或父母结点)。具有同一双亲的孩子结点互为兄弟结点把每个结点的所有子树中的结点称为该结点的子孙结点从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。相关术语结点的层次和树的高度结点的层次从树根开始定义,根结点为第1层,它的孩子结点为第2层,以此类推,一个结点所在的层次为其双亲结点所在的层次加1树中结点的最大层次称为树的高度(或树的深度)。相关术语有序树和无序树若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则称为有序树,否则称为无序树森林n(n＞0)个互不相交的树的集合称为森林相关术语路径与路径长度对于任意两个结点ki和kj,若树中存在一个结点序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由ki到kj的一条路径,用路径所通过的结点序列(ki,ki1,ki2,…,kj)表示这条路径。路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。7.2二叉树概念和性质二叉树的概念二叉树的性质二叉树的存储二叉树的概念定义二叉树是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树的概念5种形态(a)(b)(c)(d)(e)二叉树的概念满二叉树在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉树的最下一层,这样的二叉树称为满二叉树。完全二叉树若二叉树中最多只有最下面两层的结点的度数可以小于2,并且最下面一层的叶结点都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树ABCDEHIJKFGLMNO123456789101511121314满二叉树ABCDEHIJKFG1234567891011完全二叉树二叉树的性质性质1非空二叉树上第i层上至多有2i-1个结点,这里应有i≥1。性质2高度为h的二叉树至多有2h-1个结点(h≥1)。性质3非空二叉树上结点数满足：n0=n2+1二叉树的性质性质4具有n个(n＞0)结点的完全二叉树的高度为log2n+1或log2n+1。性质5对完全二叉树中编号为i的结点(1≤i≤n,n≥1,n为结点数)若i=1，则i为根结点，无双亲；否则结点i的双亲为i/2若2i