数据结构（树形结构 树与二叉树）

在树形结构中，其数据元素之间的逻辑关系是一对多的非线性关系，且呈现层次结构。树形结构的特点是，一个数据结构可以有多个后继，但每个元素只能有唯一的前驱，最上层的元素（树根）没有前驱。

二叉树是树的一种特殊形式，树形结构和二叉树结构之间可以互相转换。

树形结构

树：一棵树（Tree）T是由n（n>=）0个结点组成的有限集合。如果n=0，则称为空树。如果n>0，有且仅有一个特定的结点root，则称为数T的根节点，其余节点可被划分为m（m>=0）个不相交的子集，其中的每个子集都是一棵树，称为T的子树。

结点：树中的每个元素称为结点。

结点的度：结点拥有的子树个数称为结点的度。A结点的度为2，B结点的度是3.

叶子结点：度为0的结点称为叶子结点或终端结点。D、E、F、I、J、H都是叶子结点。

分支结点：度不为0的结点称为分支结点或非终端结点。A、B、C、D、E是分支结点。

树的度：树的度是书中各节点的度的最大值。该树的度是3。

孩子结点：一个结点的后继结点（子树）称为该结点的孩子结点。B和C是A的孩子。

双亲结点：一个结点称为其后继结点的双亲节点。A是B和C的双亲结点。

兄弟结点：同一个双亲的孩子之间互称兄弟。B和C是兄弟结点。

祖先结点：结点的祖先是从根到该结点所经分支上的所有结点。结点J的祖先节点是E、B、A。

子孙节点：以某结点为根的子树中的任一结点都称为该结点的子孙。B结点的子孙是D、E、F、I、J。

结点层数：从根节点开始，根为第一层，根的孩子为第二层，如此下去，直到最下面一层。结点A的层数是1，结点B、C的层数是2。

树的高度：树中结点的最大层数称为树的高度或深度。树的最大层数是4层，因此树的高度是4。

有序树和无序树：如果将树中的结点的各子树看成从左至右是有次序的，则称该数为有序树，否则称为无序树。

森林：由m（m>=0）棵树组成的集合称为森林。

树的存储结构

树的存储不仅要存储树中的结点的信息，而且还要存储表示结点间关系的信息。由于结点之间的关系有父子关系、兄弟关系等，因此在实际应用中，可以采用多种形式的存储结构来表示数。

顺序存储结构

树的顺序存储结构采用双亲数组表示法。

一棵具有n个结点的树，如果存储每个结点的信息，并且存储每个结点的双亲信息信息，那么这棵树也就唯一地确定了。假设以一组地址连续的空间（数组）存储结点的双亲信息，每个结点设置data和parent两个信息项。其中parent用来存储结点的双亲信息，而一个结点的双亲信息可以用其双亲结点在树中结点的序号表示，即存储双亲结点的位置。

（最上面的树形结构图）

树的双亲数组存储结构

树的这种存储表示方法便于寻找双亲结点的操作，但是当要查找孩子结点时，则必须扫描整个数组。

链式存储结构

链式存储采用指针方式指向孩子结点或双亲结点，分为孩子链表表示法和双亲链表表示法。

1）孩子链表表示法

孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。孩子结点的数据域仅存放它们在向量空间的序号。以这样的方式存储便于实现设计孩子及其子孙的运算，但不便于实现与双亲有关的运算。

2）双亲链表表示法

与孩子链表表示法相对应的是双亲链表表示法，可记录双亲结点的向量序号。将双亲数组表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。

在实际应用中，为了提高空间利用率和降低算法设计难度，通常不处理一般的树和森林，而只对二叉树进行操作，因为一般的树和森林与二叉树可以互相转化。

二叉树

二叉树是一种很重要的非线性数据结构，它的特点是，每个结点最多有两棵子树，且其子树有左右之分（次序不能任意颠倒）。

二叉树的基本概念

二叉树（BinaryTree）是n（n>=0）个结点的有限集，它或者是空集（n=0），或者由一个根节点及两棵互不相交的分别称为这个根节点的左子树和右子树的两棵子树组成。

二叉树中的每个结点最多有两个孩子，分别称为该结点的左孩子和右孩子。

二叉树的基本形态

二叉树有五种基本形态，a）空二叉树；b）仅有根节点的二叉树；c）右子树为空的二叉树；d）左子树为空的二叉树；e）左、右子树均不为空的二叉树

二叉树的五种基本形态

满二叉树、完全二叉树及平衡二叉树

1）满二叉树

除了叶子结点外每一个结点都有左孩子和右孩子，且叶结点都处在最底层的二叉树称为满二叉树。

满二叉树具有以下特点

①每一层上的结点数都达到最大值。如果给定二叉树的高度，则满二叉树是具有最多结点树的二叉树。
②满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下面。

2）完全二叉树

只有最下面的两层节点的度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树称为完全二叉树。

完全二叉树有如下特征

①在完全二叉树的最下面一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树
②在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必定是叶结点
③满二叉树是完全二叉树，完全二叉树未必是满二叉树。

3）平衡二叉树

平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差绝对不超过1，这样的二叉树就是平衡二叉树。