树

无论是线性表也好，栈和队列也罢，都是一对一的线性结构，都是2P模式。
而树是一种一对多的数据结构。

一、定义

树(Tree)是n(n>=0)个结点的有限集。当n=0时成为空树，在任意一棵非空树中：

• 有且仅有一个特定的称为根(Root)的结点；
• 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、...、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。
• n>0时，根结点是唯一的，坚决不可能存在多个根结点。
• m>0时，子树的个数是没有限制的，但它们互相是一定不会相交的。

树.png

1.结点

每一个圈圈我们就称为树的一个结点。结点拥有的子树数称为结点的度-(Degree)，树的度取树内各结点的度的最大值。

• 度为0的结点称为叶结点(Leaf)或终端结点；
• 度不为0的结点称为分支结点或非终端结点，除根结点外，分支结点也称为内部结点。

结点分类.png

2.结点间的关系

结点的子树的根称为结点的孩子(Child)，
相应的，该结点称为孩子的双亲(Parent)，
同一双亲的孩子之间互称为兄弟(Sibling)。

结点的祖先是从根到该结点所经分支上的所有结点。

3.结点的层次

结点的层次(Level)从根开始定一起，根为第一层，根的孩子为第二层。
其双亲在同一层的结点互为堂兄弟。
树中结点的最大层次称为树的深度(Depth)或高度。

结点的层次.png

二、树的存储结构

1.双亲表示法

双亲表示法，言外之意就是以双亲作为索引的关键词的一种存储方式。
我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示其双亲结点在数组中位置的元素。
也就是说，每个结点除了知道自己是谁之外，还知道它的爸爸妈妈在哪里。

定义：

// 树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct PTNode
{
    ElemType data;  // 结点数据
    int parent;     // 双亲位置
}PTNode;

typedef struct
{
    PTNode nodes[MAX_TREE_SIZE];
    int r;          // 根的位置
    int n;          // 结点数目
}PTree;

双亲表示法.png

这样的存储结构，我们可以根据某结点的parent指针找到它的双亲结点，所用的时间复杂度是O(1)，索引到parent的值为-1时，表示找到了树结点的根。如果我们要知道某结点的孩子，则要遍历整个树结构。

针对此种情况进行改进：只需要稍微改变一下结构即可：

改进版双亲表示法.png

它们兄弟之间的关系如图：

兄弟之间的关系.png

一个存储结构设计得是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等等。

2.孩子表示法

换个角度来考虑，由于树中每个结点可能有多棵子树，可以考虑用多重链表来实现。

方案一：根据树的度，声明足够空间存放子树指针的结点。

方案一.png

此种方法缺点十分明显，就是造成了浪费！

方案二：

方案二.png

此种方案做到了不浪费，但每个结点的度的值不同，初始化和维护起来难度都很大。

方案三：

方案三.png

3.双亲孩子表示法

双亲孩子表示法.png

代码实现：

#define MAX_TREE_SIZE   100

typedef char ElemType;

// 孩子结点
typedef struct CTNode
{
    int child;              // 孩子结点的下标
    struct CTNode *next;    // 指向下一个孩子结点的指针
} *ChildPtr;

// 表头结构
typedef struct
{   
    ElemType data;          // 存放在树中的结点的数据
    int parent;             // 存放双亲的下标
    ChildPtr firstchild;    // 指向第一个孩子的指针
} CTBox;

// 树结构
typedef struct
{
    CTBox nodes[MAX_TREE_SIZE]; // 结点数组
    int r, n;
}

4.孩子兄弟表示法