根据二叉树的前序序列和中序序列构造二叉树,具体算法怎么写

Question

本帖最后由 huoyingfans 于 2010-06-14 12:03:38 编辑

Answer 1

http://blog.csdn.net/lazy_p/archive/2010/01/31/5275260.aspx
请多指教，写的不好，呵呵！

Answer 2

这个问题应该发到数据结构与算法区。
A是根结点，从中序序列找到A，把它划分为左右两棵子树。
B是左子树根结点，从中序序列的左子树中找到B，然后划分为两棵子树。
如此递归下去。

Answer 3

    1楼的代码有问题啊，getPostOrder("ABCDEFG", "CBEDAFG");
System.out.println(postOrderReverse.reverse()); 输出为CEDBGFABADC  不对啊！    如何根据先序序列和后序序列生成二叉树，然后打印后序序列？？

Answer 4

#include <iostream>
#include <queue>using namespace std;struct BiNode
{
    char data;
    BiNode *lchild, *rchild;
};
typedef BiNode *BiTree;int CreateBiTree(BiTree &T, const char *s1, const char *s2, int len)
{
    if (len<=0)
   {
    T = NULL;
    return 1;
   }
   else
   {
    T = new BiNode;
    T->data = *s1;
    int i;
    for ( i=0; i<len; i++) if (s2[i]==*s1) break;
    CreateBiTree(T->lchild, s1+1, s2, i);
    CreateBiTree(T->rchild, s1+i+1, s2+i+1, len-(i+1));
    }
    return 1;
}int DestroyBiTree(BiTree &T)
{
   if (T==NULL) return 1;
   DestroyBiTree(T->lchild);
   DestroyBiTree(T->rchild);
   delete T;
   T = NULL;
   return 1;
}int ATraverse(BiTree &T)
{
    if (T==NULL) return 1;
    ATraverse(T->lchild);
    ATraverse(T->rchild);
    cout<<T->data;
    return 1;
}int LevelTraverse(BiTree &T)
{
    if (T==NULL) return 1;
    queue<BiNode *> Q;
    Q.push(T);
    while (!Q.empty())
   {
      BiNode *p = Q.front(); Q.pop();
      cout<<p->data;
      if (p->lchild!=NULL) Q.push(p->lchild);
      if (p->rchild!=NULL) Q.push(p->rchild);
    }
    return 1;
}main()
{
   char a[2000],b[2000];
   while(cin>>a>>b)
   {
      BiTree T;
      int count=0;
      int n;
      for(n=0;a[n]!='\0';n++); 
      CreateBiTree(T,a,b,n);
      ATraverse(T);
      cout<<" ";
      LevelTraverse(T); 
      cout<<endl; 
      DestroyBiTree(T);  
   }    
}

Answer 5

   对不起啊，我的描述不够准确，以下是详细描述
/** 内部树节点类 */
private static class TreeNode {
Object element;// 结点的信息 TreeNode left;// 结点的左孩子 TreeNode right;// 结点的右孩子 public TreeNode(Object o) {
element = o;
}
}   String preorder="ABCDEFG";//前序遍历序列 
   String inorder = "CBEDAFG";//中序遍历序列   public void createBinaryTree(String preorder,String inorder);//根据前序和中序生成二叉树
   public void postorder(TreeNode root);//后序遍历生成的二叉树

Answer 6

我的程序输出来的结果是:CEDBGFA
有问题吗？你这个答案是因为你没钱把前面我的测试数据给注释掉的原因，每次获得的时候必须要初始化postOrderReverse ，不然前面的答案会被累加的，呵呵！