树是一种重要的线性结构.docx

树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用,如在编译源程序如下时,可用树表示源源程序如下的语法结构。又如在数据库系统中,树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。一、树的概述树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。(一)树的定义树是由一个或多个结点组成的有限集合,其中:⒈必有一个特定的称为根(ROOT)的结点;⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、......Tn,而且,这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。树的递归定义如下:(1)至少有一个结点(称为根)(2)——也即是宽度,简单地说,就是结点的分支数。以组成该树各结点中最大的度作为该树的度,如上图的树,其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。——组成该树各结点的最大层次,如上图,其深度为4;——指若干棵互不相交的树的集合,如上图,去掉根结点A,其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林;——指树中同层结点从左到右有次序排列,它们之间的次序不能互换,这样的树称为有序树,否则称为无序树。,常用的方法是用括号:先将根结点放入一对圆括号中,然后把它的子树由左至右的顺序放入括号中,而对子树也采用同样的方法处理;同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。如上图可写成如下形式:(A(B(E(K,L),F),C(G),D(H(M),I,J))):二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:(1)空二叉树——(a);(2)只有一个根结点的二叉树——(b);(3)右子树为空的二叉树——(c);(4)左子树为空的二叉树——(d);(5)完全二叉树——(e)注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。:(1)完全二叉树——只有最下面的两层结点度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树;(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。(1)在二叉树中,第i层的结点总数不超过2^(i-1);(2)深度为h的二叉树最多有2^h-1个结点(h>=1),最少有h个结点;(3)对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;(4)具有n个结点的完全二叉树的深度为int(log2n)+1(5)有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:若I为结点编号则如果I<>1,则其父结点的编号为I/2;如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子;如果2