c++二叉树怎么创建及遍历

前言

二叉树是一种常用的数据结构，它由一组节点组成，每个节点最多有两个子节点。对于二叉树的创建和遍历来说，有多种方法可供选择，每种方法都有自己的特点和适用场景。在本文中，我们将重点介绍如何使用C++创建和遍历二叉树。

创建二叉树

在C++中，我们可以通过定义一个二叉树的节点结构来创建二叉树。节点结构包括一个值和指向左子节点和右子节点的指针。首先，我们需要定义一个节点类：

class Node {
public:
    int value;
    Node* left;
    Node* right;
    
    Node(int val) {
        value = val;
        left = nullptr;
        right = nullptr;
    }
};

接下来，我们可以使用该节点类来创建二叉树。一种常见的创建方法是通过递归创建，即先创建根节点，然后递归地创建左子树和右子树。下面是一个示例的递归创建二叉树的函数：

Node* createBinaryTree(vector& nums, int start, int end) {
    if (start > end) {
        return nullptr;
    }
    
    int mid = (start + end) / 2;
    Node* root = new Node(nums[mid]);
    
    root->left = createBinaryTree(nums, start, mid - 1);
    root->right = createBinaryTree(nums, mid + 1, end);
    
    return root;
}

以上代码中，我们传入一个有序数组nums、数组起始索引start和数组结束索引end作为参数。函数通过计算中间索引mid，并以nums[mid]的值创建一个节点作为根节点。然后，它递归地创建左子树和右子树，分别调用自身，并将子树的根节点赋值给root的左右指针。

遍历二叉树

在C++中，常见的二叉树遍历方法有三种：前序遍历、中序遍历和后序遍历。下面分别介绍这三种遍历方法：

• 前序遍历：首先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。
• 中序遍历：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
• 后序遍历：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。

下面是示例代码实现这三种遍历方法：

void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
}

void postorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->value << " ";
}

总结

通过使用C++中的类和递归，我们可以方便地创建和遍历二叉树。创建二叉树时，可以使用递归方法来分别创建左子树和右子树，然后将其链接到根节点。遍历二叉树时，可以通过前序、中序和后序三种方法来获取不同的节点顺序。这些方法在解决二叉树相关问题时非常有用。