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

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

推荐答案 2017-10-18

内容比较多，好好看看
单链表实现二叉树结构综合案例（使用类模板的方法）
--------------------二叉树节点类
#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;
/*
           10(0)
     9(1)        8(2)
7(3)   6(4)   5(5)    4(6)
  */
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;
}

追问

每个<之前都加过;号了，度不行啊

温馨提示：答案为网友推荐，仅供参考

当前网址：http://66.wendadaohang.com/zd/Upixis92vn999xxix99.html

相似回答

生成并遍历二叉树?答：TreeNode* root = construct(s, i); // 生成该二叉树 cout << "其前序遍历序列为：";preOrder(root);cout << endl;cout << "其中序遍历序列为：";inOrder(root);cout << endl;cout << "其后序遍历序列为：";postOrder(root);cout << endl;return 0;} 编译通过，输出如下：符合示例...

急!~编写一个C++语言程序,对二叉树实现操作答：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；4. 将二叉树每个结点的左右子树交换位置。【数据描述】//- - - - - - 二叉树的二叉链表存储表示 - - - ...

编写一个C++程序,先生成再层次遍历一个二叉树答：const int MaxLength=10;//结点个数不超过10个 typedef struct BTNode{ ElemType data;struct BTNode *lchild,*rchild;}BTNode,* BiTree;void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树 // if(T) return;char ch;ch=getchar(); //不能用cin来输...

二叉树的建立和遍历(C++)答：//---中序遍历二叉树--- void zhongbianli(bitnode *T){ if(T){ zhongbianli(T->lchild);visit(T);zhongbianli(T->rchild);} } //---先序遍历二叉树--- void xianbianli(bitnode *T){ if(T){ visit(T);xianbianli(T->lchild);xianbianli(T->rchild);} } //---...

C++数据结构 二叉树的遍历 问题见补充答：一个一个节点画，后序从后往前看，（1）K为根（2）中序中找到K，以K为界划分2侧为左右子树，K左边的DCBGEAHFIJ为K的左子树，K没有右子树（3）看后序，K左边是J，J是K左子树的根（4）中序中找到J，同（2）（5）看后序，J左边是I，I是J左子树的根（6）中序中找到I，同（2...

运用C++如何使用二叉链表存储二叉树,遍历输出叶子节点路径,递归输出...答：构造的二叉树结构如下：运行结果如下：代码如下：include <iostream>#include <vector>using namespace std;typedef struct tnode //定义树节点结构{int val;tnode* left;tnode* right;tnode(int x=0):val(x),left(NULL),right(NULL){}//默认构造函数}TreeNode,*pTreeNode;void getPath(Tree...

大家正在搜

用c语言实现二叉树的中序遍历用栈实现二叉树的非递归遍历二叉树后序遍历用栈实现二叉树后序遍历的非递归实现二叉树用栈的方式遍历使用栈遍历二叉树非递归不用栈遍历二叉树二叉树用二叉链表方式存储树的遍历栈的使用