数据结构二叉树看图看图

Question

用c语言
帮我注释详细一点 谢谢 看图 asdfghjzkahdkxbsldbxlsvsoxbd

Answer 1

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

const int maxn = 30;
char postOrder[maxn] = { 0 };
char inOrder[maxn] = { 0 };

struct node {
    int data;
    node* lchild;
    node* rchild;
};

// 根据后序序列和中序序列还原一棵二叉树
node* create(int postL, int postR, int inL, int inR) {
    if (postL > postR) return nullptr;

    node* root = new node;
    root->data = postOrder[postR];

    int k; 
    for (k = inL; k <= inR; ++k) {
        if (inOrder[k] == postOrder[postR]) {
            break; // 在中序区间中找到了根节点的位置
        }
    }
    int numLeft = k - inL;    // 偏移量
    
    // 注意此处对左子树区间和右子树区间的划分，根据关键的偏移量来划分的结果
    root->lchild = create(postL, postL + numLeft - 1, inL, k - 1);
    root->rchild = create(postL + numLeft, postR - 1, k + 1, inR);

    return root;
}

// 层序遍历
void LayerOrder(node* root) {
    queue<node*> q;
    q.push(root);
    bool isFirstNode = true;
    while (!q.empty()) {
        node* top = q.front();
        q.pop();

        if (isFirstNode) {
            printf("%c", top->data);
            isFirstNode = false;
        }
        else {
            printf("%c", top->data);
        }

        if (top->lchild != nullptr) q.push(top->lchild);
        if (top->rchild != nullptr) q.push(top->rchild);
    }
}

int main() {
    scanf("%s", inOrder);
    scanf("%s", postOrder);
    LayerOrder(create(0, strlen(inOrder) - 1, 0, strlen(inOrder) - 1));
    return 0;
}