二叉树的实现C++

二叉树是一种非常常见的数据结构，它由节点和边构成，每个节点最多有两个子节点。二叉树的实现可以使用指针或数组等方式，这里给出一种基于指针的二叉树实现。

定义二叉树节点类：

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : val(val), left(NULL), right(NULL) {}
};

在类中定义了节点的值（val）和左右子节点指针（left和right）。构造函数用来初始化节点。

定义二叉树类：

class BinaryTree {
private:
    TreeNode *root;
public:
    BinaryTree() : root(NULL) {}
    void insert(int val);
    void traverse();
    void inorder(TreeNode *node);
};

二叉树类中包含一个根节点指针（root），构造函数用来初始化根节点。insert()函数用来插入新的节点，traverse()函数用来遍历二叉树，inorder()函数用来中序遍历二叉树。中序遍历是指先遍历左子树，再遍历根节点，最后遍历右子树。

插入节点的实现：

void BinaryTree::insert(int val) {
    TreeNode *node = new TreeNode(val);
    if (root == NULL) {
        root = node;
        return;
    }
    TreeNode *p = root;
    while (true) {
        if (val < p->val) {
            if (p->left == NULL) {
                p->left = node;
                break;
            }
            p = p->left;
        } else {
            if (p->right == NULL) {
                p->right = node;
                break;
            }
            p = p->right;
        }
    }
}

在插入节点时，如果根节点为空，则直接将新节点作为根节点。否则，从根节点开始遍历二叉树，如果新节点的值小于当前节点的值，则向左子树遍历，否则向右子树遍历，直到找到一个空节点为止，将新节点插入到该空节点位置。

中序遍历的实现：

void BinaryTree::traverse() {
    inorder(root);
    cout << endl;
}

void BinaryTree::inorder(TreeNode *node) {
    if (node == NULL) {
        return;
    }
    inorder(node->left);
    cout << node->val << " ";
    inorder(node->right);
}

中序遍历的实现是递归的，先遍历左子树，再遍历根节点，最后遍历右子树。如果当前节点为空，则返回。否则，先递归遍历左子树，输出当前节点的值，再递归遍历右子树。

完整代码如下：

#include <iostream>

using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : val(val), left(NULL), right(NULL) {}
};

class BinaryTree {
private:
    TreeNode *root;
public:
    BinaryTree() : root(NULL) {}
    void insert(int val);
    void traverse();
    void inorder(TreeNode *node);
};

void BinaryTree::insert(int val) {
    TreeNode *node = new TreeNode(val);
    if (root == NULL) {
        root = node;
        return;
    }
    TreeNode *p = root;
    while (true) {
        if (val < p->val) {
            if (p->left == NULL) {
                p->left = node;
                break;
            }
            p = p->left;
        } else {
            if (p->right == NULL) {
                p->right = node;
                break;
            }
            p = p->right;
        }
    }
}

void BinaryTree::traverse() {
    inorder(root);
    cout << endl;
}

void BinaryTree::inorder(TreeNode *node) {
    if (node == NULL) {
        return;
    }
    inorder(node->left);
    cout << node->val << " ";
    inorder(node->right);
}

int main() {
    BinaryTree tree;
    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(1);
    tree.insert(4);
    tree.insert(6);
    tree.insert(8);
    tree.traverse();
    return 0;
}