根据二叉树的中序序列+前序序列 可以唯一确定一个二叉树——数据结构课程（分治，递归）

定理：

　　仅根据先序、中序、后序序列中的其中一个无法唯一确定一个二叉树。 

　　根据二叉树的中序序列+前序序列 或者中序序列+后序序列 可以唯一确定一个二叉树，这里给出了构造方法。

 1 #include<cstdio>
 2 #include<string.h>
 3 #include<malloc.h>
 4 using namespace std;
 5 #define MaxSize 100
 6 typedef  char ElemType;
 7 typedef struct node
 8 {
 9     ElemType data;
10     struct node* lchild;
11     struct node* rchild; 
12 }BTNode; 
13 
14 void CreateBTree(BTNode * &b, char * str)//传入地址b，将其作为根 
15 {
16     BTNode *St[MaxSize],*p=NULL; //建立指针型数组？
17     int top=-1,k,j=0;//top为栈顶指针，k为标记，j为字符串指针 
18     
19     b=NULL;//初始化树为空
20     char ch=str[j];//j指向字符串的指针
21     while(ch!='')//扫描字符串
22     {
23         switch(ch)//判断当前字符 
24         {
25             case '(':St[++top]=p;k=1;break;//接下来的节点为左子树 
26             case ')':--top;break;
27             case ',':k=2;break;
28             default:p=(BTNode *)malloc(sizeof(BTNode));//当前字符为节点 
29                     p->data=ch;p->lchild=p->rchild=NULL;
30                     if(b==NULL) b=p;//第一个节点当做根节点
31                     else
32                     {
33                         switch(k)
34                         {
35                             case 1:St[top]->lchild=p;break;
36                             case 2:St[top]->rchild=p;break;
37                             
38                         }
39                     } 
40                         
41         }
42         ch=str[++j];
43     } 
44 }
45 
46 void DestroyBTree(BTNode * &b)//销毁当前二叉树
47 {
48     if(b!=NULL)
49     {
50         DestroyBTree(b->lchild);
51         DestroyBTree(b->rchild);
52         free(b);//递归释放节点空间 
53     }
54 } 
55 
56 void DispBTree(BTNode *b)
57 {
58     if(b!=NULL)
59     {
60         printf("%c",b->data);
61         if (b->lchild!=NULL || b->rchild!=NULL)
62         {    printf("(");                        
63             DispBTree(b->lchild);                //递归处理左子树
64             if (b->rchild!=NULL) printf(",");    //有右孩子结点时才输出','
65             DispBTree(b->rchild);                //递归处理右子树
66             printf(")");                        
67         }
68     }
69 }
二叉树的基本操作

具体思路为：（分治，递归）

　　1根据先序或者后序序列先找出当前树的根节点

　　2然后从中序序列中找到根节点所在的位置

　　3中序序列中，根节点之前的属于左子树，根节点之后的属于右子树

　　4对左子树和右子树所在的序列分别进行1~3操作。

 1 #include "二叉树基本操作.cpp"   //调用自己的函数库
 2 #define MaxWidth 40
 3 /*函数功能： 
 4     根据前序和中序字符串 创建二叉树， 
 5     输入当前子树前序中序字符串的首地址
 6     以及当前子树的节点数
 7 
 8 */ 
 9 BTNode *CreateBT1(char *pre ,char *in,int n)
