21xrx.com
2025-04-02 12:22:59 Wednesday
文章检索 我的文章 写文章
C++实现二叉树的创建
2023-06-27 12:03:15 深夜i     11     0
C++ 二叉树 实现 创建 节点

二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子树。C++语言中可以使用指针和结构体来实现二叉树的创建。

首先，定义一个结构体表示二叉树中的一个节点，它包含三个成员变量：节点数据、左子树指针和右子树指针。代码如下：

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

其中，val表示节点存储的数据，left和right分别表示左子树指针和右子树指针，这里使用nullptr表示空指针。

接下来，利用递归算法来创建二叉树。递归算法的思想是先递归创建左子树，再递归创建右子树，最后返回当前节点的指针。代码如下：

class Solution {
public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty())
      return nullptr;
    
    int rootVal = preorder[0];
    int rootIndex = 0;
    for (int i = 0; i < inorder.size(); i++) {
      if (inorder[i] == rootVal)
        rootIndex = i;
        break;
      
    }
    vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + rootIndex + 1);
    vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);
    vector<int> rightPreorder(preorder.begin() + rootIndex + 1, preorder.end());
    vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end());
    TreeNode* root = new TreeNode(rootVal);
    root->left = buildTree(leftPreorder, leftInorder);
    root->right = buildTree(rightPreorder, rightInorder);
    return root;
  }
};

在上述代码中，buildTree函数接收两个参数：preorder和inorder，它们分别表示二叉树的前序遍历和中序遍历。函数的返回值为二叉树的根节点指针。

具体实现过程如下：首先判断preorder和inorder是否为空，如果都为空则返回空指针；取preorder的第一个元素作为根节点的值；在inorder中找到根节点所在的位置rootIndex；将preorder和inorder分别拆分为左右子树的前序和中序遍历；创建根节点，递归创建左右子树，将它们分别作为根节点的左右子树指针，最后返回根节点指针。

通过上述递归算法，我们可以创建二叉树，而且可以通过前序遍历和中序遍历快速重构一棵二叉树。这里的方法可以具体在leetcode上测试，加深理解。

  
  

评论区