C++对树进行后序遍历的代码

#include <stdio.h>
#include <string.h>
struct Node{
    Node *lchild;// 左儿子指针
    Node *rchild;// 右儿子指针
    char c;//结点字符信息
}Tree[50];// 静态内存分配数组
  
int loc;// 静态数组中已经分配的结点个数
Node *creat(){//申请一个结点空间，返回指向其的指针
    Tree[loc].lchild=Tree[loc].rchild=NULL;//初始化左右儿子为空
    return &Tree[loc++];
}
char str1[30],str2[30];// 保存前序和中序遍历字符串
  
//修改打印输出的位置就可以进行相应的前序和中序遍历了
void postOrder(Node *T){
    if(T->lchild!=NULL){
        postOrder(T->lchild);
    }
    if(T->rchild!=NULL){
        postOrder(T->rchild);
    }
    printf("%c",T->c);// 遍历该结点，输出字符信息
}
Node *build(int s1,int e1,int s2,int e2){
    Node* ret=creat();
    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;
}
  
  
int main(){
    freopen("in.txt", "r", stdin);
    while(scanf("%s",str1)!=EOF){
        scanf("%s",str2);//输入
        loc=0;// 初始化静态内存空间中已经使用结点个数为0
        int L1=strlen(str1);
        int L2=strlen(str2);
        Node *T=build(0,L1-1,0,L2-1);
        postOrder(T);//后序遍历
        printf("n");
    }
    return 0;
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。