如何用C++创建一颗二叉树 |21xrx.com

如何用C++创建一颗二叉树

2023-07-06 00:51:10 深夜i -- --

C++ 二叉树创建

二叉树是一种常见的数据结构，它是由节点和边构成的，每个节点最多拥有两个子节点，我们可以用C++语言来创建一颗二叉树。

首先，我们需要定义节点类，它包括存储节点值的变量和两个指针，分别指向左子树和右子树。我们可以用以下代码来定义一个简单的节点类：


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

接下来，我们需要编写一个创建二叉树的函数，该函数接受一个整数数组和数组的长度作为参数，并返回一颗二叉树的根节点。

我们可以使用递归算法来创建二叉树，从根节点开始，将数组分成两个子数组，并分别递归创建左子树和右子树，最后将左右子树连接到根节点上。以下是一个简单的递归函数：


Node* buildTree(int* arr, int len) {
  if (len == 0)
    return NULL;
  
  int mid = len / 2;
  Node* root = new Node(arr[mid]);
  root->left = buildTree(arr, mid);
  root->right = buildTree(arr + mid + 1, len - mid - 1);
  return root;
}

在上述代码中，我们首先判断数组的长度是否为0，如果是，返回NULL，表示当前节点为空。然后，我们计算数组的中间元素位置，并以此位置的元素创建一个新的节点作为当前节点。接着，我们递归创建左子树和右子树，将它们连接到当前节点上，并返回当前节点。

最后，我们可以通过以下代码测试我们创建的二叉树函数：


int main() {
  int arr[] = 6;
  Node* root = buildTree(arr, 7);
  return 0;
}

上述代码将创建一个包含7个元素的数组，并将其作为参数传递给buildTree函数来创建二叉树。最终，我们可以通过检查根节点来确定二叉树是否成功创建。

总结一下，用C++创建一颗二叉树需要定义一个节点类，编写一个递归函数来创建二叉树，并在主函数中测试它的工作效果。对于初学者来说，通过理解递归算法的过程，创建一颗二叉树不是很难。

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

下一篇: C++中函数的返回值可用作函数重载的条件

评论区

()

相似文章