C++ 实现二叉树的建立和遍历代码 |21xrx.com

C++ 实现二叉树的建立和遍历代码

2023-07-05 12:38:00 深夜i -- --

C++ 二叉树建立遍历代码

二叉树是一种非常重要的数据结构，它可以在计算机科学中扮演着重要的角色。在很多场景下，我们需要快速地搜索和遍历数据，而二叉树可以为我们提供这样的功能。在这篇文章中，我们将介绍使用C++实现二叉树的建立和遍历的方法。

二叉树的定义很简单，它由节点的左右子节点和一个根节点组成，我们可以通过迭代的方式不断扩展二叉树。在C++语言中，我们可以使用结构体或类来定义一个二叉树节点，例如：


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

上述代码中，我们定义了一个结构体 `TreeNode`，每个节点包含一个 `int` 类型的值 `val`，以及左右子节点 `left` 和 `right`。在构造函数中，我们初始化了将这些变量设置为 `nullptr`。

接下来，我们需要实现二叉树的建立。这个过程可以通过递归实现，也可以通过迭代实现。下面是使用递归实现二叉树的代码：


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

在上面的代码中，我们定义了一个函数 `buildTree` 它接受两个向量作为输入，`preorder` 表示前序遍历的结果，`inorder` 表示中序遍历的结果。首先，我们判断输入的向量是否为空，如果为空，直接将节点置为 `nullptr`。然后，我们从 `preorder` 中取出根节点，找到它在 `inorder` 中的位置，将其左边的元素作为左子树，右边的元素作为右子树。接着，我们使用递归的方式建立左右子树，返回根节点即可。

接下来是实现二叉树的遍历操作，包括前序遍历、中序遍历和后序遍历。我们可以通过递归的方式来遍历这个二叉树，具体代码实现如下：


void preorderTraverse(TreeNode* root) {
  if (root == nullptr)
    return;
  
  cout << root->val << " ";
  preorderTraverse(root->left);
  preorderTraverse(root->right);
}
void inorderTraverse(TreeNode* root) {
  if (root == nullptr)
    return;
  
  inorderTraverse(root->left);
  cout << root->val << " ";
  inorderTraverse(root->right);
}
void postorderTraverse(TreeNode* root) {
  if (root == nullptr)
    return;
  
  postorderTraverse(root->left);
  postorderTraverse(root->right);
  cout << root->val << " ";
}

上述代码中，我们分别定义了三个递归函数 `preorderTraverse`、`inorderTraverse` 和 `postorderTraverse`，它们分别实现了前序遍历、中序遍历和后序遍历操作。具体实现中，我们首先判断节点是否为空，如果是就返回。然后分别对其左子树和右子树递归遍历，最后输出当前节点即可。

总的来说，我们使用C++实现二叉树的建立和遍历操作其实是非常简单的。通过结构体或类定义节点，并使用递归操作，我们可以在短时间内轻松地实现这些操作。在实际开发和算法题解中，我们也常常需要处理二叉树相关的问题，因此对二叉树的理解和实现是非常重要的。

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

下一篇: 如何开发我的世界Java版模组？

评论区

()

相似文章