NOJ数据结构018——建立二叉树的二叉链表

爱被打了一巴掌 2023-01-16 09:53 234阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]

在本题中，给出中序遍历结果以及先序遍历结果或后序遍历才可以构建唯一二叉树，若给出先序和后序，则不唯一。

本题思路即从左到右按顺序读取pre字符串，并在mid字符串中找到相应位置pos\_m，在pos\_m左边的字符串递归建立左子树，右边递归建立右子树。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct Node
    {
        
        char data;
        struct Node* LChild;
        struct Node* RChild;
    }BiNode, *BiTree;
    
    int PreFindMid(char *pre, char *mid, int pos_p, int pos_le, int pos_ri);
    //找到先序字符对应的中序字符
    BiTree CreateTree(char *pre, char *mid, int *pos_p, int pos_le, int pos_ri);
    //建立二叉树
    void PostOrder(BiTree T);
    //后序输出
    
    int main()
    {
        
        int len_pre;
        char pre[100], mid[100];
        scanf("%s%s", pre, mid);
        len_pre = strlen(pre);
        BiTree T;
        int pos_p = 0;
        T = CreateTree(pre, mid, &pos_p, 0, len_pre-1);
        PostOrder(T);
        return 0;
    }
    
    int PreFindMid(char *pre, char *mid, int pos_p, int pos_le, int pos_ri)
    {
          //找到先序字符对应的中序字符
        for (int i = pos_le; i <= pos_ri; i++) {
        
            if (pre[pos_p] == mid[i]) {
        
                return i;
            }
        }
        return 0;
    }
    
    BiTree CreateTree(char *pre, char *mid, int *pos_p, int pos_le, int pos_ri)
    {
          //建立二叉树
        BiTree tmp;
        tmp = (BiTree) malloc (sizeof(BiNode));
        tmp->data = pre[*pos_p];
        tmp->LChild = NULL;
        tmp->RChild = NULL;
        (*pos_p)++;
        int pos_m;
        pos_m = PreFindMid(pre, mid, *pos_p-1, pos_le, pos_ri);
        //找到pre字符串的读取字符在mid字符串的位置
        if (pos_m > pos_le) {
        
            tmp->LChild = CreateTree(pre, mid, pos_p, pos_le, pos_m-1);
        }
        if (pos_m < pos_ri) {
        
            tmp->RChild = CreateTree(pre, mid, pos_p, pos_m+1, pos_ri);
        }
        return tmp;
    }
    
    void PostOrder(BiTree T)
    {
          //后序输出
        if (T == NULL) {
        
            return;
        }
        PostOrder(T->LChild);
        PostOrder(T->RChild);
        printf("%c", T->data);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/a35e846d17ce462ebf854d8712fbaa01.png