数据结构⼊门-树的遍历以及⼆叉树的创建
树定义：
1. 有且只有⼀个称为根的节点
2. 有若⼲个互不相交的⼦树，这些⼦树本⾝也是⼀个树
通俗的讲：
1. 树是有结点和边组成，
2. 每个结点只有⼀个⽗结点，但可以有多个⼦节点
3. 但有⼀个节点例外，该节点没有⽗结点，称为根节点
⼀、专业术语
结点、⽗结点、⼦结点、根结点
深度：从根节点到最底层结点的层数称为深度，根节点第⼀层
叶⼦结点：没有⼦结点的结点
⾮终端节点：实际上是⾮叶⼦结点
度：⼦结点的个数成为度
⼆、树的分类
⼀般树：任意⼀个结点的⼦结点的个数都不受限制
⼆叉树：任意⼀个结点的⼦结点个数最多是两个，且⼦结点的位置不可更改
⼆叉数分类：
1. ⼀般⼆叉数
2. 满⼆叉树：在不增加树层数的前提下，⽆法再多添加⼀个结点的⼆叉树
3. 完全⼆叉树：如果只是删除了满⼆叉树最底层最右边的连续若⼲个结点，这样形成的⼆叉树就是完全⼆叉树
森林：n个互不相交的树的集合
三、树的存储
⼆叉树存储
连续存储(完全⼆叉树)
优点：查某个结点的⽗结点和⼦结点(也包括判断有没有⼦结点)速度很快
缺点：耗⽤内存空间过⼤
链式存储
⼀般树存储
1. 双亲表⽰法：求⽗结点⽅便
2. 孩⼦表⽰法：求⼦结点⽅便
3. 双亲孩⼦表⽰法：求⽗结点和⼦结点都很⽅便
4. ⼆叉树表⽰法：把⼀个⼀般树转化成⼀个⼆叉树来存储，
具体转换⽅法：
设法保证任意⼀个结点的左指针域指向它的第⼀个孩⼦，右指针域指向它的兄弟，只要能满⾜此条件，就可以把⼀个⼀般树转化为⼆叉树
⼀个普通树转换成的⼆叉树⼀定没有右⼦树
森林的存储
先把森林转化为⼆叉树，再存储⼆叉树
四、树的遍历
先序遍历：根左右
先访问根结点，再先序访问左⼦树，再先序访问右⼦树
中序遍历：左根右
中序遍历左⼦树，再访问根结点，再中序遍历右⼦树
后续遍历：左右根
后续遍历左⼦树，后续遍历右⼦树，再访问根节点
五、已知两种遍历求原始⼆叉树
给定了⼆叉树的任何⼀种遍历序列，都⽆法唯⼀确定相应的⼆叉树，但是如果知道了⼆叉树的中序遍历序列和任意的另⼀种遍历序列，就可以唯⼀地确定⼆叉树
已知先序和中序求后序
先序：ABCDEFGH
中序：BDCEAFHG
求后序：这个⾃⼰画个图体会⼀下就可以了，⾮常简单，这⾥简单记录⼀下
1. ⾸先根据先序确定根，上⾯的A就是根
2. 中序确定左右，A左边就是左树(BDCE)，A右边就是右树(FHG)
3. 再根据先序，A左下⾯就是B，然后根据中序，B左边没有，右边是DCE
4. 再根据先序，B右下是C，根据中序，c左下边是D，右下边是E，所以整个左树就确定了
5. 右树，根据先序，A右下是F，然后根据中序，F的左下没有，右下是HG，
6. 根据先序，F右下为G，然后根据中序，H在G的左边，所以G的左下边是H
再来⼀个例⼦，和上⾯的思路是⼀样的，这⾥就不详细的写了
先序：ABDGHCEFI
中序：GDHBAECIF
已知中序和后序求先序
中序：BDCEAFHG
后序：DECBHGFA
这个和上⾯的思路是⼀样的，只不过是反过来，后序根，中序左右
树简单应⽤
树是数据库中数据组织⼀种重要形式
操作系统⼦⽗进程的关系本⾝就是⼀棵树
⾯向对象语⾔中类的继承关系
哈夫曼树
六、⼆叉树的创建
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
char data;
struct Node * lchild;
struct Node * rchild;
}BTNode;
/*
⼆叉树建⽴
*/
void BuildBT(BTNode ** tree)
{
char ch;
scanf("%c" , &ch); // 输⼊数据
if(ch == '#')  // 如果这个节点的数据是#说明这个结点为空
*tree = NULL;
else
{
*tree = (BTNode*)malloc(sizeof(BTNode));//申请⼀个结点的内存  (*tree)->data = ch; // 将数据写⼊到结点⾥⾯
BuildBT(&(*tree)->lchild); // 递归建⽴左⼦树
BuildBT(&(*tree)->rchild); // 递归建⽴右⼦树
}
}
/*
⼆叉树销毁
*/
void DestroyBT(BTNode *tree) // 传⼊根结点
{
if(tree != NULL)
{
DestroyBT(tree->lchild);
DestroyBT(tree->rchild);
free(tree);  // 释放内存空间
}
}
/*
⼆叉树的先序遍历
*/
void Preorder(BTNode * node)
{
if(node == NULL)
return;
else
{
printf("%c ",node->data );
Preorder(node->lchild);
Preorder(node->rchild);
}
}
/*
⼆叉树的中序遍历
*/
void Inorder(BTNode * node)
{
if(node == NULL)
return;
else
{
Inorder(node->lchild);
printf("%c ",node->data );
Inorder(node->rchild);
}
}
/*
⼆叉树的后序遍历
*/
void Postorder(BTNode * node)
{
if(node == NULL)
return;
else
{
Postorder(node->lchild);
Postorder(node->rchild);
printf("%c ",node->data );
}
}
/*
⼆叉树的⾼度
树的⾼度 = max(左⼦树⾼度，右⼦树⾼度) +1
*/
int getHeight(BTNode *node)
{
int Height = 0;
if (node == NULL)
return 0;
else
{
int L_height = getHeight(node->lchild);
int R_height = getHeight(node->rchild);
Height = L_height >= R_height ? L_height +1 : R_height +1; }
return Height;
}
int main(int argc, char const *argv[])
{
BTNode * BTree; // 定义⼀个⼆叉树
printf("请输⼊⼀颗⼆叉树先序序列以#表⽰空结点:");
BuildBT(&BTree);
printf("先序序列：");
Preorder(BTree);
printf("\n中序序列：");
Inorder(BTree);
printf("\n后序序列：");
Postorder(BTree);
二叉树的遍历及应用实验报告printf("\n树的⾼度为：%d" , getHeight(BTree));
return 0;
}
// ABC##DE##F##G##