本文主要向大家介绍了C/C++知识点之C++实现利用（前序和中序生成二叉树）以及（二叉树的镜像），通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

#include<iostream>
#include<string.h>
#include<stack>
using namespace std;
typedef struct BTree
{
    int val;
    struct BTree *left,*right;
}BTree;
/*二叉树的类，包含着操作二叉树的各种方法*/
class Tree
{
    public:
    BTree *create_node(int level,string pos);
    void PreOrder(BTree *t);  //先序遍历
    void InOrder(BTree *t);  //中序遍历
    void PostOrder(BTree *t);  //后序遍历
    void NonRecursivePreOrder(BTree*t); //非递归前序遍历
    void NonRecursiveInOrder(BTree*t);  //非递归中序遍历
    void NonRecursivePostOrder(BTree*t);//非递归后序遍历
    BTree* PreOrder_and_INorder_RemakeTree(int *startPreorder,int *endPreder,int *startInorder,int*endInorder);
    BTree *root;
};

/*用先序遍历的方法递归构造一课二叉树*/
BTree* Tree::create_node(int level,string pos)
{
    int data;
    BTree *node = new BTree;
    int a[]={100,99,98,97,0,0,20,0,0,10,0,0,5,1,0,0,2,0,0};
    static int t=0;
    cout<<"please enter data:level "<<level<<" "<<pos<<"--->值为:"<<a[t]<<endl;
       data=a[t++];
    if(data == 0)
    {
        return NULL;
    }
    node->val= data;
    node->left = create_node(level+1,"left");
    node->right= create_node(level+1,"right");
    return node;
}

void Tree::PreOrder(BTree *t)
{
    if(t)
    {
        cout<<t->val<<" ";;
        PreOrder(t->left);
        PreOrder(t->right);
    }
}

void Tree::InOrder(BTree *t)
{
    if(t)
    {
        InOrder(t->left);
        cout<<t->val<<" ";;
        InOrder(t->right);
    }
}

