原来你是这样的数据结构之树结构

什么是树结构

树结构是一种描述非线性层次关系的数据结构,其中主要的是树的概念,树是n个数据结点的集合,在该集合中包含一个根结点,根结点之下分布这一些互不交叉的子集合,这些子集合是根结点的子树,它的结构特征如下:

• 在树结构中,有且仅有一个结点没有直接前驱,这个前驱就是树的根结点.
• 除根结点外,其余每个结点有且仅有一个直接前驱.
• 每个结点可以有任意多个直接后继.

上图就是一个典型的树结构,就像现实中树的根系,其中A结点是树的根结点,根结点A有三个直接后继结点B,C,D,而结点B,C,D他们都只有一个前驱结点A.

一个树结构也可以是空的，此时空树中没有数据结点，也就是一个空集合，如果树结构中仅包含一个结点，那么这也是一个树，树根便是该结点自身。

树的基本概念

父结点和子结点：每个结点子树的根称为该结点的子结点，响应的，该结点称为其子结点的父结点。
兄弟结点：具有同一父结点的结点称为兄弟结点。
结点的度：一个结点所包含子树的数量。
树的度：是指该树所有结点中最大的度。
叶结点：树中度为零的结点称为叶结点或终端结点。
分之结点：树中度不为零的结点称为分之结点或非终端结点。
结点的层数：结点的层数从数根开始计算，根结点为第一层，依次向下为第2,3,....层(树一种层次结点，每个结点都出在一定的层次上)。
树的深度：树中结点的最大层数称为树的深度。
有序数：若树中各结点的子树(兄弟结点)是按一定次序从左向右排列的，称为有序树。
无序树：若树中各结点的子树(兄弟结点)未按依定次序排列，称为无序树。
森林：n棵互不相交的树的集合。

二叉树

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

1.什么是二叉树

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

普遍的树结构中，结点的最大度数是没有限制的，而二叉树结点的最大度数为2，另外，树结构中没有左子树和右子树的区别。

一个二叉树的结构可以是空的，此时空二叉树中没有数据结点，是一个空集合。如果二叉树结构中仅包含一个结点，这么这也是一个二叉树，树根便是该结点本身。

二叉树还可以进一步细分为两种特殊的类型：
满二叉树和完全二叉树。

满二叉树：

满二叉树即在二叉树中除最下一层的叶结点外，每层的结点都有两个子结点。

完全二叉树

完全二叉树记载二叉树中除二叉树最后一层歪，其他各层的结点数据都达到最大个数，且最后一层结点按照从左向右的顺序连续存在，只缺最后一层右侧若干结点。

2.完全二叉树的性质

对于完全二叉树，若树中包含n个结点，假设这些结点按照顺序方式存储，那么，对于任意一个结点m来说，具有如下性质。

• 如果m!=1,则结点m的父结点的编号为m/2;
• 如果2m<=n ,则结点m的左子树根结点编号为2m;若r*m>n,则没有左子树，也没有右子树；
• 如果2m+1<=n,则结点m的右子树根结点编号为2m+1;若2*m+1>n,则无右子树。
• 对于完全二叉树，其深度为[log2n]+1.

这些基本性质展示了完全二叉树结构的特点，在完全二叉树的存储方式及运算处理上都有重要意义。
按照数据的存储方式，树结构可以分为顺序存储结构和链式存储结构。

3.二叉树的顺序存储

顺序存储方式是最基本的数据存储方式。和线性表类似，树结构的顺序存储一般采用一维数组来表示，这里的关键是定义合适的次序来存放树中各个层次的数据。

image

先来分析完全二叉树的顺序存储，上面的这个图每个结点的数据都是字符类型，如果采用顺序存储方式，可以将其按层来存储，即先存储根结点，然后从左往右一次存储下一层结点的数据，直到所有的结点数据完全存储。
[A,B,C,D,F,G,H]
上述二叉树顺序存储结构的数据定义，可以采用如下形式：

static final int MAXLEN = 100;              //最大结点数
char [] SeqBinTree = new Char9[MAXLEN];     //定义保存二叉树数组

二叉树的链式存储

与线性结构的链式存储类型，二叉树的链式存储结构包含结点元素及分布指向左子树和右子树的引用。典型的二叉树的链式存储结构如下：

class ChainTreeType
{
    char NodeData;                          //元素数据
    ChainTreeType LSonNode;                 //左子树
    ChainTreeType RSonNode;                 //右子树
}

ChainTreeType root = null;                  //根结点

有时候，为了后续计算的方便，也可以保存一个该结点的父结点的引用，此时二叉树的链式存储结构包含了结点元素，指向父结点的引用及分别指向左子树和右子树的引用，这种带父引用的链式存储结构代码如下：

class ChainTreeType
{
    char NodeData;                          //元素数据
    ChainTreeType LSonNode;                 //左子树
    ChainTreeType RSonNode;                 //右子树
    CharinTreeType ParentNode;              //父结点引用
}

ChainTreeType root = null;                  //根结点

上述就是树结构及二叉树的基本内容，下一篇我们用链式存储结构来实现一个二叉树。