本文主要是对数据结构中非线性结构 树 的学习和总结。
树的定义
专业定义：
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;
}
