树（Tree）

本文主要是对数据结构中非线性结构 树 的学习和总结。

树的定义

专业定义：

1.有且只有一个称为根的节点
2.有若干个互不相交的子树，这些子树本身也是一棵树

通俗的定义：

1.树由节点和边组成
2.每一个节点只有一个父节点但可以有多个子节点
3.当有一个节点例外，该节点没有父节点，该节点称为根节点

专业术语：

节点  父节点  子节点  子孙  堂兄弟  
深度：从根节点到最底层节点的层数称之为深度。  根节点是第一层
叶子节点：没有子节点的节点
非终端节点： 实际就是非叶子节点
度： 子节点的个数称为度  

树的分类

• 一般树： 任意一个节点的子节点个数都不受限制。
• 二叉树：任意一个节点的子节点个数最多两个，且子节点的个数不可更改。
  1. 一般二叉树
  2. 满二叉树：在不增加树的层数的前提下，无法再添加一个节点的二叉树称为满二叉树。
  3. 完全二叉树：如果只是删除了满二叉树最低存最右边的若干个连续节点，这样形成的二叉树就是完全二叉树。
• 森林：n个互不相交的树的集合。

树的存储

二叉树的存储

连续存储【完全二叉树】
1. 优点： 查找某个节点的父节点和子节点（也包括有没有子节点）。
2. 缺点：耗用内存空间过大。
链试存储
1. 优点：耗用内存空间小。

一般树的存储
1.双亲表示法： 求父节点方便。

树结构.png
树的双亲表示法.png

代码结构定义

//树的双亲表示法节点结构的定义
#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;

上面的树存储结构图根据某个节点的parent指针找到它的双亲节点，所用的时间复杂度为O(1),索引到parent的值为-1，表示找到了树节点的根。如果我们要知道某个节点的孩子节点，就的遍历整个树结构了。
下面是改进后的树结构存储图，可以比较方便的求出某个节点的孩子节点。

图片.png

改进过后的树存储结构，没法表示树结构中兄弟之间的关系？
如下是改进过后最终的树结构存储图：

图片.png

2.孩子表示法：求子节点方便， 求父节点麻烦。存储结构如下：

图片.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.二叉树表示法：把一个普通树转化成二叉树来存储
具体转换方法（把一个普通树转化成二叉树）：设法保证任意一个节点的左指针域指向他的第一个孩子，右指针域指向他的下一个兄弟，只要能满足此条件就能把一个普通的树转换成二叉树，一个普通树转换成二叉树一定没有右子树。

森林的存储

先把森林转化为二叉树，再存储二叉树    

树的操作

遍历

先序遍历【先访问根节点】： 先访问根节点，再先序访问左子树，再先序访问右子树
中序遍历【中间访问根节点】：中序遍历左子树，再访问根节点，再中序遍历右子树
后序遍历【最后访问根节点】：先中序遍历左子树，中序遍历右子树，再访问根节点

已知两种遍历序列求原始二叉树

通过先序和中序或者中序和后序我们可以还原出原始二叉树，但 `通过先序和后序是无法还原出原始的二叉树` 
换种说法：只有通过先序和中序，或通过中序和后序，我们才可以唯一的确定一个二叉树。

应用

1. 树是数据库中数据组织一种重要的形式
2. 操作系统子父进程的关系本身就是一棵树
3. 面向对象语言中类的继承关系
4. 赫夫曼树      

树的遍历相关算法的实现（C语言）

#include <stdio.h>
#include <stdlib.h>

//定义二叉树的节点
struct BTNode {
    int data; //存放二叉树节点的数据域
    struct BTNode *pLchild; //指向左孩子结点的指针
    struct BTNode *pRchild; //指向右孩子结点的指针
};

//创建一颗二叉树，返回头结点的指针
struct BTNode *CreateBTree(void);
//先序遍历二叉树
void PreTraverseBTree(struct BTNode *pT);
//中序遍历二叉树
void InTraverseBTee(struct BTNode *pT);
//后续遍历二叉树
void PostTraverseBTree(struct BTNode *pT);


struct BTNode *CreateBTree(void)
{
    struct BTNode * pA = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode * pB = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode * pC = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode * pD = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode * pE = (struct BTNode*)malloc(sizeof(struct BTNode));
    
    pA->data = 'A';
    pB->data = 'B';
    pC->data = 'C';
    pD->data = 'D';
    pE->data = 'E';
    
    pA->pLchild = pB;
    pA->pRchild = pC;
    pB->pLchild = pB->pRchild = NULL;
    pC->pLchild = pD;
    pC->pRchild = NULL;
    pD->pLchild = NULL;
    pD->pRchild = pE;
    pE->pLchild = pE->pRchild = NULL;
    return pA;
}

void PreTraverseBTree(struct BTNode *pT) {
    //先访问根节点 再先序访问左子树 再先序访问右子树
    if (pT == NULL)
    {
        return;
    }
    printf("%c\n", pT->data);
    PreTraverseBTree(pT->pLchild);
    PreTraverseBTree(pT->pRchild);
}

void InTraverseBTee(struct BTNode *pT) {
    //先访问根节点 再先序访问左子树 再先序访问右子树
    if (pT == NULL)
    {
        return;
    }
    InTraverseBTee(pT->pLchild);
    printf("%c\n", pT->data);
    InTraverseBTee(pT->pRchild);
}

void PostTraverseBTree(struct BTNode *pT) {
    //先访问根节点 再先序访问左子树 再先序访问右子树
    if (pT == NULL)
    {
        return;
    }
    PostTraverseBTree(pT->pLchild);
    PostTraverseBTree(pT->pRchild);
    printf("%c\n", pT->data); 
}

int main() {
    struct BTNode *pT = CreateBTree();
    printf("先序遍历\n");
    PreTraverseBTree(pT);
    printf("中序遍历\n");
    InTraverseBTee(pT);
    printf("后序遍历\n");
    PostTraverseBTree(pT);
    return 0;
}