我们知道,中序遍历和前序或者后序能够唯一确定一颗二叉树,因此,给定前序遍历以及中序遍历序列能够确定建立这颗二叉树,然后后序遍历便能够得到相应的序列
代码如下(内含二叉树的建立,求二叉树的高度)
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> typedef struct Node{ Node *lchild; Node *rchild; char c; }Node,*Tree;//静态内存分配数组 //int loc; char str1[30]; char str2[30]; Node *createNode(){ // Tree[loc].lchild = Tree[loc].rchild=NULL; // return &Tree[loc++]; Tree node = (Tree)malloc(sizeof(Node)); if (node) { node->lchild=node->rchild=nullptr; return node; }else{ printf("无法分配节点"); exit(0); } } //后序遍历算法 void postOrder(Node *T){ if (T->lchild!=NULL) { postOrder(T->lchild); } if (T->rchild!=NULL) { postOrder(T->rchild); } printf("%c",T->c); } //先序遍历 void preOrder(Tree T){ printf("%c",T->c); if (T->lchild!=NULL) { preOrder(T->lchild); } if (T->rchild!=NULL) { preOrder(T->rchild); } } //中序遍历 void midOrder(Tree T){ if (T->lchild!=NULL) { midOrder(T->lchild); } printf("%c",T->c); if (T->rchild!=NULL) { midOrder(T->rchild); } } Node * build(int s1,int e1,int s2,int e2){ //根据前序遍历序列str1和中序遍历序列str2构建树,并返回树的根节点, Node * ret = createNode();//构建根节点, ret->c = str1[s1]; int rootIdx; for (int i = s2; i<=e2;i++ ) { if (str2[i]==str1[s1]) { rootIdx = i;//在中序遍历序列中找到根节点的下标; break; } } if(rootIdx!=s2){//说明左子树不为空 ret->lchild = build(s1+1, s1+(rootIdx-s2), s2, rootIdx-1); } if (rootIdx!=e2) {//说明右子树不为空 ret->rchild=build(s1+(rootIdx-s2)+1, e1, rootIdx+1, e2); } return ret; } //建立一颗二叉树,前序 Node *buildTree(){ //输入字符建立二叉树,遇到#便设置这个节点为空 Node *root =(Tree)malloc(sizeof(Node)); char a; scanf("%c",&a); if (a=='#') { root = nullptr; }else{ root->c = a; root->lchild = buildTree(); root->rchild = buildTree(); } return root; } //求树的高度 int high_Tree(Tree T){ if (T==nullptr) { return 0; }else{ int lh = high_Tree(T->lchild); int rh = high_Tree(T->rchild); return lh>rh?lh+1:rh+1; } } int main() { while(scanf("%s",str1)!=EOF){ scanf("%s",str2); int L1 = strlen(str1); int L2 = strlen(str2); Node * T = build(0, L1-1, 0, L2-1); postOrder(T); printf("%d ",high_Tree(T)); printf(" "); } return 0; }