二叉树--二叉搜索树

admin

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdlib>
using namespace std;

// 二叉树节点结构体
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = newNode->right = nullptr;
    return newNode;
}

// 插入节点（二叉搜索树方式）
TreeNode* insert(TreeNode* root, int data) {
    // 如果树为空，创建新节点作为根节点
    if (root == nullptr) {
        return createNode(data);
    }
    
    // 否则递归插入到左子树或右子树
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    
    // 不插入重复值
    return root;
}

// 前序遍历
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 << " ";       // 访问根节点
}

// 查找节点
TreeNode* search(TreeNode* root, int key) {
    // 树为空或找到节点
    if (root == nullptr || root->data == key) {
        return root;
    }
    
    // 关键字小于根节点值，在左子树中查找
    if (key < root->data) {
        return search(root->left, key);
    }
    
    // 否则在右子树中查找
    return search(root->right, key);
}

// 找到以root为根的树中的最小值节点
TreeNode* findMin(TreeNode* root) {
    TreeNode* current = root;
    // 循环找到最左节点
    while (current && current->left != nullptr) {
        current = current->left;
    }
    return current;
}

// 删除节点
TreeNode* deleteNode(TreeNode* root, int key) {
    // 树为空
    if (root == nullptr) return root;
    
    // 查找要删除的节点
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        // 找到要删除的节点
        
        // 情况1：叶子节点或只有一个子节点
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        
        // 情况2：有两个子节点
        // 找到中序后继（右子树的最小值）
        TreeNode* temp = findMin(root->right);
        
        // 复制后继节点的值到当前节点
        root->data = temp->data;
        
        // 删除后继节点
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// 计算树的高度
int getHeight(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    
    // 递归计算左右子树高度
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    
    // 返回较大的高度加1（当前节点）
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 销毁树
void destroyTree(TreeNode* root) {
    if (root == nullptr) return;
    
    // 先销毁左右子树
    destroyTree(root->left);
    destroyTree(root->right);
    
    // 再销毁当前节点
    free(root);
}

// 主函数演示
int main() {
    TreeNode* root = nullptr;
    
    // 插入节点
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);
    
    cout << "二叉树操作演示:\n" << endl;
    
    cout << "前序遍历: ";
    preorderTraversal(root);
    cout << endl;
    
    cout << "中序遍历: ";
    inorderTraversal(root);
    cout << endl;
    
    cout << "后序遍历: ";
    postorderTraversal(root);
    cout << endl;
    
    int key = 40;
    TreeNode* found = search(root, key);
    if (found != nullptr) {
        cout << "\n找到节点: " << found->data << endl;
    } else {
        cout << "\n未找到节点: " << key << endl;
    }
    
    cout << "\n树的高度: " << getHeight(root) << endl;
    
    // 删除节点
    key = 30;
    root = deleteNode(root, key);
    cout << "\n删除节点 " << key << " 后的中序遍历: ";
    inorderTraversal(root);
    cout << endl;
    
    // 销毁树
    destroyTree(root);
    root = nullptr;
    cout << "\n树已销毁" << endl;
    
    return 0;
}

admin

可以使用 C++ 的new操作符来替代 C 语言的malloc函数，这样更符合 C++ 的编程风格。使用new不仅会分配内存，还会自动调用结构体的构造函数（虽然在这个例子中结构体没有显式定义构造函数，但依然是更合适的 C++ 做法）。
将创建节点的代码修改为new版本如下：

[C++] 纯文本查看 复制代码

// 创建新节点（使用new操作符）
TreeNode* createNode(int data) {
    TreeNode* newNode = new TreeNode;  // 使用new分配内存
    newNode->data = data;
    newNode->left = newNode->right = nullptr;
    return newNode;
}

[C++] 纯文本查看 复制代码

// 销毁树（使用delete操作符）
void destroyTree(TreeNode* root) {
    if (root == nullptr) return;
    
    // 先销毁左右子树
    destroyTree(root->left);
    destroyTree(root->right);
    
    // 再销毁当前节点（使用delete）
    delete root;
}