C++实现二叉树的先序、中序、后序遍历 |21xrx.com

C++实现二叉树的先序、中序、后序遍历

2023-07-08 04:06:46 深夜i -- --

C++ 二叉树先序遍历中序遍历后序遍历

二叉树是一种非常有用的数据结构，在计算机科学领域中，我们通常使用二叉树来解决各种不同类型的问题。为了使用二叉树并对其进行操作，我们需要学会遍历它。在 C++ 中，有三种不同的遍历方式：先序、中序和后序遍历。

先序遍历是指从根节点开始，按照根、左、右的顺序遍历整个二叉树。中序遍历是指从根节点开始，按照左、根、右的顺序遍历整个二叉树。后序遍历是指从根节点开始，按照左、右、根的顺序遍历整个二叉树。

实现二叉树的先序、中序和后序遍历是很容易的。我们可以使用递归函数来完成这个任务，因为这个函数具有访问每个节点的能力。首先，我们需要定义一个表示二叉树节点的结构体或类。这个结构体或类应该包含两个成员变量：左侧子树和右侧子树。

以下是一个示例代码：


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

需要注意的是，这里我们使用了指针来指向左侧和右侧子树，因为二叉树的每个节点都有左侧和右侧子树。

接下来，我们可以使用先序遍历函数来遍历二叉树：


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

在先序遍历函数中，我们首先检查根节点是否为空。如果为空，则返回并停止遍历。否则，我们将当前节点的值打印出来，再分别对左侧和右侧子树进行遍历。

中序遍历和后序遍历的实现方式与先序遍历类似。中序遍历函数如下：


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

后序遍历函数如下：


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

最后，我们可以将这些函数应用于二叉树的遍历中。例如，我们可以创建一个二叉树并对其进行先序遍历，如下所示：


int main() {
  TreeNode* root = new TreeNode(1); // 创建根节点
  root->left = new TreeNode(2); // 创建左侧子树
  root->right = new TreeNode(3); // 创建右侧子树
  root->left->left = new TreeNode(4);
  root->left->right = new TreeNode(5);
  root->right->left = new TreeNode(6);
  root->right->right = new TreeNode(7);
  cout << "Preorder Traversal: ";
  preOrder(root);
  cout << endl;
  return 0;
}

输出结果如下：

Preorder Traversal: 1 2 4 5 3 6 7

通过这篇文章，我们学习了如何使用 C++ 语言来实现二叉树的先序、中序和后序遍历。使用这些遍历方式，我们可以轻松地使用二叉树来解决各种计算机科学问题。

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

下一篇: 使用Node.js编写独立的服务器应用

评论区

()

相似文章