用c++来实现二叉树的遍历。

输入一棵树的各个节点信息，输出各种遍历的序列（先根、后根、中根、层次）。输入其中两种遍历序列，试图构造出该树，并输出其他两种遍历序列。

内容比较多，好好看看
单链表实现二叉树结构综合案例（使用类模板的方法）
--------------------二叉树节点类
#ifndef TREE_NODE
#define TREE_NODE
#include <iostream>
using namespace std;
template<typename T>
class Tree_Node
{
friend ostream& operator<< <T>(ostream& out,const Tree_Node& TN);//特例 这里不是：Tree_Node<T>&……模板参数移到前面去了
public:
    Tree_Node();
    Tree_Node<T>* searchNode(int _index); //判断当前节点，当前节点的孩子节点是否是要寻找的节点
    void DeleteNode();
    void Preorder();
    void Inorder();
    void Postorder();
    int m_iIndex; //节点的唯一索引值 
    T   m_TData;  //节点的数据类型在运行的时候指定
 //凡是要用到当前类的声明对象的都要加上模板参数
    Tree_Node<T>* m_pLchild; //左孩子指针
    Tree_Node<T>* m_pRchild; //右孩子指针
    Tree_Node<T>* m_pParent; //父指针
};
template<typename T>
ostream& operator<<(ostream& out,const Tree_Node<T>& TN) //模板参数又移到形参变量的地方了
{
    out<<TN.m_iIndex<<":"<<TN.m_TData<<endl;
    return out;
}
template<typename T>
Tree_Node<T>::Tree_Node() //实现构造函数，模板参数在类名中已经体现出来了
{
    this->m_iIndex =0;
    this->m_TData =NULL;
    this->m_pLchild =NULL;
    this->m_pRchild =NULL;
    this->m_pParent =NULL;
}
template<typename T>
Tree_Node<T>* Tree_Node<T>::searchNode(int _index) //根据节点的唯一索引值，查找节点，并返回节点的指针
{
    if (this->m_iIndex == _index) // 这个this指的是根节点这个对象
    {
        return this;
    }
    Tree_Node<T>* find_node =NULL;  //保存左子树和右子树查找到的结果
    if (this->m_pLchild !=NULL)
    {
        if (this->m_pLchild->m_iIndex == _index)
        {
            return this->m_pLchild;
        }
        else //当前节点的左孩子不是目标节点，再查找左孩子的后代，并返回结果，递归实现的关键
        {
            find_node = this->m_pLchild->searchNode(_index);
            //如果在左子树上找到了，则返回找到的节点,如果没有找到，再去右子树查找，在右子树查找的结果不管有没有都返回
            if (find_node != NULL)
            {
                return find_node;
            }
        }

    }
    if (this->m_pRchild !=NULL)
    {
        if (this->m_pRchild->m_iIndex == _index)
        {
            return this->m_pRchild;
        }else
        {
            find_node =this->m_pRchild->searchNode(_index);
            return find_node;  
        }
    }
    return NULL; // 要执行到这一步，就说明该节点既没有左孩子和右孩子，本身也不是待查找节点，就返回空指针了
}
template<typename T>
void Tree_Node<T>::DeleteNode()  // 删除节点，递归删除它的左孩子节点和右孩子节点
{
    if (this->m_pLchild !=NULL) //如果当前节点的左孩子节点不为空，则递归删除该左孩子节点和左孩子所有后代节点
    {
        this->m_pLchild->DeleteNode();
    }
    if (this->m_pRchild != NULL)//如果当前节点的右孩子节点不为空，则递归删除该子节点的所有后代
    {
        this->m_pRchild->DeleteNode();
    }
    //如果当前节点的父指针不为空，把这个指向关系置空
    if (this->m_pParent != NULL)
    {
        //判断当前节点是父节点的左孩子还是右孩子，以便置空父节点的左孩子指针还是右孩子指针
        if (this->m_pParent->m_pLchild == this)
        {
            this->m_pParent->m_pLchild =NULL; //如果当前节点是父节点的左孩子，则置空父节点的
        }
        if (this->m_pParent->m_pRchild == this)
        {
            this->m_pParent->m_pRchild =NULL;
        }
    }
    delete this; 
       //这里没有显示的定义析构函数的原因是，删除节点的时候，该节点的所有指针对象都已经是空值了，没有释放内存空间的需要
      // 自身节点也就是一个数据域，使用系统默认的析构函数就能完成这一点
       //最后再删除本身这个节点，递归执行到这一步，就是叶子节点做的操作，这一层递归结束后，它的父节点就变成了叶子节点，递归很合理
}
template<typename T>
void Tree_Node<T>::Preorder()  // 二叉树的前序遍历
{
    //前序遍历先输出本身，再输出左子树，后输出右子树,递归的使用本身
    cout<<this->m_iIndex<<"："<<this->m_TData<<endl;
    if (this->m_pLchild !=NULL) //如果当前的左节点不为空，则递归输出左节点以及左节点的后代
    {
        this->m_pLchild->Preorder();
    }
    if (this->m_pRchild !=NULL) 
    {
        this->m_pRchild->Preorder();
    }
}
template<typename T>
void Tree_Node<T>::Inorder() //二叉树的中序遍历
{

    //中序遍历先输出左子树，再输出根，后输出右子树
    if (this->m_pLchild !=NULL) //如果当前的左节点不为空，则递归输出左节点以及左节点的后代
    {
        this->m_pLchild->Inorder();
    }
    cout<<this->m_iIndex<<"："<<this->m_TData<<endl;
    if (this->m_pRchild !=NULL)
    {
        this->m_pRchild->Inorder();
    }
}
template<typename T>
void Tree_Node<T>::Postorder() //二叉树的后序遍历
{
    if (this->m_pLchild !=NULL) //如果当前的左节点不为空，则递归输出左节点以及左节点的后代
    {
        this->m_pLchild->Postorder();
    }
    if (this->m_pRchild !=NULL)
    {
        this->m_pRchild->Postorder();
    }
    cout<<this->m_iIndex<<"："<<this->m_TData<<endl; // 最后输出根节点的信息
}
#endif
------------------------------二叉树类的实现，带有模板参数的类，声明和实现最好放在一个文件中，不容易出错
#ifndef TREE_h
#define TREE_h
#include "Tree_Node.h"
template<typename T>
class Tree
{
public:
    Tree();
    Tree_Node<T>* searchNode(int _index); //从根节点递归的方法向下搜索树，知道找到节点的索引等于参数的索引值
    bool AddNode(int _index, int _direction,Tree_Node<T>* pNode); //添加节点
    bool DeleteNode(int _index); //删除节点，不仅仅要删除自己，还要删除自己所有的后代节点，父节点的指向，用递归来实现
    ~Tree(); //析构函数
    //树的前序遍历，后序遍历和中序遍历都是递归的方法，递归的调用节点中的方法，从这里就看到面向对象编程的好处了，比C语言的方法简单多了
    void Preorder();
    void Inorder();
    void Postorder();
private:
    Tree_Node<T>* m_pTree;
};
template<typename T>
Tree<T>::Tree()
{
    this->m_pTree = new Tree_Node<T>();
    //第一个节点为根节点，索引默认为0，未指定它的孩子节点，所以孩子节点指针为空，父节点不存在，指向默认为空
    //这个地方出现了错误，写代码的时候语法没有检测出来，任何地方使用带有模板参数的函数都要加上参数列表
    //错误的写法：this->m_pTree = new Tree_Node();
}
template<typename T>
Tree_Node<T>* Tree<T>::searchNode(int _index)
{
    return this->m_pTree->searchNode(_index);
}
template<typename T>
bool Tree<T>::AddNode(int _index, int _direction,Tree_Node<T>* pNode)
{
    Tree_Node<T>* direction_node = this->searchNode(_index); 
                          //插入节点是在指定的节点下插入，如果这个指定的节点不存在，插入操作就失败了
    if (direction_node ==NULL)
    {
        return false;
    }
    //不能传进来的临时节点pNode做为树中新增的结点，因为是对指针的操作，外部操作pNode会同步影响到插入树中节点的值，应该重新申请一块内存空间
    Tree_Node<T>* new_node =new Tree_Node<T>();
    if (NULL == new_node)
    {
        return false;
    }
    new_node->m_iIndex = pNode->m_iIndex;
    new_node->m_TData= pNode->m_TData;
    //新增节点的父节点
    new_node->m_pParent = direction_node;
    if (_direction ==0) //如果插入的是左孩子，指针指向如下
    {
        direction_node->m_pLchild = new_node;
        // 程序这里默认，目标节点没有孩子节点，二叉树的构造是从上到下一步一步构造的
       //实际上有了删除节点的方法，即使该节点有过孩子节点，只需删除该孩子节点，也不是很麻烦
    }
    if (_direction ==1) //如果是右孩子，则当前节点指向目标节点
    {
        direction_node->m_pRchild = new_node;
    }
    return true;
}
template<typename T>
bool Tree<T>::DeleteNode(int _index) // 删除节点，这一步应该放在
{
    Tree_Node<T>* direction_node = this->searchNode(_index);
    if (NULL == direction_node) //如果目标节点为空，那么删除操作也就没有意义了
    {
        return false;
    }
    //如果不为空则调用节点对象的删除方法
    direction_node->DeleteNode();
    return true;
}
template<typename T>
Tree<T>::~Tree()
{
    //树的析构函数执行起来就很简单了，直接对根节点调用deleteNode函数就可以了
    this->m_pTree->DeleteNode();
    // 或者 DeleteNode(0)
}
template<typename T>
void Tree<T>::Preorder()
{
    //前序遍历
    this->m_pTree->Preorder();
}
template<typename T>
void Tree<T>::Inorder()
{
    //中序遍历
    this->m_pTree->Inorder();
}
template<typename T>
void Tree<T>::Postorder()
{
    //后续遍历
    this->m_pTree->Postorder();
}
#endif
--------------------测试主文件
#include <iostream>
#include <stdlib.h>
#include "Tree.h"
using namespace std;