void Tree::PostOrder(BTree *t)
{
    if(t)
    {
        PostOrder(t->left);
        PostOrder(t->right);
        cout<<t->val<<" ";
    }
}
void Tree::NonRecursivePreOrder(BTree*t)
{
  if(t==NULL)
   return;
  stack<BTree*>s;
  BTree *p;
  p=t;
  while(p||!s.empty())
  {
   if(p)
   {
       cout<<p->val<<" ";
       s.push(p);
       p=p->left;
   }
   else{
       p=s.top();
       p=p->right;
       s.pop();
   }
  }
}
void Tree::NonRecursiveInOrder(BTree*t)
{
    if(t==NULL)
        return;
    stack<BTree*>s;
    BTree*p;
    p=t;
    while(p||!s.empty())
    {
        if(p)
        {
            s.push(p);
            p=p->left;
        }
        else
        {
            p=s.top();
            cout<<p->val<<" ";
            p=p->right;
            s.pop();
        }
    }
}
void Tree::NonRecursivePostOrder(BTree*t)
{
  if(t==NULL)
      return;
  stack<BTree*>s;
  BTree*p=t;
  BTree*r;
  while(p||!s.empty())
  {
      if(p)
      {
          s.push(p);
          p=p->left;
      }
      else
      {
          p=s.top();
          if(p->right&&p->right!=r)
          {
              p=p->right;
              s.push(p);
              p=p->left;
          }
          else
          {
              cout<<p->val<<" ";
              r=p;
              s.pop();
              p=NULL;
          }
      }
  }

}
BTree* Tree::PreOrder_and_INorder_RemakeTree(int *startPreorder,int *endPreorder,int *startInorder,int*endInorder)
{
  int rootValue=startPreorder[0];
  BTree*root=new BTree;
   root->val=rootValue;
   root->left=NULL;
   root->right=NULL;
//　　　　　  在中序遍历中找根节点的值
   int*rootInorder=startInorder;
   while(rootInorder<=endInorder&&*rootInorder!=rootValue)
       rootInorder++;
   int leftLength=rootInorder-startInorder;
   int *leftPreorderEnd=startPreorder+leftLength;
   if(leftLength>0)
   {
       root->left=PreOrder_and_INorder_RemakeTree(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1);
   }
   if(leftLength<endPreorder-startPreorder)
   {
       root->right=PreOrder_and_INorder_RemakeTree(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
   }
return root;
}
BTree* binary_tree_mirror(BTree*head)
{
    BTree*newHead=head;
    if(head==NULL)
        return NULL;
    if(head->left!=NULL&&head->right!=NULL)
    {
        BTree *p;
        p=head->left;
        head->left=head->right;
        head->right=p;
    }
    binary_tree_mirror(head->left);
    binary_tree_mirror(head->right);
    return newHead;
}


int main()
{
    Tree tree;
    tree.root = tree.create_node(1,"root");
    cout<<"Pre"<<endl;
    tree.PreOrder(tree.root);
    cout<<endl;
    cout<<"非递归前序遍历"<<endl;
    tree.NonRecursivePreOrder(tree.root);
    cout<<endl;
    cout<<"In"<<endl;
    tree.InOrder(tree.root);
    cout<<endl;
    cout<<"非递归中序遍历"<<endl;
    tree.NonRecursiveInOrder(tree.root);
    cout<<endl;
    cout<<"Post"<<endl;
    tree.PostOrder(tree.root);
    cout<<endl;
    cout<<"非递归后序遍历"<<endl;
    tree.NonRecursivePostOrder(tree.root);
    int preNum[]={100,99,98,97,20,10,5,1,2};
    int InNum[]={97,98,20,99,10,100,1,5,2};
    BTree*root2;
    int *endPreorder=&preNum[8];
    int *endInorder=&InNum[8];
    root2=tree.PreOrder_and_INorder_RemakeTree(preNum,endPreorder,InNum,endInorder);
    cout<<endl;
    cout<<"用后序遍历测试用前序和中序生成的二叉树："<<endl;
     tree.PostOrder(root2);
     cout<<"二叉树的镜像为:"<<endl;
     BTree *newTree;
     newTree=binary_tree_mirror(root2);
     cout<<"镜像二叉树的后序遍历为:"<<endl;
     tree.PostOrder(newTree);
     return 0;
}
二叉树的图：
　　　　　　　　　　                     (100)
                             (99)              (5)
                        (98)     (10)       (1)     (2)
                     (97)   (20)

复制代码
 结果：

复制代码
please enter data:level 1 root--->值为:100
please enter data:level 2 left--->值为:99
please enter data:level 3 left--->值为:98
please enter data:level 4 left--->值为:97
please enter data:level 5 left--->值为:0
please enter data:level 5 right--->值为:0
please enter data:level 4 right--->值为:20
please enter data:level 5 left--->值为:0
please enter data:level 5 right--->值为:0
please enter data:level 3 right--->值为:10
please enter data:level 4 left--->值为:0
please enter data:level 4 right--->值为:0
please enter data:level 2 right--->值为:5
please enter data:level 3 left--->值为:1
please enter data:level 4 left--->值为:0
please enter data:level 4 right--->值为:0
please enter data:level 3 right--->值为:2
please enter data:level 4 left--->值为:0
please enter data:level 4 right--->值为:0
Pre
100 99 98 97 20 10 5 1 2 
非递归前序遍历
100 99 98 97 20 10 5 1 2 
In
97 98 20 99 10 100 1 5 2 
非递归中序遍历
97 98 20 99 10 100 1 5 2 
Post
97 20 98 10 99 1 2 5 100 
非递归后序遍历
97 20 98 10 99 1 2 5 100 
用后序遍历测试用前序和中序生成的二叉树：
97 20 98 10 99 1 2 5 100
镜像二叉树的后序遍历为:
2 1 5 10 20 97 98 99 100     

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！