利用c++设一棵二叉树以二叉链表表示 b) 利用递归方式实现由后序、中序序列构造二叉树的算

在C++中，我们可以使用二叉链表来表示二叉树，其中每个节点包含数据、左指针和右指针。下面是一个简单的示例，展示如何创建一个基本的二叉链表结构：

class Node {
public:
    int data;
    Node* left;
    Node* right;
    // 构造函数
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// 插入节点到二叉链表
void insert(Node*& root, int value) {
    if (root == nullptr) {
        root = new Node(value);
    } else if (value < root->data) {
        insert(root->left, value);
    } else {
        insert(root->right, value);
    }
}

// 创建空二叉树
Node* createEmptyBinaryTree() {
    return nullptr;
}

对于从后序遍历（Right-Left-Root）和中序遍历（Left-Root-Right）构建二叉树，我们通常需要两个辅助函数。递归方式可以这样实现：

// 后序遍历构造二叉树
Node* buildTreeFromPostOrder(vector<int>& postorder, int n) {
    if (postorder.empty()) return nullptr; // 根据后序最后一个元素作为根

    int root_val = postorder.back();
    Node* root = new Node(root_val);
    postorder.pop_back(); // 移除根节点

    // 分别递归处理左右子树
    root->left = buildTreeFromPostOrder(postorder, n); // 左子树
    root->right = buildTreeFromPostOrder(postorder, n); // 右子树

    return root;
}

// 中序遍历构造二叉树
Node* buildTreeFromInOrder(vector<int>& inorder, int start, int end) {
    if (start > end) return nullptr;

    int val = inorder[start]; // 找到当前位置的值
    Node* root = new Node(val);

    // 在剩余的中序序列里找到根的位置
    int index = searchInOrder(inorder, start + 1, end, val);
    root->left = buildTreeFromInOrder(inorder, start, index - 1);
    root->right = buildTreeFromInOrder(inorder, index + 1, end);

    return root;
}

int searchInOrder(vector<int>& inorder, int low, int high, int target) {
    // 省略实际搜索部分，这里假设已有一个线性查找函数
    // 返回目标值所在子数组的起始索引
}