第.34證明：由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。證明：采納遞歸法證明。當n=1時，前序序列和中序序列均只有一個元素，且一樣，即為樹的根，由此惟一確定了一棵二叉樹。假設n≤m-1時命題均成立，那么證明n=m時亦成立。假設前序序列為a1，a2，...，am，中序序列為b1，b2，...，bm。因為前序序列由前序遍歷二叉樹所得，那么a1即為根結點的元素，又中序序列由中序遍歷二叉樹所得，那么在中序序列中必能找到和a1值一樣的元素，設為bj，由此可以得到{b1，...，bj-1}為左子樹的中序序列，{bj+1，bm}為右子樹的中序序列。假設j=1，即b1為根，此時二叉樹的左子樹為空，{a2，...，am}為右子樹的前序序列，{b2，...，m}為右子樹的中序序列。右子樹上的結點數為m-1，由此，這二個序列惟一確定了右子樹，就惟一確定了二叉樹。假設j=m，即bm為根，此時二叉樹的右子樹為空，那么子序列{a2，...，am}和{b1，...，bm-1}一確定左子樹。假設2≤j≤m-1，那么子序列{a2，...，aj}和{b1，...，bjá1}惟一確定了左子樹，子序列{aj+1，...，am}和{bj+1，...，bm}惟一確定了右子樹。由此，證明白惟一的根及其左,右子樹只能構成一棵確定的二叉樹。5.35一棵二叉樹的前序序列和中序序列分別存在于兩個一維數組中，試編寫算法建立該二叉樹的二叉鏈表。解：此題的算法如下：設前序序列和中序序列分別存放在兩個一維數組pre(1，n)和ind(1，n)中，按前序序列pre(i，j)和中序序列ind(u，v)構造二叉樹，其根結點指針為s。btree*voidbintree(i，j，u，v)inti，j，u，v;{intk，l;btree*head，*s;head=NULL;/*根指針初始化，head為空樹*/if(j>=i)head=(btree*)malloc(sizeof(btree));/*建立根結點*/head->data=pre[i];k=u;while(ind[k]!=pre[i])k++;/*在中序序列中查找根結點*/l=i+k-u;/*l為左子樹中最右下結點在前序序列中的位置*/if(k==u)head->left=NULL;elses=bintree(i+1，l，u，k-1);/*構造左子樹*/head->left=s;if(k==v)head->right=NULL;elses=bintree(l+1，j，k+1，v);/*構造右子樹*/head->right=s;return(head);第五章上機內容：5.1,建立一棵二叉排序樹并中序遍歷。(依據題目完善程序)#include“stdio.h〞#include“malloc.h〞structnode{chardata；structnode*lchild,*rchild；}bnode；typedefstructnode*blink；blinkadd(blinkbt,charch)if(bt==NULL)bt=nalloc(sizeof(bnode))；bt->data=ch；bt->lchild=bt->rchild=NULL；elseif(ch<bt->data) bt->lchild=add(bt->lchid,ch)； else bt->rchild=add(bt->rchild,ch)；returnbt；voidinorder(blinkbt)if(bt){inorder(bt->lc)；printf〔“%c〞,bt->data〕；inorder(bt->rc)；main()blinkroot=NULL；inti,n；charx；scanf〔“%c〞,&n)；for(i=1；i<=n；i++)x=getchar()；root=add(root,x)；inorder(root)；printf〔“\n〞〕；5.2,由先綴表示式建立二叉樹的二叉鏈表構造，求該表達式對應的后綴,中綴表達式。解：#defineNULL0typedefstructtreechardata;structtree*lc,*rc;}JD;JD*creat(JD*bt)chark;scanf("%c",&k);if(k==’\0’)bt=NULL;elsebt=(JD*)malloc(sizeof(JD));bt->data=k;bt->lc=creat(bt->lc);bt->rc=creat(bt->rc);return(bt);voidinorder(JD*bt){if(bt!=NULL){inorder(bt->lc);printf("%c",bt->data);inorder(bt->rc);voidpostorder(JD*bt){if(bt!=NULL){postorder(bt->lc);postorder(bt->rc);printf("%c",bt->data);main()JD*bt,*p;p=creat(bt);printf("\ninorder:\n");inorder(p);printf("\npostorder:\n");postorder(p);getch();5.3,編寫程序，實現按層次遍歷二叉樹。解：voidleverorder(JD*bt)JD*p,*queue[N];inti=0,j=0;for(i=0;i<N;i++)queue[i]=NULL;i=0;if(bt!=NULL)queue[i++]=bt;while(bt!=NULL&&queue[j]!=NULL)if(bt->lc!=NULL)queue[i++]=bt->lc;if(bt->rc!=NULL)queue[i++]=bt->rc;printf("%3d",queue[j++]->data);bt=queue[j];5.4,建立由合法的表達式字符串確定的只含二元操作符的非空表達式樹，其存儲構造為二叉鏈表，用二叉樹的遍歷算法求該中綴表達式對應的后綴,前綴表達式。解：#defineNULL0typedefstructtreechardata;structtree*lc,*rc;}JD;JD*creat(JD*bt)chark;scanf("%d",&k);if(k==0)bt=NULL;elsebt=(JD*)malloc(sizeof(JD));bt->data=k;bt->lc=creat(bt->lc);bt->rc=creat(bt->rc);return(bt);voidpreorder(JD*bt)if(bt!=NULL)printf("%cz",bt->data);preorder(bt->lc);preorder(bt->rc);voidpostorder(JD*bt){if(bt!=NULL){postorder(bt->lc);