写在前面：
二叉树是比较简单的一种数据结构，理解并熟练掌握其相关算法对于复杂数据结构的学习大有裨益
一.二叉树的创建
[不喜欢理论的点我跳过>>]
所谓的创建二叉树，其实就是让计算机去存储这个特殊的数据结构（特殊在哪里？特殊在它是我们自定义的）
首先，计算机内部存储都是线性的，而我们的树形结构是一种层级的，计算机显然无法理解，计算机能够接受的原始数据类型并不能满足我们的需求
所以，只好自定义一种数据结构来表示层级关系
实际上是要定义结构 + 操作，结构是为操作服务的，举个例子，我们要模拟买票的过程，现有的数据结构无法满足我们的需求（不要提数组...），我们需要的操作可能是:
1.获取站在买票队伍最前面的人
2.把买好票的人踢出队伍
3.第一个人买完票后，他后面的所有人都要“自觉”地向前移动
明确了这三个操作，再根据操作来定义结构，最后我们得到了队列（数组/链表 + 对应的函数）
二叉树也是这样，计算机看到的只是结构 + 操作，结构是Node集合（二叉链表），操作是创建、遍历、查找等等函数
结点：
struct bt
{
char data;
struct bt *left;
struct bt *right;
};
结点就是一个桶，两只手（桶里装数据，两只手伸出去抓左右两个孩子）
操作：
//createBT();
//printBT();
//deleteNode(Node node);
//...
-------上面是对二叉树的理解，下面是创建二叉树具体实现-------
二叉树的创建过程其实就是遍历过程（此处指递归方式），我们知道二叉树的任何一种遍历方式都可以把树形结构线性化（简单的说就是一组遍历结果可以唯一的表示一颗二叉树），因此可以根据遍历结果来还原一颗二叉树
先序遍历递归建树的具体思路：
1.读入当前根结点的数据
2.如果是空格，则将当前根置为空，否则申请一个新结点，存入数据
3.用当前根结点的左指针和右指针进行递归调用，创建左右子树
语言描述可能不太好懂，代码如下：
struct bt
{
char data;
struct bt *left;
struct bt *right;
};
void createBT(struct bt ** root)
{
char c;
c=getchar();
if(c == ' ')*root=NULL;//若为空格则置空
else
{
*root=(struct bt *)malloc(sizeof(struct bt));//申请新结点
(*root)->data=c;//存入数据
createBT(&((*root)->left));//建立当前结点的左子树
createBT(&((*root)->right));//建立当前结点的右子树
}
}
例如，如果我们要建立一个二叉树a(b, c)，只要输入它的先序遍历结果ab××c××即可（×表示空格），其余两种建树方式于此类似，不再详述，至于非递归的建树方法参见下面的非递归遍历，非常相似
二.遍历
遍历在实现方式上有递归与非递归两种方式，所谓的非递归其实是由递归转化而来的（手动维护一个栈），开销（内存/时间）上可能非递归的更好一些，毕竟操作系统的栈中维护的信息更多，现场的保存与恢复开销都要更大一些
在遍历顺序上有3种方式：
1.先序遍历（根-左-右）
2.中序遍历（左-根-右）
3.后序遍历（左-右-根）
举个例子，二叉树a(b, c(d, e))的三种遍历结果分别是：
1.abcde
2.badce
3.bdeca
-------下面看看后序遍历的递归与非递归实现，其余的与之类似-------
后序遍历递归：
void postOrder(struct bt * root)
{
if(root == NULL)return;
else
{
postOrder(root->left);
postOrder(root->right);
putchar(root->data);
}
}
后序遍历非递归：
void postOrder(struct st* root)
{
struct st* stack[100];//声明结点栈
int top=-1;//栈顶索引
struct bt* p=root;//当前结点（present）
struct bt* q=NULL;//上一次处理的结点
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;//遍历左子树
if(top!=-1)
{
p=stack[top];
if(p->right==NULL||p->right==q)//无右孩子，或右孩子已经遍历过
{
putchar(p->data);//输出根结点
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;//遍历右子树
}
}
}
为了描述地更清晰，上面直接实现了栈的操作，当然，更规范的做法是将栈作为一个独立的数据结构封装起来，在我们的函数中调用栈提供的操作函数来进行相关操作
三.输出叶结点
检索特定结点的一系列操作都是建立在遍历的基础上的，输出叶结点就是一个例子，叶结点满足的条件是左右孩子都为空，我们只要在遍历中添加这样的判断条件就可以了
//此处采用先序遍历
void printLeaves(struct bt* root)
{
if(root == NULL)return;
else
{
if(root->left == NULL&&root->right == NULL)putchar(root->data);
else
{
printLeaves(root->left);
printLeaves(root->right);
}
}
}
于此类似的操作有，输出二叉树中满