一、定义
1 专业定义
有且只有一个称为根的节点有若干各互不相交的子树，这些子树本身也是一棵树
2 通俗定义
树是由节点和边组成。每个节点只有一个父节点，但是可以由多个字节点。但有一个节点例外，该节点没有父节点，此节点称为根节点。
3 专业术语
节点 父节点 子节点 子孙 堂兄弟 深度：从根节点到最底层节点的层数称为深度（根节点是第一层） 叶子节点：没有子节点的节点 非终端节点：非叶子节点 度：子节点的个数称为度 数的度：含有最大子节点的个数即最大的度就是数的度
二、分类
1 一般树
任意一个节点的子节点的个数都不受控制
2 二叉树
任意一个节点的子节点个数最多两个，且子节点的位置不可更改
分类：
3 森林
n个互不相交的树的集合
三、树的存储
3.1二叉树的存储
连续存储【完全二叉树】 优点：查找某个节点的父节点和子节点（也包括判断有没有节点）很快 缺点：耗用内存空间很大
链式存储
3.2一般树的存储
双亲表示法 求父节点方便
孩子表示法 求子节点方便
双亲孩子表示法 求父节点和子节点都很方便
二叉树表示法 把一个普通树转换成二叉树来存储 具体转换方法： 设法保证任意一个节点的左指针域指向它的第一个孩子，右指针域指向它的兄弟 只要满足此条件，就可以把一个普通树转化为二叉树 一个普通树转化成的二叉树一定没有右子树
3.3森林的存储
将各个树的根节点看作一组兄弟节点，把森林转化成二叉树，再存储
四、操作
4.1遍历
先序遍历（先访问跟节点） 先访问根节点， 再先序访问左子树， 再先序访问右子树 中序遍历（中间访问根节点） 中序遍历左子树 再访问根节点 再中序遍历右子树 B-D-C-E-A-L-F-N-Q-M
B-D-C-A-M-Q-E-L-N
后序遍历（最后访问根节点） 中序遍历左子树 中序遍历右子树 再访问根节点 B-D-M-F-L-E-C-A
N-W-T-S-F-P-L-Q-M
4.2已知两种遍历序列求原始二叉树
通过先序和中序 或者 中序和后序，我们可以还原出原始的二叉树； 但是通过先序和后序是无法还原出原始的二叉树。
或者说：只有通过先序和中序，或者通过中序和后序，我们才可以唯一的确定一个二叉树
已知先序和中序求后序： 示例1： D-E-C-B-H-G-F-A
示例2： 先序：A-B-D-G-H-C-E-F-I 中序：G-D-H-B-A-E-C-I-F 求后序：G-H-D-B-E-I-F-C-A
已知后序和中序求先序： 后序最后出现的是根节点 示例1： 中序：B-D-C-E-A-F-H-G 后序：D-E-C-B-H-G-F-A 求先序：A-B-C-D-E-F-G-H
五、应用
树是数据库中数据组织的一种重要形式 操作系统子父进程关系本身就是一棵树 面向对象语言中类的继承关系本身就是一棵树 赫夫曼树
六、代码实现
#include<stdio.h>
#include<malloc.h>
struct BTNode
{
char data
;
struct BTNode
* pLchild
;
struct BTNode
* pRchild
;
};
struct BTNode
* CreateBTree(void);
void PreTraverseBTree(struct BTNode
* pT
);
void InTraverseBTree(struct BTNode
* pT
);
void PostTraverseBTree(struct BTNode
* pT
);
int main(void){
struct BTNode
* pT
=CreateBTree();
printf("先序遍历：\n");
PreTraverseBTree(pT
);
printf("中序遍历：\n");
InTraverseBTree(pT
);
printf("后序遍历：\n");
PostTraverseBTree(pT
);
return 0;
}
void PreTraverseBTree(struct BTNode
* pT
){
if(pT
!=NULL){
printf("%c\n",pT
->data
);
if(NULL!=pT
->pLchild
){
PreTraverseBTree(pT
->pLchild
);
}
if(NULL!=pT
->pRchild
){
PreTraverseBTree(pT
->pRchild
);
}
}
}
void InTraverseBTree(struct BTNode
* pT
){
if(pT
!=NULL){
if(NULL!=pT
->pLchild
){
InTraverseBTree(pT
->pLchild
);
}
printf("%c\n",pT
->data
);
if(NULL!=pT
->pRchild
){
InTraverseBTree(pT
->pRchild
);
}
}
}
void PostTraverseBTree(struct BTNode
* pT
){
if(pT
!=NULL){
if(NULL!=pT
->pLchild
){
PostTraverseBTree(pT
->pLchild
);
}
if(NULL!=pT
->pRchild
){
PostTraverseBTree(pT
->pRchild
);
}
}
printf("%c\n",pT
->data
);
}
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
->pRchild
=pB
->pLchild
=NULL;
pC
->pLchild
=pD
;
pC
->pRchild
=NULL;
pD
->pLchild
=NULL;
pD
->pRchild
=pE
;
pE
->pRchild
=pE
->pLchild
=NULL;
return pA
;
}
