这里主要介绍一下：二叉树的建树、先序遍历、中序遍历、后序遍历；主要运用了递归的方法，简化了问题；
题目：
深度遍历二叉树
Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte
Total Submit:1332 Accepted:389
Total Submit:1332 Accepted:389
Description
二叉树(binary tree)是非常重要的树形数据结构，它是结点的有限集合，该集合或者为空集，或者是由一个根和两个互不相交的、称为该根的左子树和右子树的二叉树组成。
一般意义上，遍历（traverse）一棵二叉树意味着对该二叉树中的每个结点访问且仅访问一次。
（1）若二叉树不为空，先序遍历是指先访问该树根结点，再访问先序遍历左子树，最后先序遍历右子树。
（2）若二叉树不为空，中序遍历是指先中序遍历左子树，再访问该树根结点，最后中序遍历右子树。
（3）若二叉树不为空，后序遍历是指先后序遍历左子树，再后序遍历右子树，最后访问该树根结点。
图1018-1给出一棵二叉树，先序遍历序列为A B D C E F，中序遍历序列为B D A E C F，后序遍历序列为D B E F C A，样例输出给出了输出格式。
图1018-1
编程建立下图1018-2描述的二叉树，给出先序、中序和后序遍历序列。
图1018-2
Input
无需显式输入任何数据
Output
共三行，依次输出先序、中序和后序遍历序列。
Sample Input
Sample Output
PreOrder: A B D C E F
InOrder: B D A E C F
PostOrder: D B E F C A
代码：
#include <iostream>
using namespace std;
class Node
{
private:
char element;
Node *lchild, *rchild;
public:
Node(char e) { element = e; lchild = rchild = NULL; }
Node(char e, Node *l, Node *r) { element = e; lchild = l; rchild = r; }
friend class Btree;
};
class Btree
{
private:
Node *root;
public:
Btree() { root = NULL; }
~Btree() {}
void makeTree(char e, Btree l, Btree r);
void preOrder(Node *node);
void inOrder(Node *node);
void postOrder(Node *node);
Node *reRoot();
};
int main()
{
Btree x, y, z, a, b, c, d;
y.makeTree('K', c, d);
z.makeTree('C', y, d);
y.makeTree('G', c, z);
z.makeTree('J', c, d);
x.makeTree('F', z, y);
y.makeTree('H', c, d);
z.makeTree('E', y, x);
y.makeTree('B', c, d);
x.makeTree('A', c, y);
y.makeTree('D', z, x);
cout << "PreOrder:";
y.preOrder(y.reRoot());
cout << endl;
cout << "InOrder:";
y.inOrder(y.reRoot());
cout << endl;
cout << "PostOrder:";
y.postOrder(y.reRoot());
cout << endl;
return 0;
}
void Btree::makeTree(char e, Btree l, Btree r)
{
root = new Node(e, l.root, r.root);
l.root = r.root = NULL;
}
Node* Btree::reRoot()
{
return root;
}
void Btree::preOrder(Node *node)
{
if(node)
{
cout << " " << node->element;
preOrder(node->lchild);
preOrder(node->rchild);
}
}
void Btree::inOrder(Node *node)
{
if(node)
{
inOrder(node->lchild);
cout << " " << node->element;
inOrder(node->rchild);
}
}
void Btree::postOrder(Node *node)
{
if(node)
{
postOrder(node->lchild);
postOrder(node->rchild);
cout << " " << node->element;
}
}