数据结构树和二叉树教案

////////////////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 第六章树和二叉树 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 下面呢，我们就讨论第六章、树和二叉树。那么我们回忆一下数据结构四大类。第一类， 线性结构，除了广义表以外，我们都讨论完了。现在我们开始讨论第二大类，树形结构，在 ( 树形结构里面呢，我们主要讨论两种结构。一类树，一类二叉树线性结构里头我们讨论了 ) 什么？。 D 首先，我们先看树的数据类型定义。那先看数据对象：具有相同特性的数据元素的集 合，这就是它的数据对象。数据元素之间是一个什么样的关系呢，我们用下面这段话来描述。 如果数据对象是一个空集，我们称之为空树。从这里看得出来，所有的数据结构都这样一个 空的这样一个结构。空串、空表等等。空树的意思是一个数据元素都没有。否则的话，如果 root 这个集合不是一个空集的话，那么在这个数据结构里面一定存在一个成为根的数据元素， 而且这个数据元素一定是唯一的。就是说，一定存在，而且唯一。那么就是说除了空树以外， 如果数据集合里面只有一个数据元素的话，那么这个数据元素，就是这个树的根。如果说这 1m 个数据集合里面的元素个数大于的话，其余个结点呢，我们一定可以给它分成个子集。 这些子集互不相交。并且每个子集本身呢，又是一棵符合上面定义的树。这些子集是树，而 ABCDEFGIJ 且称之为根的子树。我们看一个例子，（画图）这是一个树，当然它不是空 9A 树，这个树呢是个数据元素的集合。一定存在这一个叫做根的结点。这个呢，我们称 BC 之为树根，除了这个根以外，我们可以分成这样三个集合。以开始的一个子集，以开 D 始的一个子集，和开始的一个子集。这三个子集互不相交，每个子集呢又是一棵树，并 且它和根呢，有一个关系存在，这棵树叫做根的子树。这棵树呢，又存在一个根结点，这 root 根和我们子树根之间，存在这一个这样一个前驱后继的关系，一般画树，我们不画箭头， BCDAB 但是我们讨论的是有向树，是有箭头的。就是说是的后继。那对于的这样一个子 树，又是符合我们定义的子树，那就是说它有一个根结点，它有两颗子树。在根结点和子树 EFE 根之间呢，又存在一个前驱和后继的关系，那对、来说，它们本身又是一颗树。对于 这棵树来说，它的数据元素只有一个，所以它是仅含有根结点的一颗子树。在定义的时候我 们说还有空树的，但是在实际使用的时候，是没有意义的。由于我们数据结构和离散数学还 是有一定的关系的，在离散数学中，为了一些数学上的完整性的定义，才有空树这样的定义， 在我们数据结构中也有定义，单实际上用处不大。这就是树的类型的一个结构特性。 下面我们本来就该讨论基本操作了，但是对于树来讲呢，还有一些基本术语介绍一下， 以便我们对基本操作的理解。下面就看有关树的基本术语。现在先来看一下有关树的术语。 树当中，它的基本单位是一个结点： + 什么叫结点呢：数据元素若干指向子树的分支 A+BCD 比如刚才我们举的那个例子，一个数据元素指向的子树的分支，那就称一个 结点。 结点的度：结点上指向分支的个数（在树上面每个结点的度可能是不一样的，比如我们 分解到只含有一个根结点的子树时，它没有子树也没有分支，那它的度就是零。对于刚才的 3. 根结点，它的度就是） ; 整个树的度我们定义为：整个树当中所有结点的度的最大值。对于我们刚才的那棵树 33. 呢，这棵树的度呢，就是，因为，结点最大的度是 叶子结点：对树来说，分解到最后，对于子树来说就一个根节点，度为零的结点。（也 就是只有一个根结点的子树。对于这样的一个结点，是没有子树的，它对于整个树来说，是