int main()
{
    Tree<int>* tree =new Tree<int>();
    //生成一个树的，默认有一个根节点，根节点不放数据，索引默认为0
    Tree_Node<int>* node1 = new Tree_Node<int>();
    node1->m_iIndex =1;
    node1->m_TData  =9;
    Tree_Node<int>* node2 = new Tree_Node<int>();
    node2->m_iIndex =2;
    node2->m_TData  =8;
    //在根节点下插入1和2号子节点
    tree->AddNode(0,0,node1);
    tree->AddNode(0,1,node2);
    Tree_Node<int>* node3 = new Tree_Node<int>();
    node3->m_iIndex =3;
    node3->m_TData  =7;
    Tree_Node<int>* node4 = new Tree_Node<int>();
    node4->m_iIndex =4;
    node4->m_TData  =6;
    //在1号节点下插入3和4号子节点
    tree->AddNode(1,0,node3);
    tree->AddNode(1,1,node4);
    Tree_Node<int>* node5 = new Tree_Node<int>();
    node5->m_iIndex =5;
    node5->m_TData  =5;
    Tree_Node<int>* node6 = new Tree_Node<int>();
    node6->m_iIndex =6;
    node6->m_TData  =4;
    //在2号节点下插入5和6号子节点
    tree->AddNode(2,0,node5);
    tree->AddNode(2,1,node6);
    //前序遍历：0 1 3 4 2 5 6
    tree->Preorder();
    cout<<"---------------------"<<endl;
    //中序遍历：3 1 4 0 5 2 6
    tree->Inorder();
    cout<<"---------------------"<<endl;
    //后序遍历：3 4 1 5 2 6 0
    tree->Postorder();
    cout<<"---------------------"<<endl;
    cout<<*(tree->searchNode(3))<<endl; //返回3：7 模板类的输出运算符友元函数形式重载成功，特例，一定要记住，会用
    cout<<"---------------------"<<endl;

   // 删除操作的实现
    tree->DeleteNode(2);
    tree->Preorder();
    system("pause");
    return 0;
}