搜索
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////第六章树和二叉树//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////下面呢，我们就讨论第六章、树和二叉树。那么我们回忆一下数据结构四大类。第一类，线性结构，除了广义表以外，我们都讨论完了。现在我们开始讨论第二大类，树形结构，在树形结构里面呢，我们主要讨论两种结构。一类树，一类二叉树(线性结构里头我们讨论了什么？)。首先，我们先看树的数据类型定义。那先看数据对象D：具有相同特性的数据元素的集合，这就是它的数据对象。数据元素之间是一个什么样的关系呢，我们用下面这段话来描述。如果数据对象是一个空集，我们称之为空树。从这里看得出来，所有的数据结构都这样一个空的这样一个结构。空串、空表等等。空树的意思是一个数据元素都没有。否则的话，如果这个集合不是一个空集的话，那么在这个数据结构里面一定存在一个成为根的数据元素root，而且这个数据元素一定是唯一的。就是说，一定存在，而且唯一。那么就是说除了空树以外，如果数据集合里面只有一个数据元素的话，那么这个数据元素，就是这个树的根。如果说这个数据集合里面的元素个数大于1的话，其余个结点呢，我们一定可以给它分成m个子集。这些子集互不相交。并且每个子集本身呢，又是一棵符合上面定义的树。这些子集是树，而且称之为根的子树。我们看一个例子，（画图）ABCDEFGIJ这是一个树，当然它不是空树，这个树呢是9个数据元素的集合。一定存在这一个叫做根的结点。这个A呢，我们称之为树根，除了这个根以外，我们可以分成这样三个集合。以B开始的一个子集，以C开始的一个子集，和D开始的一个子集。这三个子集互不相交，每个子集呢又是一棵树，并且它和根呢，有一个关系存在，这棵树叫做根的子树。这棵树呢，又存在一个根结点，这root根和我们子树根之间，存在这一个这样一个前驱后继的关系，一般画树，我们不画箭头，但是我们讨论的是有向树，是有箭头的。就是说BCD是A的后继。那对于B的这样一个子树，又是符合我们定义的子树，那就是说它有一个根结点，它有两颗子树。在根结点和子树根之间呢，又存在一个前驱和后继的关系，那对E、F来说，它们本身又是一颗树。对于E这棵树来说，它的数据元素只有一个，所以它是仅含有根结点的一颗子树。在定义的时候我们说还有空树的，但是在实际使用的时候，是没有意义的。由于我们数据结构和离散数学还是有一定的关系的，在离散数学中，为了一些数学上的完整性的定义，才有空树这样的定义，在我们数据结构中也有定义，单实际上用处不大。这就是树的类型的一个结构特性。下面我们本来就该讨论基本操作了，但是对于树来讲呢，还有一些基本术语介绍一下，以便我们对基本操作的理解。下面就看有关树的基本术语。现在先来看一下有关树的术语。树当中，它的基本单位是一个结点：什么叫结点呢：数据元素+若干指向子树的分支比如刚才我们举的那个例子，一个数据元素A+指向BCD的子树的分支，那就称一个结点。结点的度：结点上指向分支的个数（在树上面每个结点的度可能是不一样的，比如我们分解到只含有一个根结点的子树时，它没有子树也没有分支，那它的度就是零。对于刚才的根结点，它的度就是3.）整个树的度;我们定义为：整个树当中所有结点的度的最大值。对于我们刚才的那棵树呢，这棵树的度呢，就是3，因为，结点最大的度是3.叶子结点：对树来说，分解到最后，对于子树来说就一个根节点，度为零的结点。（也就是只有一个根结点的子树。对于这样的一个结点，是没有子树的，它对于整个树来说，是很特殊的，叫做叶子结点。除了叶子结点，其他的结点的度都是大与零的。）反过来我们把它叫做分支结点：就是那些度大于零的结点。对于一棵树来说呢，我们经常要谈到的是，根结点，叶子结点、分支结点。当然了，根结点也是分支结点的一种。树呢，我们看是一个层次的结构，那从根结点，沿着分支呢，能走到任何一个结点。从根到这个结点所经过的分支和结点，构成了一条路径。这条路径叫从根到这个结点的路径。在树里面还有一些术语，根我们族谱里面的术语差不多。因为，树这样的一个结构，最早就是从族谱中的来的。有孩子结点、双亲结点、前面我们讲到了根和子树根的关系，是父子关系，或者是双亲和孩子的关系。对于树根来说，是树根的孩子，那么反过来，这个跟对子树根来说，它是双亲。兄弟结点呢，是有相同的根的子树，这些子树根之间的关系呢，就是兄弟关系了。它们有相同的双亲。有了兄弟结点，呢我们还可以得到堂兄弟结点。祖先结点的定义呢，我们说从根到结点有一条路径，这条路径有若干个结点，这些结点都是它的祖先。包括它的祖父、太祖父、等这些都是它的祖先。那子孙结点就是，在这棵根以下的结点，都是它的子孙结点。树是一个层次的关系：所以在树上的结点呢，它有它的层次，我们假设根结点的层次为1以下的结点呢，就依次类推了。那也就是说第l层的结点的子树根结点的层次为l+1层。从刚才这棵树看，A是第一层的，BCD是第二层的。EFG是第三层，的IJ是第四层。叶子结点最大的层次数，我们称之为树的深度。树的深度：树中叶子结点所在的最大层次，就是树的深度。这里面我们要强调一下，数据结构在这个树的层次上来讲呢，有时候约定是不一样的，有的书上把根结点的层数设为0，有的设为1.我们在这设定为1.这个时候呢。树的深度是不变的，还是最大层次数，叶子结点的层数变了，变成原来的层数减1.（在看别的书的时候，要看一下说明，如果根节点层为0的话，深度和最大的叶子节点层次数差1）那么在数据结构中呢，树和森林是不一样的，但又是两个密切相依赖的两个概念，森林呢，是M棵互不相交树的集合。反过来，从另外一个角度，树的定义可以由森林来定义。就是说任何一棵非空树是一个二元组T=（root，F）都是有一个根和子树森林构成的。（画图）比如（这样的一个树，我去掉了根结点，就可以看作是由3棵树构成的一个森林，这是一二三棵树。这个森林加上一个根，就是一颗树。反过来，森林又是树的集合。这个概念我们以后也会经常用到）下面我们看，树的基本操作。树的基本操作比较多，我们可以分为三类进行讨论，一类是查找，一类是插入，一类是删除。我们先看查找。查找呢一种是特定的查找一种是按关系查找，比如我们查树的根root(T)。或者找树上的某个结点返回它的值、或者是给一个值返回树上的这个结点。Value(T,cur_e)。一种是按关系的查找，有找双亲结点Parent(T,cur_e)。取这个结点的双亲。反过来，我们按照孩子的关系来找。树呢，有多个孩子，以后，我们会知道，我们是根据第一个孩子，和兄弟关系来找的。一个是每一个结点最左边的孩子，一个是每一个结点的右兄弟。那我们看，通过找这个结点的左孩子LeftChild(T,cur_e)，在找这个孩子结点的右兄弟RightSibling(T,cur_e)，当把有兄弟找完之后，这个结点的孩子结点就完全找到了。还有就是对树的特性进行的操作，一个是看树是不是为空TreeEmpty(T)。一个是树的深度TreeDepth(T)，还有一个树的重要操作呢，是树的遍历TraverseTree(T,Visit())。以上是根查找相关的操作。第二呢，我们看插入的操作，一，我们看初始化一个空树InitTree(&T)。二、还有根据定义来建立一颗树CreateTree(&T,definition)，这个定义呢，可以有各种给法，比如给一个root和一个森林。或者呢，我给树上的每个结点，结点的每个孩子结点，一直到叶子结点为止，这样也可以定义一个树。所以呢，我可以根据一个定义，创建一棵树。三、给树的某个结点赋予一个值Assign(T,cur_e,value)。第四个呢，插入一个孩子结点InsertChild(&T,&p,i,c)。就是在T这棵书上，在p所指的这个结点上，插入一个c的一个子树，位置呢，由i来确定。第三个呢，是关于删除的操作，这些操作包括，清空树ClearTree(&T)、销毁树DestroyTree(&T)，把树T中p结点的第i个孩子删除,DeleteChild(&T,&p,i).这是树的基本操作的定义。我们讨论的树呢我们要说明一下，我们讨论的树呢，是一个有向树。虽然我们画图的时候不画箭头，但是我们根和子树之间呢，有一个前驱和后继的关系，所以每一棵树1）有确定的根，2）树根和子树根之间有为有向的关系。一般就叫树，但实际上，讨论的是有向树。但是我们讨论的树和子树之间呢可以有次序，也可以无次序，子树之间是否存在次序关系，决定了我们这棵树是有序树，还是无序树。子树之间存在次序则是有序树，子树之间不存在次序则是无序树。我们看最早的例子，这里我们再画一颗树。这两棵树的差别在于哪里呢，差别不在于结构，9个元素，三个棵子树。只不过子树的次序位置变化了。如果你讨论的是无序树，那么这两棵树是相同的，如果你讨论的是有序树，那么这两棵树就不等同，通常我们讨论的树呢，都是无序树（除了你特殊说明以外）。因为我们树这个结构在我们非数值型程序领域，主要描述我们日常生活中的这种层次关系，也就是上下级的关系，而对同级来说呢，是不讲次序的。因此，我们讨论的主要是无序树，那也就是说在无序树底下，这两棵树是等同的。这个呢，我们说是有关树的一些定义。现在，我们把树这样一个结构呢，和线性结构来比较一下，首先我们看，线性结构，它肯定存在一个没有前驱的第一个数据元素，那么在树形结构里面，也存在这一个没有前驱的元素，就是这个根结点。这一点呢，和顺序结构是类似的。都存在一个没有前驱的数据元素。在线性结构里面，只有一个没有后继的线性数据元素，我们称之为最后一个元素，那么在树结构里面呢，就是度为零的结点，我们称之为叶子结点，在树里面，叶子结点就不是一个了。而可以有多个。其他的元素呢，在线性结构里面呢，都唯一有一个前驱，一个后继。树中的其他结点呢，分支节点，有一个前驱，可能有多个后继。所以我们说线性结构呢，是一种一对一的结构，而树形结构呢，是一种一对多的结构。从根开始，它可以有多个子树根，而每一个子树根上面只有一个双亲，底下呢，可以有多个孩子结点。一直到叶子结点呢，它没有后继。这就是从线性结构一对一的关系，扩展到树结构1对多的关系。以后我们会知道将树的结构再扩展到图的结构。那么这个就是关于树的类型定义。当然我们一般情况下，就该讨论树的实现和操作了，但是由于树的结构有它的不确定性，就是说它每个结点的度呢是可以不同的，它处理起来呢，相对来说比较麻烦一些。在这种情况下，我们就讨论一种结构相对固定的树，也就是下面我们要将的二叉树，在以后我们会知道对树的这样一种结构我们会转化为二叉树来讨论的。所以我们下面就要从新看一下二叉树的类型的定义。第二个问题，二叉树的类型定义。二叉树的定义呢，我们就不按照数据对象、和数据关系来说了，简单的看一下文字的描述就可以了，这样比较简洁。二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成的。（画一个二叉树的例子）二叉树也一定有一个根结点。除了根结点以外，其他结点分成两个互不相交的结点的集合。每一个集合是根的子树，同时它本身又是满足定义的一颗二叉树。二叉树的定义上有非常重要的一句话。就是这棵二叉树叫做根的左子树。这棵二叉树叫做根的右子树。那么我们再看二叉树的定义，虽然每个根结点只有两棵子树，这两棵子树都有特定的含义，一个叫左子树，一个叫右子树。当然这个左、右子树本身又可以是空树。比如B这个二叉树，它是由一个空的左子树和一个不空的右子树组成的。二C这个二叉树是由一个不空的左子树和空的右子树构成的。同样对于D这棵树，它是由左右都为空的二叉树构