写在前面：
?
二叉树是比较简单的一种数据结构，理解并熟练掌握其相关算法对于复杂数据结构的学习大有裨益
?
一.二叉树的创建
?
[不喜欢理论的点我跳过>>]
?
所谓的创建二叉树，其实就是让计算机去存储这个特殊的数据结构（特殊在哪里？特殊在它是我们自定义的）
?
首先，计算机内部存储都是线性的，而我们的树形结构是一种层级的，计算机显然无法理解，计算机能够接受的原始数据类型并不能满足我们的需求
?
所以，只好自定义一种数据结构来表示层级关系
?
实际上是要定义结构 + 操作，结构是为操作服务的，举个例子，我们要模拟买票的过程，现有的数据结构无法满足我们的需求（不要提数组...），我们需要的操作可能是:
?
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);
? ? ? ? }
? ? }
}
于此类似的操作有，输出二叉树中满