根据二叉树的中序序列+前序序列 可以唯一确定一个二叉树——数据结构课程（分治，递归）
定理：
仅根据先序、中序、后序序列中的其中一个无法唯一确定一个二叉树。
根据二叉树的中序序列+前序序列 或者中序序列+后序序列 可以唯一确定一个二叉树，这里给出了构造方法。
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; }
遍历
支付宝扫一扫
微信扫一扫
最新评论