树和二叉树的基本知识

Jsoi2006春季函授B层次讲义（3）常州市第一中学林厚从1/35树和二叉树的基本知识树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。树型结构在现实世界中广泛存在，如把一个家族看作为一棵树，树中的结点为家族成员的姓名及相关信息，树中的关系为父子关系，即父亲是儿子的前驱，儿子是父亲的后继；把一个国家或一个地区的各级行政区划分看作为一棵树，树中的结点为行政区的名称及相关信息，树中的关系为上下级关系，如一个城市包含有若干个区，每个区又包含有若干个街道，每个街道又包含有若干个居委会；把一本书的结构看作是一棵树，树中的结点为书、章、节的名称及相关信息，树中的关系为包含关系。树在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构；在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。在许多算法中，常用树型结构描述问题的求解过程、所有解的状态和求解的对策等。在树型结构中，二叉树是最常用的结构，它的分支个数确定，又可以为空，具有良好的递归特性，特别适宜于程序设计，因此我们常常将一般树型结构转换成二叉树进行处理。第一节树一、树的定义一棵树（tree）是由n（n0）个元素组成的有限集合，其中：1．每个元素称为结点(node)；2．有一个特定的结点，称为根结点或树根（root）；3．除根结点外，其余结点被分成m（m=0）个互不相交的有限集合T0,T1,T2,……Tm-1，而每一个子集Ti又都是一棵树（称为原树的子树subtree）。图1图1就是一棵典型的树结构。从树的定义可以看出：1．树是递归定义的，这就决定了树的操作和应用大都是采用递归思想来解决；2．一棵树中至少有1个结点，这个结点就是根结点，如上图中的结点1；3．只有根结点没有前趋结点，其余每个结点都有唯一的一个前趋结点；4．所有结点都可以有0或多个后继结点；二、树的基本概念下面以图1为例给出树结构中的一些基本概念：1．一个结点的子树个数，称为这个结点的度（degree），如结点1的度为3，结点3的度为0。度为0的结点称为叶结点（又称树叶leaf，如结点3、5、6、8、9）。度不为0的结点称为分支结点（如结点1、2、4、7）。根结点以外的分支结点又称为内部结点（如结点2、4、7）。树中各结点的度的最大值称为这棵树的度（又称宽度），图1所示这棵树的（宽）度为3。2．在用上述图形表示的树结构中，对两个用线段（称为树枝）连接的相关联的结点，称上端的结点为下端结点的父结点，称下端的结点为上端结点的子结点，称同一个父结点的多个子结点为兄弟结点。如结点1是结点2、3、4的父结点，结点2、3、4都是结点1的子结点，它们又是兄弟结点，同时结点2又是结点5、6的父结点。称从根结点到某个子结点所经过的所有结点为这个子结点的祖先。如结点1、4、7是结点8的祖先。称以某个结点为根的子树中的任一结点都是该结点的子孙。如结点7、8、9都是结点4的子孙。3．定义一棵树的根结点的层次（level）为1，其它结点的层次等于它的父结点的层次数加1。如结点2、3、4的层次为2，结点5、6、7的层次为3，结点8、9的层次为4。一棵树中所有结点的层次的最大值称为树的深度（depth），图1所示这棵树的深度为4。4．若树中各结点的子树是按照一定的次序从左向右安排的，它们之间的次序不能互换，这样的树称之为有序树，否则称之为无序树。所以，树虽然是非线性结构，但也是有序结构。例如，对于下面图2中的两棵树，若看作为无序树，则是相同的；若看作为有序树，则是不同的，因为根结点A的两棵子树的次序不同。又如对于一棵反映了父子关系的家族树，兄弟结点之间是按照排行大小而有序排列的，所以它是一棵有序树。因为任何无序树都可以当作具有任一次序的有序树来处理，所以下面如果不特别指明，均认为树是有序的。图25.对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1。如图1中，结点1和结点8之间存在着一条路径，并可用（1、4、7、8）表示这条路径，该条路径的长度为3。从根结点出发，到树中的其余结点一定存在着一条路径。注意，不同子树上的结点之间不存在路径。但是，如果把树看成是一个图的话(可以把树理解为是图的一个子类)，那么我们就可以继承图的路径的定义，认为不同子树上的两个结点应该是有路径的（图论意义上的路径）。6．森林（forest）是m(m=0)棵互不相交的树的集合。三、树的表示方法和存储结构树的表示方法有多种，如图1采用的就是一种形象的树形表示法；另外还有一种常用的表示方法“括号表示法”，它的表示方法归纳如下：先将整棵树的根结点放入一对圆括号中，然后把它的子树由左至右放入括号中，同层子树用圆括号括在一起（同层子树之间用逗号隔开），而对子树也采用同样的方法处理，直到所有的子树都只有一个根结点为止。用括号表示法表示图1的步骤如下：=（T）=（1（T1，T2，T3））{A是根结点，有3棵子树，用逗号隔开}=（1（2（T11，T12），3，4（T31）））{分别对3棵子树做同样的操作}=（1（2（5，6），3，4（7（T311，T312））））=（1（2（5，6），3，4（7（8，9））））实际上，以上方法是按照树的层次逐步展开，直到所有结点都已列出。树的存储结构也有多种形式，其中使用较多的采是链式存储结构，下面给出几种常见的存储树的数据结构。1．父亲表示法：定义一个数组，每个数组元素为一个记录，除了存放一个结点的数据信息外，还存放该结点的父结点编号。数据结构定义如下：Constm=10；{树的结点数}Typenode=Recorddata:Integer；{数据域}parent:Integer；{指针域}End；Vartree:Array[1..m]Ofnode；这种方法充分利用了树中除根结点外每个结点都有唯一的父结点这个性质，很容易找到树根（可以规定根结点的父结点为0），但找孩子时却需要遍历整个线性表。2．孩子表示法：利用单链表，每个结点包括一个数据域和若干个指针域，每个指针都指向一个孩子结点。由于一般树的各个结点的孩子数不确定，所以指针数应该等于整棵树的度。当树的度越大时，空指针域所占比例也越大，给存储空间造成很大浪费。假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下：Constm=10；{树的度}Typetree=^node；node=Recorddata:Char；{数据域}child:Array[1..m]Oftree{指针域，指向若干孩子结点}End；Vart:tree；注：空间上的浪费其实可以用“虚开实用”的方法完美地解决，在FreePascal等环境下可以用Getmem、Freemem等过程达到这个目的，这样建立一棵普通树的时间复杂度也是很不错的。有兴趣的同学可以参考有关书籍与程序。由于每个结点都只存放各自孩子结点的编号，所以这种方法只能从根（父）结点遍历到子结点，不能从某个子结点返回到它的父结点。3．父亲孩子表示法：利用双链表结构，每个结点包括一个数据域和二个指针域，一个指向该结点的若干孩子结点，一个指向其父结点。克服了上述第1种存储方法的缺点，假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下：Constm=10；Typetree=^node；node=Recorddata:Char；child:Array[1..m]Oftree；father:treeEnd；Vart:tree；4．孩子兄弟表示法：有些程序中需要对兄弟结点进行处理，这种情况下，可以使用另外一种双链表结构，每个结点包括一个数据域和二个指针域，一个指针指向该结点的第一个孩子结点，一个指针指向该结点的下一个兄弟结点。克服了上述第2种存储方法的缺点，假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下：Typetree=^node；node=Recorddata:Char；firstchild,next:tree；End；Vart:tree；四、树的遍历在应用树结构解决问题时，往往需要按照某种次序获得树中全部结点的信息，这种操作叫做“树的遍历”。遍历一般按照从左向右的顺序，常用的遍历方法有：1．先序（根）遍历：先访问根结点，再从左到右按照先序思想遍历各棵子树。图1先序遍历的结果为：{1，2，5，6，3，4，7，8，9}；2．后序（根）遍历：先从左到右遍历各棵子树，再访问根结点。图1后序遍历的结果为：{5，6，2，3，8，9，7，4，1}；3．层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的次序。图1层次遍历的结果为：{1，2，3，4，5，6，7，8，9}；4．叶结点遍历：有时我们把所有的数据信息都存放在叶结点中，而其余结点都是用来表示数据之间的某种分支或层次关系，这种情况就用这种方法。图1按照这个思想访问的结果为：{5，6，3，8，9}；很明显，先序遍历和后序遍历两种方法的定义是递归的，所以在程序实现时往往也是采用递归的思想，既通常所说的“深度优先搜索”。按照先序遍历思想编写的递归过程如下：Proceduretra1(t,m){访问以t为根结点的含有m棵子树的过程}BeginIftNilThenBeginWrite(t^.data,’’)；{访问根结点}ForI:=1TomDo{前序遍历各子树}tra1(t^.child[I],m)；End；End；也可以用堆栈的方法编写这个程序，留给读者作为练习。层次遍历应用也较多，实际上就是我们所说的“广度优先搜索”。思想如下：若某个结点被访问，则该结点的子结点应被记录下来，等待被访问。顺序访问各层次上结点，直至不再有未访问过的结点。为此，引入一个队列来存储等待访问的子结点，设一个队首和队尾指针分别表示出队、进队的下标。程序框架如下：Constn=100；Varhead,tail,i:integer；q:array[1..n]oftree；p:tree；Begintail:=1；head:=1；{初始化}q[tail]:=t；tail:=tail+1；{t进队}While(headtail)doBegin{队列非空}p:=q[head]；head:=head+1；{取出队首结点}Write(p^.data,‘‘)；{访问某结点}Fori:=1TomDo{该结点的所有子结点按顺序进队}Ifp^.child[i]NilThenBeginq[tail]:=p^.child[I]；tail:=tail+1；End；End；End；例1：单词查找树[问题描述]在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：1．根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母；2．从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词；3．在满足上述条件下，该单词查找树的结点数最少。4．例如图3左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。[问题输入]输入文件名为word.in，该文件为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成，长度不超过63个字母。文件总长度不超过32K，至少有一行数据。[问题输出]输出文件名为word.out，该文件中仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。[样例输入]AANASPASASCASCIIBASBASIC[样例输出]13图3[算法分析]首先要对建树的过程有一个了解。对于当前被处理的单词和当前树：在根结点的子结点中找单词的第一位字母，若存在则进而在该结点的子结点中寻找第二位……如此下去直到单词结束，即不需要在该树中添加结点；或单词的第n位不能