二叉树编程题

⑴ 跪求编程大神~用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)