二叉樹編程題

⑴ 跪求編程大神~用c語言編個程序

下面是我做過的題目，演算法思想樹上已經說的很詳細了，我就給代碼哈。

題目描述
輸入二叉樹的先序遍歷序列和中序遍歷序列，輸出該二叉樹的後序遍歷序列。
輸入
第一行輸入二叉樹的先序遍歷序列；
第二行輸入二叉樹的中序遍歷序列。
輸出
輸出該二叉樹的後序遍歷序列。
示例輸入
ABDCEF
BDAECF
示例輸出
DBEFCA

#include<iostream>
#include<cstring>
#defineMAX50+3
usingnamespacestd;
typedefcharElem_Type;
typedefstructBiTree
{
Elem_Typedata;//數據
structBiTree*Lchild;//左孩子
structBiTree*Rchild;//右孩子
}BiTree;//要查找的元素查找的地方數組的長度
intSearch_Num(Elem_Typenum,Elem_Type*array,intlen)
{
for(inti=0;i<len;i++)
if(array[i]==num)
returni;
//return-1;//沒有找到
}//前序遍歷中序遍歷中序數組長度
BiTree*Resume_BiTree(Elem_Type*front,Elem_Type*center,intlen)
{
if(len<=0)
returnNULL;
BiTree*temp=newBiTree;
temp->data=*front;
intindex=Search_Num(*front,center,len);
temp->Lchild=Resume_BiTree(front+1,center,index);
temp->Rchild=Resume_BiTree(front+index+1,center+index+1,len-index-1);
returntemp;
}
voidPostOrderTraverse(BiTree*root)//後序遍歷
{
if(root!=NULL)
{
PostOrderTraverse(root->Lchild);
PostOrderTraverse(root->Rchild);
cout<<root->data;
}
}
intmain(void)
{
Elem_Type*preorder=newElem_Type[MAX];//前序
Elem_Type*inorder=newElem_Type[MAX];//中序
cin>>preorder;cin>>inorder;
BiTree*root=Resume_BiTree(preorder,inorder,strlen(inorder));
PostOrderTraverse(root);
cout<<endl;
return0;
}
/**************************************
Problemid:
Username:
Result:Accepted
TakeMemory:444K
TakeTime:0MS
SubmitTime:2014-05-1622:52:07
**************************************/

⑵ 解決編程問題（1）

由兩種遍歷所得的順序能唯一確定一棵二叉樹，比如給定了一顆二叉樹的先序序列是:ABDECFG,中序序列是：DBEAFCG，由先序序列可以確定該二叉樹根為A,因為先序遍歷的順序是從根到左子樹再到右子樹，然後從中序序列中，可以得知DBE在A的左子樹，而FCG在A的右子樹，由於在先序序列中B緊跟在A後，所以B肯定是A左子樹的樹根，再看中序序列里，A的左子樹是DBE，由中序序列遍歷的順序為：左子樹，雙親，右子樹，可知D為B的左子樹，E為B的右子樹，同樣可以分析樹根A的右子樹，先序序列中ABDE已經將樹根和左子樹遍歷完成，所以剩下的CFG是右子樹的先序遍歷序列，可知C為右子樹的樹根，F為C的左子樹，G為C的右子樹，所以該二叉樹按層序遍歷的順序應該是ABCDEFG先根遍歷就是先訪問根節點 再依次訪問左右子樹中根遍歷就是先訪問左子樹 再依次訪問根節點和右子樹後根遍歷就是先訪問左右子樹 在訪問根節點

⑶ 快快編程第43題加分二叉樹怎麼做

dp:

由於它是中序遍歷，所以結果二叉樹的任意一棵子樹都是中序遍歷中的一段區間

設d[i][j]表示i到j的區間所組成的二叉樹的最高加分

若子樹的樹根為k（i<=k<=j），則左子樹為區間i~k-1右子樹為k+1~j

加分為d[i][k-1]*d[k+1][j]+a[k]

所以狀態轉移方程為d[i][j]=max(d[i][k-1]*d[k+1][j]+a[k] | i<=k<=j)