1.树的原理
树（Tree）是n（n≥0）个节点的有限集合T，它满足两个条件 ：
????????1.有且仅有一个特定的称为根（Root）的节点；
????????2.其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树
表示方法 ：树形表示法、目录表示法。
????????一个节点的子树的个数称为该节点的度数，
????????一棵树的度数是指该树中节点的最大度数，
????????度数为零的节点称为树叶或终端节点，
????????度数不为零的节点称为分支节点，
????????除根节点外的分支节点称为内部节点。
- 若树中每个节点的各个子树的排列为从左到右，不能交换，即兄弟之间是有序的，则该树称为有序树。
- m（m≥0）棵互不相交的树的集合称为森林。
- 树去掉根节点就成为森林，森林加上一个新的根节点就成为树。
2.二叉树
定义
????????二叉树是n(n ≥ 0)个节点的有限集合；要么是空集(n＝0)，要么是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成，严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。
性质
性质1 二叉树第i层上的结点数目最多为2^(i-1),(i≥1)。
性质2 深度为k的二叉树至多有2^k-1个结点(k≥1)。
性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
顺序存储?
链式存储
typedef int data_t;
typedef struct node_t;
{
data_t data;
struct node_t *lchild ,*rchild ;
} bitree_t;
bitree_t *root;
二叉树由根节点指针决定。
3. 二叉树的遍历
????????遍历 ：沿某条搜索路径周游二叉树，对树中的每一个节点访问一次且仅访问一次。
????????二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。
由于二叉树的递归性质，遍历算法也是递归的。三种基本的遍历算法如下 ：
? ? ? ? 1.先访问树根，再访问左子树，最后访问右子树；（根左右）
? ? ? ? 2.先访问左子树，再访问树根，最后访问右子树；（左根右）
? ? ? ? 3.先访问左子树，再访问右子树，最后访问树根；（左右根）
?注：当遍历算法为左根右时，先对根节点A进行左根右判断，得到B，此时B有子树，那么把B当作根，继续左根右判断，发现没有左节点，根是B，故B入队，右是C，C有子树，那么把C当作根，继续左根右，D是左且没有子树，故D入队，根C入队，此时A的左侧遍历完成，根A入队，右为E，有子树，将E作为根，左没值，故E入队，右F有子树，来到左G，G有子树，来到左H，H没子树，H入队，根G入队，右K入队，F入队，中序序列：BDCAEHGKF
?4.二叉树遍历的实现
创建树
// 递归的方法
bitree * tree_create() {
data_t ch;
bitree *r; // 根节点
scanf("%c", &ch);
if (ch == '#') // 符号# 用来表示这里的节点是空
return NULL;
if ((r = (bitree *)malloc(sizeof(bitree))) == NULL) {
printf("malloc failed\n");
return NULL;
}
r->data = ch;
r->left = tree_create(); // 这里用 只有树根的树结构去理解
r->right = tree_create(); // r->left和r->right均为NULL
return r;
}这里使用了先序的方式来创建树，以上图为例，输入scanf 的序列应该是：
A B # C D # # # E # F G H # # K # # #
先序遍历
void preorder(bitree * r) { // 先序遍历
if (r == NULL) {
return;
}
// 这三行的递归 也体现出了对于树的每个内部节点，都会将其视为根，进行根左右的遍历
printf("%c", r->data);
preorder(r->left);
preorder(r->right);
}中序遍历
void inorder(bitree * r) { // 中序遍历
if (r == NULL) {
return;
}
inorder(r->left);
printf("%c", r->data);
inorder(r->right);
}后序遍历
void postorder(bitree * r) { // 后序遍历
if (r == NULL) {
return;
}
postorder(r->left);
postorder(r->right);
printf("%c", r->data);
}层次遍历
// 代码整体看下来，就是按照树的层数由一层到末层、从左到右依次遍历
void layerorder(bitree * r) { // 传入参数是树的根节点，不是整个树
linkqueue * lq; // 用于访问
if ((lq = queue_create()) == NULL)
return;
if (r == NULL)
return;
printf("%c", r->data);
enqueue(lq, r); // 树根入队
while (!queue_empty(lq)) {
r = dequeue(lq); //循环①树根出队 循环②：左孩子出队 循环③：右孩子出队 循环④：左孩子的左右孙子继续循环
if (r->left) {
printf("%c", r->left->data); // 这就相当于遍历到了
enqueue(lq, r->left);
}
if (r->right) {
printf("%c", r->right->data);
enqueue(lq, r->right);
}
}
puts("");
}