21xrx.com
2024-09-20 01:09:20 Friday
登录
文章检索 我的文章 写文章
C++ 实现完全二叉树的构建
2023-06-23 19:55:03 深夜i     --     --
C++ 完全二叉树 构建

C++ 是一门高级编程语言，被广泛应用于软件开发和编程领域。它拥有一系列强大的数据结构，如二叉树和完全二叉树等，在编写程序时可以大大简化代码。本文将介绍如何使用 C++ 实现完全二叉树的构建。

什么是完全二叉树？

完全二叉树是一种特殊的二叉树，满足以下两个条件：

1. 除了最后一层，其余层的节点数都是满的。

2. 最后一层的节点从左到右依次排列。

如下图所示：

     1

    /  \

   2   3

   / \  /

  4  5 6

在上述完全二叉树中，每层都是满的，而最后一层节点从左到右依次排列。这种树结构非常常见，特别是在堆排序和优先队列中。

C++ 实现完全二叉树的构建

我们可以使用 C++ 实现完全二叉树的构建。首先，我们需要定义一个二叉树节点的数据结构。

struct TreeNode

{

  int val;

  TreeNode* left;

  TreeNode* right;

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

};

可以看出，这里的二叉树节点包括一个整型变量 val 和两个指针分别指向左子节点和右子节点。

接下来，我们需要写一个函数来构建完全二叉树。我们可以使用广度优先搜索的方法，从根节点开始逐层构建二叉树。在构建过程中，我们需要一些额外的数据结构来记录每层节点的信息。

TreeNode* buildCompleteBinaryTree(vector & nums)

{

  int n = nums.size();

  if (n == 0) return nullptr;

  queue q;

  TreeNode* root = new TreeNode(nums[0]);

  q.push(root);

  int i = 1;

  while (i < n)

  {

    TreeNode* cur = q.front();

    q.pop();

    if (cur == nullptr) continue;

    cur->left = new TreeNode(nums[i]);

    q.push(cur->left);

    ++i;

    if (i < n)

    {

      cur->right = new TreeNode(nums[i]);

      q.push(cur->right);

      ++i;

    }

  }

  return root;

}

上述代码中，buildCompleteBinaryTree 函数接收一个整数数组 nums，用于构建完全二叉树。我们首先判断数组是否为空，如果为空，直接返回 nullptr；如果不为空，我们定义一个队列 q，将输入数组的第一个元素作为根节点，加入队列 q 中。接着，我们用一个 while 循环逐层构建二叉树，直到数组中的所有元素都加入到了树中。

在 while 循环中，我们首先从队列 q 中取出一个节点 cur，这个节点就是我们要逐层构建的节点。如果 cur 是空指针，则直接跳过；如果 cur 没有左子节点，则将数组中的下一个元素作为它的左子节点，加入队列 q 中；如果 cur 已经有了左子节点，则将数组中的下一个元素作为它的右子节点，也加入队列 q 中。

最后，我们返回根节点，完整的代码如下：

#include

#include

#include

using namespace std;

struct TreeNode

{

  int val;

  TreeNode* left;

  TreeNode* right;

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

};

TreeNode* buildCompleteBinaryTree(vector & nums)

{

  int n = nums.size();

  if (n == 0) return nullptr;

  queue q;

  TreeNode* root = new TreeNode(nums[0]);

  q.push(root);

  int i = 1;

  while (i < n)

  {

    TreeNode* cur = q.front();

    q.pop();

    if (cur == nullptr) continue;

    cur->left = new TreeNode(nums[i]);

    q.push(cur->left);

    ++i;

    if (i < n)

    {

      cur->right = new TreeNode(nums[i]);

      q.push(cur->right);

      ++i;

    }

  }

  return root;

}

void print(TreeNode* root)

{

  if (root == nullptr) return;

  cout << root->val << " ";

  print(root->left);

  print(root->right);

}

int main()

{

  vector nums = 3;

  TreeNode* root = buildCompleteBinaryTree(nums);

  print(root);

  return 0;

}

我们可以将构建的完全二叉树打印出来，验证我们的代码是否正确：

1 2 4 5 3 6

上述代码先定义了一个包含六个元素的整型数组，用于构建二叉树。然后，我们调用 buildCompleteBinaryTree 函数来构建完全二叉树，将得到的根节点存储在 root 变量中。最后，我们调用 print 函数打印出这个完全二叉树的所有节点。

总结

本文介绍了如何使用 C++ 实现完全二叉树的构建。完全二叉树在编写程序时经常用到，这个树结构不仅可以用于优先队列和堆排序，也可以用于解决许多实际问题。使用 C++ 实现二叉树，代码简洁易懂，可以大大减少工作量，并且提高代码执行效率。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复