C++二叉树的创建及遍历详情

什么是二叉树

二叉树是一种树形结构，它特别的地方在于，每个节点最多拥有两个子节点，因此叫做二叉树。

二叉树的一个重要性质是，我们可以使用递归的方式进行遍历。

二叉树的构造

可以使用结构体来表示二叉树中的每个节点：

struct Node
{
    int value;
    Node* left_child;
    Node* right_child;
};

其中，value表示节点的值，left_child和right_child分别表示左右子节点。

首先，我们需要构造一个空的二叉树：

Node* root = nullptr;

然后，我们可以开始往二叉树中插入节点：

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

上述代码中，insert函数接收一个指向根节点的指针root，以及需要插入的值value。如果二叉树为空，则直接新建一个节点；否则，如果value小于根节点的值，则递归地插入到左子树中；如果value大于根节点的值，则递归地插入到右子树中。

二叉树的遍历

遍历二叉树主要有三种方式：先序遍历、中序遍历和后序遍历。

先序遍历

先序遍历的顺序为：先输出根节点，再遍历左子树，最后遍历右子树。使用递归的方式进行先序遍历：

void pre_order_traversal(Node* root)
{
    if (root == nullptr)
    {
        return;
    }
    std::cout << root->value << " ";
    pre_order_traversal(root->left_child);
    pre_order_traversal(root->right_child);
}

中序遍历

中序遍历的顺序为：先遍历左子树，再输出根节点，最后遍历右子树。使用递归的方式进行中序遍历：

void in_order_traversal(Node* root)
{
    if (root == nullptr)
    {
        return;
    }
    in_order_traversal(root->left_child);
    std::cout << root->value << " ";
    in_order_traversal(root->right_child);
}

后序遍历

后序遍历的顺序为：先遍历左子树，再遍历右子树，最后输出根节点。使用递归的方式进行后序遍历：

void post_order_traversal(Node* root)
{
    if (root == nullptr)
    {
        return;
    }
    post_order_traversal(root->left_child);
    post_order_traversal(root->right_child);
    std::cout << root->value << " ";
}

示例说明

假设要构造以下二叉树：

     50
   /    \
  30     70
 /  \   /  \
20  40 60  80

可以使用以下代码构造：

Node* root = nullptr;
insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

对该二叉树进行中序遍历，输出结果为：

20 30 40 50 60 70 80

对该二叉树进行先序遍历，输出结果为：

50 30 20 40 70 60 80

对该二叉树进行后序遍历，输出结果为：

20 40 30 60 80 70 50

总结

以上就是C++二叉树的创建及遍历详情。二叉树是一种重要的数据结构，希望本攻略能够帮助读者理解和掌握二叉树的基本原理和用法。