C++二叉树结构的建立与基本操作

C++二叉树是一种非常常见的数据结构，同时也是算法中经常使用的一种数据结构。本文将详细讲解C++二叉树的建立和基本操作，包括二叉树的定义、创建、遍历和删除等。

1. 二叉树的定义

二叉树是一种树形结构，每个节点最多只有两个子节点：左子节点和右子节点。树的深度取决于有多少个节点，根节点是最顶端的节点，不再有父节点。节点之间存在一些有天然排序关系且有先后性的关系，因此二叉树通常用于查找、排序等算法中。

二叉树的节点可以用一个结构体来定义，结构体中包含了一个指向左子节点和右子节点的指针，以及一个数据域，如下所示：

struct TreeNode{
    int data;                // 数据域
    TreeNode* left;          // 左子节点指针
    TreeNode* right;         // 右子节点指针
    TreeNode(int val)        // 构造函数
    : data(val), left(nullptr), right(nullptr){}
};

2. 二叉树的创建

二叉树的创建可以采用递归的方式，先创建根节点，再创建左右子树。具体实现如下：

TreeNode* CreateBinaryTree(){
    int val;
    cout << "输入节点的值（-1代表空节点）：";
    cin >> val;
    if(val == -1){
        return nullptr;     // 空节点
    }
    TreeNode* node = new TreeNode(val);     // 创建新节点
    node->left = CreateBinaryTree();        // 创建左子树
    node->right = CreateBinaryTree();       // 创建右子树
    return node;
}

3. 二叉树的遍历

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

前序遍历

前序遍历的思路是先遍历节点本身，再遍历左子树，最后遍历右子树。具体实现如下：

void preorderTraversal(TreeNode* root){
    if(root == nullptr){
        return;         // 空树，直接返回
    }
    cout << root->data << " ";         // 遍历根节点
    preorderTraversal(root->left);     // 遍历左子树
    preorderTraversal(root->right);    // 遍历右子树
}

中序遍历

中序遍历的思路是先遍历左子树，再遍历节点本身，最后遍历右子树。具体实现如下：

void inorderTraversal(TreeNode* root){
    if(root == nullptr){
        return;         // 空树，直接返回
    }
    inorderTraversal(root->left);      // 遍历左子树
    cout << root->data << " ";         // 遍历根节点
    inorderTraversal(root->right);     // 遍历右子树
}

后序遍历

后序遍历的思路是先遍历左子树，再遍历右子树，最后遍历节点本身。具体实现如下：

void postorderTraversal(TreeNode* root){
    if(root == nullptr){
        return;         // 空树，直接返回
    }
    postorderTraversal(root->left);    // 遍历左子树
    postorderTraversal(root->right);   // 遍历右子树
    cout << root->data << " ";         // 遍历根节点
}

4. 二叉树的删除

二叉树的删除主要有三种情况：

• 被删除节点没有子节点，直接删除
• 被删除节点只有一个子节点，将其子节点代替该节点
• 被删除节点有两个子节点，将右子树中的最小值替换到该节点

具体实现代码如下：

TreeNode* deleteNode(TreeNode* root, int target){
    if(root == nullptr){
        return nullptr;     // 空树，直接返回
    }
    if(root->data == target){   // 找到了要删除的节点
        if(root->left == nullptr && root->right == nullptr){   // 情况一：被删除节点没有子节点
            delete root;
            return nullptr;
        }
        if(root->left == nullptr){    // 情况二：被删除节点只有一个右子节点
            TreeNode* tmp = root->right;
            delete root;
            return tmp;
        }
        if(root->right == nullptr){   // 情况二：被删除节点只有一个左子节点
            TreeNode* tmp = root->left;
            delete root;
            return tmp;
        }
        // 情况三：被删除节点有两个子节点
        TreeNode* minNode = root->right;   // 找到右子树中最小的节点
        while(minNode->left != nullptr){
            minNode = minNode->left;
        }
        root->data = minNode->data;        // 将最小值替换到被删除节点
        root->right = deleteNode(root->right, minNode->data);    // 删除右子树中的最小值
    }else if(root->data > target){
        root->left = deleteNode(root->left, target);    // 左子树中删除
    }else{
        root->right = deleteNode(root->right, target);  // 右子树中删除
    }
    return root;
}

5. 示例说明

示例1

输入数据：1 2 4 -1 -1 -1 3 -1 5 -1 -1

其中-1代表空节点，这个输入数据代表的二叉树如下所示：

graph LR
1((1)) --> 2((2))
1 --> 3((3))
2 --> 4((4))
3 --> 5((5))

输出数据：

前序遍历结果为：1 2 4 3 5

中序遍历结果为：4 2 1 3 5

后序遍历结果为：4 2 5 3 1

示例2

输入数据：5 3 2 -1 -1 4 -1 -1 7 6 -1 -1 8 -1 -1

其中-1代表空节点，这个输入数据代表的二叉树如下所示：

graph LR
5((5)) --> 3((3))
5 --> 7((7))
3 --> 2((2))
3 --> 4((4))
7 --> 6((6))
7 --> 8((8))

输出数据：

前序遍历结果为：5 3 2 4 7 6 8

中序遍历结果为：2 3 4 5 6 7 8

后序遍历结果为：2 4 3 6 8 7 5

以上就是C++二叉树的建立与基本操作的完整攻略。如果还有疑问，请留言询问。