C语言实现先序后序构造正则二叉树

首先，我们需要了解一下正则二叉树的定义。正则二叉树是一种二叉树，每个节点的度数要么为0（叶子节点），要么为2（非叶子节点）。通过先序遍历和后序遍历序列可以唯一地构造出一棵正则二叉树。

现在我们来看一下如何使用C语言来实现先序和后序构造正则二叉树。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    char data;
    struct Node* left;
    struct Node* right;
} Node;

// 根据先序序列和后序序列构造正则二叉树
Node* constructTree(char* preorder, char* postorder, int preStart, int preEnd, int postStart, int postEnd) {
    if (preStart > preEnd || postStart > postEnd) {
        return NULL;
    }

    // 创建根节点
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = preorder[preStart];
    root->left = NULL;
    root->right = NULL;

    if (preStart == preEnd) {
        return root;
    }

    // 在后序序列中找到左子树的根节点
    int leftRootIndex = postStart;
    while (postorder[leftRootIndex] != preorder[preStart + 1]) {
        leftRootIndex++;
    }

    // 构造左子树
    int leftLength = leftRootIndex - postStart + 1;
    root->left = constructTree(preorder, postorder, preStart + 1, preStart + leftLength, postStart, leftRootIndex);

    // 构造右子树
    root->right = constructTree(preorder, postorder, preStart + leftLength + 1, preEnd, leftRootIndex + 1, postEnd - 1);

    return root;
}

// 先序遍历二叉树
void preorderTraversal(Node* root) {
    if (root == NULL) {
        return;
    }

    printf("%c ", root->data);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 后序遍历二叉树
void postorderTraversal(Node* root) {
    if (root == NULL) {
        return;
    }

    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%c ", root->data);
}

int main() {
    char preorder[] = "ABDECFG";
    char postorder[] = "DEBFGCA";
    int n = sizeof(preorder) / sizeof(preorder[0]);

    Node* root = constructTree(preorder, postorder, 0, n - 1, 0, n - 1);

    printf("先序遍历结果：");
    preorderTraversal(root);
    printf("\n");

    printf("后序遍历结果：");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

在这个示例代码中，我们首先定义了一个结构体Node来表示二叉树的节点。然后，我们实现了一个函数constructTree来根据先序序列和后序序列构造正则二叉树。构造函数的参数包括先序序列、后序序列以及当前子树的起始位置和结束位置。

在构造函数中，我们首先创建了根节点，并根据先序序列确定根节点的数据。然后，我们判断当前子树是否只有一个节点，如果是，则直接返回根节点。接下来，在后序序列中找到左子树的根节点，然后递归构造左子树和右子树。

最后，我们在主函数中调用constructTree函数构造二叉树，并分别使用先序遍历和后序遍历函数打印结果。

运行该程序，将得到以下输出：

先序遍历结果：A B D E C F G 
后序遍历结果：D E B F G C A 

这样，我们就成功地实现了先序和后序构造正则二叉树的算法。