C++二叉树：建立与遍历 |21xrx.com

C++二叉树：建立与遍历

2023-07-02 11:04:02 深夜i -- --

C++ 二叉树建立遍历数据结构

C++是一种广泛使用的编程语言，它具有高效、灵活和可靠的特性，因此在算法和数据结构方面应用广泛。二叉树是一种常见的数据结构，它的特点是每个节点最多有两个子节点。在本文中，我们将讨论如何在C++中建立二叉树，并以不同的方式进行遍历。

建立二叉树

在C++中，可以使用class和struct关键字来定义二叉树节点。下面是一个定义二叉树节点的示例：


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

该节点具有三个成员变量，data存储该节点的值，left和right分别指向左子树和右子树的指针。

使用上述节点定义，我们可以通过递归地插入新节点来构建二叉树。下面是一个具有插入节点功能的示例函数：


void insert(Node* &root, int value)
{
  if (root == nullptr)
  
    root = new Node;
    root->data = value;
    root->left = root->right = nullptr;
  
  else if (value < root->data)
    insert(root->left, value);
  else
    insert(root->right, value);
}

该函数通过引用传递根节点指针和要插入的值。如果根节点为空，则创建一个新节点并将其设置为根节点。否则，将值与根节点的值进行比较，并递归地将该值插入左子树或右子树中。

遍历二叉树

二叉树有三种常见的遍历方式：前序遍历、中序遍历和后序遍历。下面分别介绍这三种遍历方式的实现。

1. 前序遍历

前序遍历的顺序是：根节点->左子树->右子树。下面是前序遍历的示例实现：


void preOrder(Node* root)
{
  if (root != nullptr)
  {
    cout << root->data << " ";
    preOrder(root->left);
    preOrder(root->right);
  }
}

该函数递归地遍历二叉树，并在访问节点时输出该节点的值。

2. 中序遍历

中序遍历的顺序是：左子树->根节点->右子树。下面是中序遍历的示例实现：


void inOrder(Node* root)
{
  if (root != nullptr)
  {
    inOrder(root->left);
    cout << root->data << " ";
    inOrder(root->right);
  }
}

该函数递归地遍历二叉树，并在访问节点时输出该节点的值。

3. 后序遍历

后序遍历的顺序是：左子树->右子树->根节点。下面是后序遍历的示例实现：


void postOrder(Node* root)
{
  if (root != nullptr)
  {
    postOrder(root->left);
    postOrder(root->right);
    cout << root->data << " ";
  }
}

该函数递归地遍历二叉树，并在访问节点时输出该节点的值。

总结

在C++中，可以通过递归地插入新节点来构建二叉树，并使用三种不同的遍历方式来访问二叉树。这些遍历方式包括前序遍历、中序遍历和后序遍历。掌握这些概念和使用方法，可以帮助我们在算法和数据结构方面更加熟练和自如。

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

下一篇: "如何编写Java多线程代码？"

评论区

()

相似文章