完整的C++ 二叉树遍历算法 |21xrx.com

完整的C++ 二叉树遍历算法

2023-07-08 18:26:43 深夜i -- --

C++ 二叉树遍历算法

C++ 二叉树遍历算法是一种非常重要的算法，它可以用于在二叉树中查找数据、改变二叉树中节点的位置以及删除和插入节点等操作。在本文中，我们将详细介绍如何使用C++语言编写一个完整的二叉树遍历算法。

首先，我们需要创建一个二叉树的节点结构体，其中包含该节点的值以及指向左右子节点的指针。代码如下：


struct Node {
  int value;
  Node* left;
  Node* right;
};

接下来，我们需要编写一个函数来创建一个新节点，并初始化其值和指针。代码如下：


Node* createNode(int value) {
  Node* node = new Node();
  node->value = value;
  node->left = NULL;
  node->right = NULL;
  return node;
}

现在我们可以开始编写二叉树遍历的算法了。二叉树遍历有三种方式，分别为前序遍历、中序遍历和后序遍历。下面我们将分别介绍这三种遍历方式的实现。

前序遍历算法

前序遍历先遍历根节点，然后遍历左子树，最后遍历右子树。代码如下：


void preOrderTraversal(Node* node) {
  if (node != NULL) {
    cout << node->value << endl;
    preOrderTraversal(node->left);
    preOrderTraversal(node->right);
  }
}

中序遍历算法

中序遍历先遍历左子树，然后遍历根节点，最后遍历右子树。代码如下：


void inOrderTraversal(Node* node) {
  if (node != NULL) {
    inOrderTraversal(node->left);
    cout << node->value << endl;
    inOrderTraversal(node->right);
  }
}

后序遍历算法

后序遍历先遍历左子树，然后遍历右子树，最后遍历根节点。代码如下：


void postOrderTraversal(Node* node) {
  if (node != NULL) {
    postOrderTraversal(node->left);
    postOrderTraversal(node->right);
    cout << node->value << endl;
  }
}

至此，我们已经实现了三种二叉树遍历算法。如果您想测试以上算法的运行情况，您需要手动构建一个二叉树，代码如下：


int main() {
  Node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  cout << "Pre-order traversal: ";
  preOrderTraversal(root);
  cout << "In-order traversal: ";
  inOrderTraversal(root);
  cout << "Post-order traversal: ";
  postOrderTraversal(root);
  return 0;
}

在本文中，我们详细介绍了如何使用C++编写一个完整的二叉树遍历算法，包括以上三种遍历方式的实现方式以及如何手动构建一个二叉树进行测试。如果您需要更深入地研究这个算法，我们建议您参考更多相关的C++教程和示例代码。

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

下一篇: C++结构体的输入输出方法

评论区

()

相似文章