这道题的大部分程序已经完成，题目中的二叉树是根据后序遍历和中序遍历序列建立的，主函数也已经给出，你只需要在适当的位置添加先序遍历二叉树的函数 PreOrder( ) 即可。 #include<stdio.h> #include<stdlib.h> typedef char DataType; typedef struct Node { DataType data; struct Node *lchild, *rchild; }BiTNode, *BinTree; void CreateBinTree_Post_In(BiTNode * &t, DataType post[], DataType in[], int s1, int t1, int s2, int t2) { int i; if (s1 <= t1) { t = (BiTNode*)malloc(sizeof(BiTNode)); t->data = post[t1]; t->lchild = NULL; t->rchild = NULL; for (i = s2; i <= t2; i++) if (in[i] == post[t1]) break; CreateBinTree_Post_In(t->rchild, post, in, s1 + i-s2, t1-1, i+1, t2); CreateBinTree_Post_In(t->lchild, post, in, s1, s1+i-s2-1, s2, i-1); } } /*你的代码段将放在这个位置*/ int main() { char *post, *in; int n; BiTNode *t; while (scanf("%d", &n) != EOF) { post = (char*)malloc(n * sizeof(char)); in = (char*)malloc(n * sizeof(char)); scanf("%s", post); scanf("%s", in);

void PreOrder(BinTree t) {
if (t != NULL) {
printf("%c ", t->data);
PreOrder(t->lchild);
PreOrder(t->rchild);
}
}

int main() {
char *post, *in;
int n;
BiTNode *t;
while (scanf("%d", &n) != EOF) {
post = (char*)malloc(n * sizeof(char));
in = (char*)malloc(n * sizeof(char));
scanf("%s", post);
scanf("%s", in);

CreateBinTree_Post_In(t, post, in, 0, n-1, 0, n-1);

printf("PreOrder: ");
PreOrder(t);
printf("\n");

free(post);
free(in);
}
return 0;
}

相关问题

一棵非空二叉树，若后序遍历与中序遍历的序列相同，则该二叉树所有结点均无左孩子。

这个说法是错误的。后序遍历与中序遍历序列相同并不意味着二叉树所有结点均无左孩子。举个例子，考虑以下二叉树：

    A
   / \
  B   C
     / \
    D   E

它的中序遍历为 `B A D C E`，后序遍历也为 `B D E C A`。可以发现，节点 C 就有左孩子 D。因此，原命题不成立。

若一棵二叉树后序遍历和中序遍历序列分别为： DHEBFIGCA和DBEHAFCIG,则该二叉树对应的先序遍历序列为_和层次遍历序列为_。

根据中序遍历和后序遍历序列，可以得到该二叉树的结构如下：

         C
        / \
       /   \
      /     \
     /       \
    /         \
   /           \
  /             \
 D               I
  \             / \
   E           /   \
    \         /     \
     F       A       G
      \     /
       H   B

其中，根据后序遍历序列，最后一个节点为根节点，即G；根据中序遍历序列，G的左边为其左子树的节点，右边为其右子树的节点，因此可以划分出左子树和右子树的中序遍历序列，分别为DBEHAFC和CIG。由于中序遍历中根节点在左子树和右子树的中序遍历序列中间，因此可以得到左右子树的后序遍历序列，分别为BEHDFA和IGHC。接下来可以分别对左右子树进行递归，重建整棵二叉树。

根据先序遍历的定义，先访问根节点，然后先序遍历左子树，最后先序遍历右子树。因此，该二叉树的先序遍历序列为CGDHEFABI，层次遍历序列为GCIDFBEAH。