C++ 实现树数据结构及基本操作

#include using namespace std;

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

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

};

class Tree { public: TreeNode* root;

Tree() : root(nullptr) {}

void insert(int val) {
    root = insertNode(root, val);
}

TreeNode* insertNode(TreeNode* node, int val) {
    if (node == nullptr) {
        return new TreeNode(val);
    }

    if (val < node->val) {
        node->left = insertNode(node->left, val);
    } else {
        node->right = insertNode(node->right, val);
    }

    return node;
}

bool search(int val) {
    return searchNode(root, val);
}

bool searchNode(TreeNode* node, int val) {
    if (node == nullptr) {
        return false;
    }

    if (val == node->val) {
        return true;
    } else if (val < node->val) {
        return searchNode(node->left, val);
    } else {
        return searchNode(node->right, val);
    }
}

void remove(int val) {
    root = removeNode(root, val);
}

TreeNode* removeNode(TreeNode* node, int val) {
    if (node == nullptr) {
        return nullptr;
    }

    if (val == node->val) {
        if (node->left == nullptr && node->right == nullptr) {
            delete node;
            return nullptr;
        } else if (node->left == nullptr) {
            TreeNode* temp = node->right;
            delete node;
            return temp;
        } else if (node->right == nullptr) {
            TreeNode* temp = node->left;
            delete node;
            return temp;
        } else {
            TreeNode* minNode = findMinNode(node->right);
            node->val = minNode->val;
            node->right = removeNode(node->right, minNode->val);
        }
    } else if (val < node->val) {
        node->left = removeNode(node->left, val);
    } else {
        node->right = removeNode(node->right, val);
    }

    return node;
}

TreeNode* findMinNode(TreeNode* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

};

int main() { Tree tree; tree.insert(5); tree.insert(3); tree.insert(7); tree.insert(2); tree.insert(4);

cout << "Search 4: " << (tree.search(4) ? "Found" : "Not found") << endl;

tree.remove(3);
cout << "Search 3: " << (tree.search(3) ? "Found" : "Not found") << endl;

return 0;

}

上述代码定义了一个树的数据结构，并实现了插入、查找和删除操作。你可以根据需要自行调用这些操作来操作树。