一:根据扩展二叉树的前序遍历序列建立该二叉树
Binode* Creat(Binode* bt) { char ch; cin>>ch; if(ch=='#') bt=NULL; else { bt=new Binode; bt->data=ch; bt->lchild=Creat(bt->lchild); bt->rchild=Creat(bt->rchild); } return bt; }
二:根据二叉树的前序遍历和中序遍历序列建立该二叉树
这是一个递归的过程,其基本思想是:先根据前序序列的第一个元素建立根节点,然后在中序序列中找到该元素,确定了根节点的左右子树的中序序列,再在前序序列中确定左右子树的前序序列,最后由左子树的前序和中序建立左子树,由右子树的前序和中序建立右子树
int pos(char ch,char *pin,int i2)//查找根节点在中序序列中的位置 { for(int i=i2;i<k;i++) if(*(pin+i)==ch) return i; }
BiNode* Creat(BiNode *root,int i1,int i2,int k) { //i1为前序的起始下标,i2为中序的起始下标,k为序列的长度,pre[]为前序序列,pin为中序序列 if(k<=0) root=NULL; else { root=new BiNode; root->data=pre[i1]; int m=Search(pre[i1],pin,i2);//查找根节点在中序序列中的位置 int leftlen=m-i2; int rightlen=k-(leftlen+1); root->lchild=Creat(root->lchild,i1+1,i2,leftlen); root->rchild=Creat(root->rchild,i1+leftlen+1,m+1,rightlen); } return root; }