////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 第六章 树和二叉树 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 下面呢，我们就讨论第六章、树和二叉树。那么我们回忆一下数据结构四大类。第一类，线性结构，除了广义表以外，我们都讨论完了。现在我们开始讨论第二大类，树形结构，在树形结构里面呢，我们主要讨论两种结构。一类树，一类二叉树(线性结构里头我们讨论了什么？)。 首先，我们先看树的数据类型定义。那先看数据对象 D：具有相同特性的数据元素的集合，这就是它的数据对象。数据元素之间是一个什么样的关系呢，我们用下面这段话来描述。如果数据对象是一个空集，我们称之为空树。从这里看得出来，所有的数据结构都这样一个空的这样一个结构。空串、空表等等。空树的意思是一个数据元素都没有。否则的话，如果这个集合不是一个空集的话，那么在这个数据结构里面一定存在一个成为根的数据元素root，而且这个数据元素一定是唯一的。就是说，一定存在，而且唯一。那么就是说除了空树以外，如果数据集合里面只有一个数据元素的话，那么这个数据元素，就是这个树的根。如果说这个数据集合里面的元素个数大于 1 的话，其余个结点呢，我们一定可以给它分成 m个子集。这些子集互不相交。并且每个子集本身呢，又是一棵符合上面定义的树。这些子集是树，而且称之为根的子树。我们看一个例子，（画图）ABCDEFGIJ 这是一个树，当然它不是空树，这个树呢是 9 个数据元素的集合。一定存在这一个叫做根的结点。这个 A 呢，我们称之为树根，除了这个根以外，我们可以分成这样三个集合。以 B 开始的一个子集，以 C 开始的一个子集，和D 开始的一个子集。这三个子集互不相交，每个子集呢又是一棵树，并且它和根呢，有一个关系存在，这棵树叫做根的子树。这棵树呢，又存在一个根结点，这 root 根和我们子树根之间，存在这一个这样一个前驱后继的关系，一般画树，我们不画箭头，但是我们讨论的是有向树，是有箭头的。就是说 BCD 是 A 的后继。那对于 B 的这样一个子树，又是符合我们定义的子树，那就是说它有一个根结点，它有两颗子树。在根结点和子树根之间呢，又存在一个前驱和后继的关系，那对 E、F 来说，它...
