网站 › 『编程语言讨论求助区』 › 为什么根据中后跟序列构造二叉树失败

d173220523 发表于 2020-8-13 13:47

为什么根据中后跟序列构造二叉树失败

本帖最后由 d173220523 于 2020-8-13 14:13 编辑

#include <iostream>
#define MaxSize 50 //定义栈中元素的最大个数
typedef struct BiTNode{
      char data; //数据域
      struct BiTNode *lchild, *rchild; //左、右孩子指针
}BiTNode,*BiTree;
BiTree PrelnCreat(char* in, char* pre, int n){
      if(n == 0)
                return NULL;
      BiTree p = new BiTNode;
      p->data = *pre;
      for(int i = 0;i < n; i++)
                if(in == *pre)
                        break;
                p->lchild = PrelnCreat(in, pre +1, i);
                p->rchild = PrelnCreat(in + i + 1, pre + i + 1, n - (i + 1));
                return p;
}
BiTree lnPostCreat(char* in, char* post, int n){
      if(n == 0)
                return NULL;
      BiTree p = new BiTNode;
      p->data = post;
      for(int i = 0;i < n; i++)
                if(in == post)
                        break;
                p->lchild = PrelnCreat(in, post, i);
                p->rchild = PrelnCreat(in + i + 1, post + i, n - (i + 1));
                return p;
}
void PostOrder(BiTree T){
      if(T){
                PostOrder(T->lchild);
                PostOrder(T->rchild);
                printf("%c",T->data);
      }
}
int main(){
      char* pre="GDAFEMHZ";
      char* in="ADEFGHMZ";
      char* post="AEFDHZMG";
      BiTree t=lnPostCreat(in,post,8);
      PostOrder(t);
      //printf("%d",treeDepth(t));
      printf("\n");
      return 0;
}

秩序的风达 发表于 2020-8-13 14:00

好像你计算根节点时的i变量是局部的？

查看完整版本: 为什么根据中后跟序列构造二叉树失败