用C++构建二叉树 |21xrx.com

用C++构建二叉树

2023-06-29 04:45:33 深夜i 21 0

C++ 二叉树构建节点遍历

二叉树是一种重要的数据结构，它在计算机科学中有广泛的应用。它由节点和边组成，每个节点最多有两个子节点。二叉树的一个重要特征是可以用递归的方式来遍历所有的节点。在这篇文章中，我们将介绍如何使用C++构建二叉树。

首先，我们需要定义一个二叉树节点的结构。一个二叉树节点包括一个值和两个指向其子节点的指针。下面是节点的定义：

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

我们可以看到，这个节点包含一个整数值，左子节点指针和右子节点指针，我们也可以注意到，节点的构造函数初始化左右子节点指针为空指针。

接下来，我们需要一个方法来构建二叉树。我们可以使用递归的方式来构建二叉树。我们可以先构建根节点，然后依次构建左子树和右子树。下面是构建二叉树的方法：

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
  if(preorder.empty() || inorder.empty())
    return nullptr;
  
  int rootVal = preorder[0];
  TreeNode *root = new TreeNode(rootVal);
  auto rootPos = find(inorder.begin(), inorder.end(), rootVal);
  int leftLength = rootPos - inorder.begin();
  vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + leftLength + 1);
  vector<int> leftInorder(inorder.begin(), rootPos);
  vector<int> rightPreorder(preorder.begin() + leftLength + 1, preorder.end());
  vector<int> rightInorder(rootPos + 1, inorder.end());
  root->left = buildTree(leftPreorder, leftInorder);
  root->right = buildTree(rightPreorder, rightInorder);
  return root;
}

这个方法的参数包括一个先序遍历序列和一个中序遍历序列。它首先检查这两个序列是否为空，如果为空，则创建空的二叉树。否则，它从先序遍历序列中获取根节点的值，并将其作为参数创建一个新的二叉树节点。接下来，我们查找根节点在中序遍历序列中的位置，并计算出左子树的长度。然后，我们使用子向量来表示左子树的先序遍历和中序遍历序列和右子树的先序遍历和中序遍历序列。最后，我们递归地构建左子树和右子树，并将它们分别赋值给新节点的左子节点和右子节点。

这个算法的时间复杂度是O(nlogn)，其中n是二叉树中节点的数量，因为我们需要做logn次递归，并且每次递归需要O(n)的时间来查找根节点和计算左子树的长度。

总的来说，使用C++构建二叉树是一项重要的任务，在这篇文章中，我们介绍了如何定义节点，以及如何使用递归的方式来构建二叉树。我们希望这篇文章对您有所帮助，如果您对C++编程感兴趣，可以继续深入学习。

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

下一篇: 如何在C++派生类中调用基类构造函数

评论区

相似文章