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

C++ 实现二叉树的创建

2023-06-23 07:28:04 深夜i -- --

C++ 二叉树创建

实现二叉树是数据结构中非常基础的部分，因为它是许多其他常见数据结构的基础。在 C++ 中，我们可以使用指针来实现二叉树。

首先，我们需要定义二叉树的节点类。该类应该包含值和左/右子节点的指针。这里我们给出节点类的定义：


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

接下来，我们可以编写一个函数来从输入的一组数组中构造一棵二叉树。例如，我们可以使用以下代码来创建一个简单的二叉树：


TreeNode* buildTree(vector<int>& nums){
 if (nums.empty()) return nullptr;
 TreeNode* root = new TreeNode(nums[0]);
 queue<TreeNode*> q{{root}};
 int i = 1;
 while (!q.empty() && i < nums.size()) {
  TreeNode* t = q.front(); q.pop();
  if (i < nums.size() && nums[i] != NULL) {
   t->left = new TreeNode(nums[i]);
   q.push(t->left);
  }
  i++;
  if (i < nums.size() && nums[i] != NULL) {
   t->right = new TreeNode(nums[i]);
   q.push(t->right);
  }
  i++;
 }
 return root;
}

在这个函数中，我们从队列中按层遍历二叉树，将节点的值设置为给定的数组值之后添加到队列中。这个函数的返回值是树的根节点。

最后，我们可以写一个函数来遍历这棵二叉树。以下是一个实现前序遍历的函数：


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

在这个函数中，我们首先输出当前节点的值，然后递归遍历左右两个子树。

使用上述的函数，我们可以快速地构造一棵二叉树，并进行操作。二叉树有许多决策树和搜索相关的应用，因此学习如何创建和操作它们对于编写高效的算法和程序非常重要。

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

下一篇: C++成绩管理系统课程设计

评论区

()

相似文章