How to construct a Binary tree in C/ C ++

在C/C++中构造二叉树通常需要定义一个二叉树节点的结构体，然后通过函数来创建新节点、插入节点以及遍历二叉树等。下面我将详细说明如何在C/C++中构造一个简单的二叉树。

1. 定义二叉树节点的结构体

首先，定义一个二叉树节点结构体TreeNode，其中包含整型的数据部分data以及两个指向左子树和右子树的指针left和right：

cpp
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    // 构造函数
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

2. 创建新节点

创建新节点的函数可以直接使用TreeNode的构造函数来实现，如上所述构造函数已经定义好了。

3. 插入节点

插入节点需要考虑将要插入的值与当前节点值的比较，基于比较结果递归地将新值插入到左子树或右子树：

cpp
TreeNode* insertTreeNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return new TreeNode(val);
    }

    if (val < root->data) {
        root->left = insertTreeNode(root->left, val);
    } else if (val > root->data) {
        root->right = insertTreeNode(root->right, val);
    }

    return root;
}

4. 遍历二叉树

二叉树的遍历通常包括前序遍历、中序遍历和后序遍历。以中序遍历为例，递归地遍历左子树，访问根节点，再递归地遍历右子树：

cpp
void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

示例代码

结合以上内容，一个完整的示例代码如下：

cpp
#include <iostream>

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

TreeNode* insertTreeNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return new TreeNode(val);
    }

    if (val < root->data) {
        root->left = insertTreeNode(root->left, val);
    } else if (val > root->data) {
        root->right = insertTreeNode(root->right, val);
    }

    return root;
}

void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

int main() {
    TreeNode* root = nullptr;
    root = insertTreeNode(root, 8);
    insertTreeNode(root, 3);
    insertTreeNode(root, 10);
    insertTreeNode(root, 1);
    insertTreeNode(root, 6);
    insertTreeNode(root, 14);

    std::cout << "Inorder traversal of binary tree: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

这段代码首先创建一个二叉树，然后插入几个节点，并使用中序遍历输出它们。这是构造和操作二叉树的基本方法。