【数据结构】二叉树

在了解二叉树之前先知道什么是树（tree），树结构是数据结构中一种非常重要的结构，应用很广，在很多系统程序中都有使用。

树结构和线性结构不同，可以把很多复杂的问题抽象成树结构，比如一个公司的人员组织架构，一个家庭的族谱，所以树结构可以表示一个层次关系，这种层次关系就是可以用树结构来表示。

树（tree）结构的定义：

树结构是一种描述非线性层次关系的数据结构，树是由n个数据节点的集合，在该集合中包含一个根节点，根节点下面分布着一些不交叉的子集合，这些子集合就是根节点的子树。树结构的示例图如下：

图一

从图一中可以看到一个类似于起来像一棵倒挂的树，越往下根系越多，可以看到节点A是根节点，它有3个直接后继节点B C D，而B节点只有一个直接前驱节点A。

一个树结构可以为空，次数树结构就没有节点，是一个空集合。如果树结构只包含一个节点，那么这也是一个树，根节点就是该节点自身。

从数学的角度来看，树具有递归的特性。在树中的每个结点及其之后的所有结点构成一个子树，这个子树也包括根结。

树结构的特点：

在一个树结构中，有且只有一个节点没有直接前驱，那么这个节点就是树的根节点。
除了根节点之外，每个节点有且只有一个直接前驱。
每个节点可以有多个直接后驱。

树的基本概念：

父结点和子结点：每个结点的子树的根称为该结点的子结点，相应地，该结点被称的父结点。
兄弟结点：具有同一父结点的结点称为兄弟结点。结点的度:一个结点所包含子树的数量。
树的度：是指该树所有结点中最大的度。
叶结点：树中度为零的结点称为叶结点或终端结点。
分支结点：树中度不为零的结点称为分枝结点或非终端结点。
结点的层数：结点的层数从树根开始计算，根结点为第1层、依次向下为第2、3层。我们知道树是一种层次结构，每个结点都处在一定的层次上..树的深度:树中结点的最大层数称为树的深度。
有序树：若树中各结点的子树(兄弟结点)是按一定次序从左向右安排的，称为有序树。
无序树：若树中各结点的子树(兄弟结点)未按定次序安排，称为无序树。.
森林： m (m>0)棵互不相交的树的集合。

下面，我们可以根据一个例子来看上述树结构的基本概念。

图二

图二所示为一个基本的树结构，节点A为根节点。结点A有3个子树，因此，结点A的度为3.同理，节点E有两个子的度为2。所有结点中，节点A的度为3最大，因此整个树的度为3。节点E是节点K和节点L的父结点，结点K和结点L是结点目的了结点，结点K和结点L之间为兄弟结点。

在这个树结构中，节点G、节点H、节点K、节点J、节点N、节点O、节点P和节点Q都是叶节点。其余的都是分支节点，整个树的深度为4.除去根节点A，留下的子树就构成了一个森林。

由于树结构不是种线性结构，一般来说，常采用层次括号法来表示。层次括号法的基本规则如下：

根节点放入对圆括号中。
根节点的子树由左至右的顺序放入括号中。
对子树做上述相同的处理。

这样，同层子树与它的根节点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。按照这种方法，图二所示的树结构可以表示成如下形式:：

（A（B（E（K,L（O）））,C（G,F（J））,D（H,I（M（P,Q）,N））））

二叉树

在树结构中，二叉树是最简单的种形式。在研究树结构的时候，二叉树是重点。因为一二叉树的描述相对简单，处理也相对简单，而且更为重要的是任意的树都可以转换成对应的二义树。因此，二.叉树是所有树结构的基础。

什么是二叉树

二叉树是树结构的种特殊形式，其是n个结点的集合，每个结点最多只能有两个了结点。二叉树的子树仍然是二又树。二叉树的一个节点上对应的两个子树分别称为左子树和右了树。由于子树有左右之分，因此二叉树是有序树。

从这个定义可以看出，在普遍的树结构中，结点的最大度数没有限制，而二叉树结点的最大度数为2.另外，树结构中没有左子树和右子树的区分，而二叉树中则有这个区别。一个二叉树结构也可以是空，此时空二叉树中没有数据结点，也就是一个空集合。如果二叉树结构中仅包含一个结点，那么这也是一个二叉树，树根便是该节点自身。
另外，依照子树的位置的个数，二叉树还有如下几种形式，如图三所示。

图三

其中，对于图(a),只有一个子节点且位于左子树位置，右子树位置为空，对于图(b)，只有一个子结点且位于右子树位置，左子树位置为空，对于图(c)，具有完整的两个子节点，也就是左子树和右子树都存在。
对于般的二又树，在树结构中可能包含上述的各种形式。按照上述二又树的这几种形式来看，为了研究的方便，叉树还可以进一步细分为两种特列的类型，满二叉树和完全二叉树。

对于满二叉树，就是在二叉树中除了最下一层的叶节点外，每层的节点都有两个子节点。典型的满二叉树如图四：