10 {
11     BTNode *b;
12     char *p;//当前节点指针
13     if(n<=0) return NULL;
14     b=(BTNode *)malloc(sizeof(BTNode));        //创建二叉树结点*b
15     b->data=*pre;//先序序列的第一个节点即为根节点
16     for(p=in;p<in+n;p++) //在中序序列中寻找根节点的位置
17         if(*p==*pre) break;
18     int k=p-in;//左子树的节点数
19     b->lchild=CreateBT1(pre+1,in,k);
20     b->rchild=CreateBT1(pre+k+1,p+1,n-k-1);
21     
22     return b;
23 }
24 BTNode *CreateBT2(char *post,char *in,int n)
25 {    BTNode *b;
26     char r,*p;
27     int k;
28     if (n<=0) return NULL;
29     r=*(post+n-1);                        //根结点值
30     b=(BTNode *)malloc(sizeof(BTNode));        //创建二叉树结点*b
31     b->data=r;
32     for (p=in;p<in+n;p++)                    //在in中查找根结点
33         if (*p==r)    break;
34     k=p-in;                                //k为根结点在in中的下标
35     b->lchild=CreateBT2(post,in,k);            //递归构造左子树
36     b->rchild=CreateBT2(post+k,p+1,n-k-1);    //递归构造右子树
37     return b;
38 }
39 int main()
40 {
41     BTNode *b;
42     ElemType pre[]="ABDEHJKLMNCFGI";
43     ElemType in[]="DBJHLKMNEAFCGI";
44     ElemType post[]="DJLNMKHEBFIGCA";
45     int n=14;
46     b=CreateBT1(pre,in,n);
47         printf("先序序列:%s
",pre);
48     printf("中序序列:%s
",in);
49     printf("构造一棵二叉树b:
");
50     printf("  括号表示法:");DispBTree(b);printf("
");
51     b=CreateBT2(post,in,n);
52     printf("构造一棵二叉树b:
");
53     printf(" 括号表示法:");DispBTree(b);printf("
");
54         DestroyBTree(b);
55     return 0;
56 }
根据（前序+中序序列）还原二叉树
#include<stdio.h>
#include<malloc.h>
#include<cstring>
#include<iostream>
using namespace std;

typedef struct Bnode /*  定义二叉树存储结构*/  
{
    char data;
    struct Bnode *lchild,*rchild;```
} BtNode,*BTree;

BtNode *Q[100]; //队列Q放树结点地址

BtNode *CreatBTree()//输入为完全二叉树的前提下，构建二叉树 
{
    char ch ,str[20];
    int front=1,rear=0;//定义队列的头尾指针 
    int i, n;
    BtNode *root = NULL, *s;

    gets(str);
    n=strlen(str);
    cout<<n<<endl;
    for(i=1; i<n; i++)  //结束标志
    {
        s=NULL;
        if (str[i]!='#')  //当前字符非空，建立节点加入队列 
        {
            s=(BtNode *)malloc(sizeof(BtNode)); //生成新结点
            s->data=str[i];
            s->lchild=NULL;
            s->rchild=NULL;
        }
        Q[++rear]=s;  //结点入队
        if (rear==1) root=s; //记录根结点
        else
        {
            if (s && Q[front])
            {
                if (rear%2==0) Q[front]->lchild=s; //左孩子入队
                else Q[front]->rchild=s;  //右孩子入队
            }
            if (rear%2==1)  front++; //新结点是双亲的右孩子，则双亲结点出队
        }
    }
    return root;
}

void preorder(BTree T)//先序遍历
{
    if(T)
    {
        cout<<T->data<<"  ";
        preorder(T->lchild);
        preorder(T->rchild);
    }
}

void inorder(BTree T)//中序遍历
{
    if(T)
    {
        inorder(T->lchild);
        cout<<T->data<<"  ";
        inorder(T->rchild);
    }
}

void posorder(BTree T)//后序遍历
{
    if(T)
    {         
        posorder(T->lchild);
        posorder(T->rchild);
        cout<<T->data<<"  ";
    }
}

int main()
{
    BtNode * mytree;
    mytree=CreatBTree();/*创建二叉树*/

    cout<<"二叉树的先序遍历结果："<<endl;
    preorder(mytree);//先序遍历二叉树
    cout<<endl;
    cout<<"二叉树的中序遍历结果："<<endl;
    inorder(mytree);//中序遍历二叉树
    cout<<endl;
    cout<<"二叉树的后序遍历结果："<<endl;
    posorder(mytree);//后序遍历二叉树
    cout<<endl;

    return 0;
}
遍历
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/CLGYPYJ/p/15503691.html