C++ 实现二叉树的创建方法 |21xrx.com

C++ 实现二叉树的创建方法

2023-06-26 14:50:06 深夜i -- --

C++ 二叉树创建方法

二叉树是一种常见的数据结构，它由根节点以及每个节点的左右子树组成，它可以用来存储有层次结构的数据。在 C++ 中，我们可以使用指针和动态内存分配来实现二叉树的创建和操作。

具体实现方法如下：

1. 定义二叉树节点的结构体，包含数据域和指向左右子树的指针（nullptr 表示空节点）：


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

2. 定义一个函数，用于根据给定的数据创建二叉树。函数接收一个数组作为参数，数组元素为每个节点的数值，其中第一个元素为根节点的数值。函数返回指向根节点的指针。


TreeNode* createTree(vector<int>& nums) {
  if (nums.empty()) return nullptr;
  int i = 0;
  TreeNode* root = new TreeNode(nums[i++]); // 创建根节点
  queue<TreeNode*> q{{root}}; // 用队列保存每一层的节点
  while (i < nums.size()) {
    TreeNode* cur = q.front();
    if (nums[i] != -1) { // 左子树非空
      cur->left = new TreeNode(nums[i]);
      q.push(cur->left);
    }
    i++;
    if (i < nums.size() && nums[i] != -1) { // 右子树非空
      cur->right = new TreeNode(nums[i]);
      q.push(cur->right);
    }
    i++;
    q.pop();
  }
  return root;
}

3. 在主函数中调用 createTree 函数，传入数据数组。


int main() {
  vector<int> nums = -1;
  TreeNode* root = createTree(nums);
  // 对二叉树进行其他操作
  return 0;
}

在上述代码中，数据数组 1 表示二叉树的形状为：

1 / \ 2 3 / 4 \ 5

其中，-1 表示空节点。接下来，我们可以对二叉树进行其他操作，例如搜索某个节点、遍历整棵树等。

二叉树虽然是一种基础的数据结构，但是它在算法和数据结构设计中扮演着重要的角色，是其他更为复杂的数据结构和算法设计的基础。了解二叉树的实现方法和使用场景，对于 C++ 开发和算法设计都是非常有益的。

上一篇: idea打包java可执行jar包

下一篇: 如何在C++编程中运行代码并查看效果

评论区

()

相似文章