C++先序和中序确定二叉树

朱雀 2022-05-24 10:37 179阅读 0赞

思考：如何才能确定一棵树？  
结论：    通过中序遍历和先序遍历可以确定一个树  
                通过中序遍历和后续遍历可以确定一个树  
                通过先序遍历和后序遍历确定不了一个树。  
单独先序遍历：能求解根，但不能求解左子树什么时候结束、右子树什么时候开始。

根据先序和中序结果画树

算法  
1、通过先序遍历找到根结点A，再通过A在中序遍历的位置找出左子树，右子树  
2、在A的左子树中，找左子树的根结点（在先序中找），转步骤1  
3、在A的右子树中，找右子树的根结点（在先序中找），转步骤1

根据如下遍历结果创建二叉树：

![Center][]

先序遍历结果：ABDHKECFIGJ

中序遍历结果：HKDBEAIFCGJ

代码：

#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=NULL;
            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);   //这里要用“%c”,因为就输出一个字符，  不能用“%s”, 它是输出字符串
       
    }
    //先序遍历
    void preOrder(Tree T){
        printf("%c",T->c);   //这里要用“%c”,因为就输出一个字符，  不能用“%s”, 它是输出字符串
        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);   //这里要用“%c”,因为就输出一个字符，  不能用“%s”, 它是输出字符串
        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 = NULL;
        }else{
            root->c = a;
            root->lchild = buildTree();
            root->rchild = buildTree();
        }
        return root;
    }
    //求树的高度
    int high_Tree(Tree T){
        if (T==NULL) {
            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\n",high_Tree(T));
            printf("\n");
        }
        
    
        return 0;
    }

源代码二：

#include <iostream>  
    #include <cstdio>  
    #include <cstdlib>  
    #include <cstring>  
    using namespace std;;  
      
    const int N=31;  
      
    
      
    typedef struct BitNode  
    {  
        char value;  
        BitNode *lchild,*rchild;    
    }BitNode,*BiTree;  
    
    /*   *&代表什么？  //https://zhidao.baidu.com/question/2266744263935050308.html
    
      这是C++的语法写法，&在形参中表示“引用”实参，
    LNode * &lst ;  中LNode * 是个整体，表示变量类型是LNode类指针， &lst中的&表明引用实参，即代表实参的一个别名。   
    标准C是不支持这种写法的。
    
    追问
    
    &不是取地址符吗？ 引用参数是什么意思
    
    追答
    
    &在变量定义区，表示引用，要注意它的用法，
    &在变量操作区，表示取地址符，如：
    
    int x=10, *p=&x ;  //这里&作用在x上， 是取地址符
    int &x  ;   //引用是C++引入的一个新特性，你要学的不是C++,则上述代码你是搞不懂的。 这里的&就表示引用。 一般这种形式会在形参中出现。
    
    LNode * &lst ;  中LNode * 是个整体，表示变量类型是LNode类指针， &lst中的&表明引用实参，即代表实参的一个别名。 操作引用变量就相当于操作实参变量
    
    
    
     */
    
    void CreatTree(BitNode* &root,char *pre,int l1,int r1,char *in,int l2,int r2)  
    {  
        if(l1<=r1&&l2<=r2)  
        {  
            int key=pre[l1];  
            int midIndex=-1;  
            for(int i=l2;i<=r2;i++)  
            {  
                if(in[i]==key)  
                {  
                    midIndex=i;  
                    break;  
                }  
            }  
            root=(BitNode *)malloc(sizeof(BitNode));  
            root->value=key;  
            root->lchild=NULL;  
            root->rchild=NULL;  
            int llen=midIndex-l2;  
            CreatTree(root->lchild, pre, l1+1, l1+llen, in, l2, midIndex-1);  
            CreatTree(root->rchild, pre, l1+llen+1, r1, in, midIndex+1, r2);  
        }  
    }  
      
    void postOrderTraverse(BitNode *&root)  
    {  
        if(root->lchild)  
            postOrderTraverse(root->lchild);  
        if(root->rchild)  
            postOrderTraverse(root->rchild);  
        printf("%c",root->value);  
    }  
      
    int main()  
    {  
        char pre[N],in[N];  
        while(scanf("%s",pre)!=EOF)  
        {  
            scanf("%s",in);  
            int len1=strlen(pre);  
            int len2=strlen(in);  
            BitNode *root=NULL;  
            CreatTree(root,pre,0,len1-1,in,0,len2-1);  
            postOrderTraverse(root);  
            printf("\n");  
        }  
        return 0;  
    }

[Center]: /images/20220524/14b8f470a6844a1690c91e7a69caa55f.png