c++构造利用二叉链表存储表示的二叉树

二叉链表存储表示的二叉树是指使用链式存储结构存储二叉树，每个节点包括一个数据域和两个指针域，分别指向它的左子树和右子树。下面是使用C++实现的二叉链表存储表示的二叉树的构造方法。

首先定义二叉树的节点结构体：

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

然后定义一个递归函数，用于根据给定的数组构造二叉树：

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
  if (postorder.empty()) return NULL;
  int rootVal = postorder.back();
  TreeNode* root = new TreeNode(rootVal);
  int rootIdx = find(inorder.begin(), inorder.end(), rootVal) - inorder.begin();
  vector<int> inorderLeft(inorder.begin(), inorder.begin() + rootIdx);
  vector<int> inorderRight(inorder.begin() + rootIdx + 1, inorder.end());
  vector<int> postorderLeft(postorder.begin(), postorder.begin() + rootIdx);
  vector<int> postorderRight(postorder.begin() + rootIdx, postorder.end() - 1);
  root->left = buildTree(inorderLeft, postorderLeft);
  root->right = buildTree(inorderRight, postorderRight);
  return root;
}

这个函数的参数是中序遍历数组和后序遍历数组，返回值是构造好的二叉树的根节点。

在函数中，首先判断后序遍历数组是否为空，如果为空，则返回NULL。

否则，根据后序遍历数组的最后一个元素创建根节点，并在中序遍历数组中找到根节点的位置。

根据根节点在中序遍历数组中的位置，将中序遍历数组和后序遍历数组分成左子树和右子树两个部分。

然后递归调用buildTree函数构造左子树和右子树，并将它们分别赋值给根节点的左指针和右指针。

最后返回根节点。

完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
  if (postorder.empty()) return NULL;
  int rootVal = postorder.back();
  TreeNode* root = new TreeNode(rootVal);
  int rootIdx = find(inorder.begin(), inorder.end(), rootVal) - inorder.begin();
  vector<int> inorderLeft(inorder.begin(), inorder.begin() + rootIdx);
  vector<int> inorderRight(inorder.begin() + rootIdx + 1, inorder.end());
  vector<int> postorderLeft(postorder.begin(), postorder.begin() + rootIdx);
  vector<int> postorderRight(postorder.begin() + rootIdx, postorder.end() - 1);
  root->left = buildTree(inorderLeft, postorderLeft);
  root->right = buildTree(inorderRight, postorderRight);
  return root;
}

void inorderTraversal(TreeNode* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  cout << root->val << " ";
  inorderTraversal(root->right);
}

int main() {
  vector<int> inorder = {9,3,15,20,7};
  vector<int> postorder = {9,15,7,20,3};
  TreeNode* root = buildTree(inorder, postorder);
  inorderTraversal(root);
  return 0;
}

输出结果为：9 3 15 20 7，表示构造的二叉树的中序遍历结果为{9, 3, 15, 20, 7}。