Untitled
unknown
c_cpp
a year ago
4.2 kB
3
Indexable
#include <iostream> #include <algorithm> using namespace std; class TreeNode { public: int key; TreeNode *left; TreeNode *right; TreeNode(int val) : key(val), left(nullptr), right(nullptr) {} }; class BST { private: TreeNode *root; TreeNode *insert(TreeNode *root, int key) { if (root == nullptr) { return new TreeNode(key); } if (key < root->key) { root->left = insert(root->left, key); } else if (key > root->key) { root->right = insert(root->right, key); } return root; } TreeNode *deleteNode(TreeNode *root, int key) { if (root == nullptr) { return root; } if (key < root->key) { root->left = deleteNode(root->left, key); } else if (key > root->key) { root->right = deleteNode(root->right, key); } else { if (root->left == nullptr) { TreeNode *temp = root->right; delete root; return temp; } else if (root->right == nullptr) { TreeNode *temp = root->left; delete root; return temp; } root->key = getMinValue(root->right); root->right = deleteNode(root->right, root->key); } return root; } int getMinValue(TreeNode *root) { while (root->left != nullptr) { root = root->left; } return root->key; } void inorderTraversal(TreeNode *root) { if (root != nullptr) { inorderTraversal(root->left); cout << root->key << " "; inorderTraversal(root->right); } } void preorderTraversal(TreeNode *root) { if (root != nullptr) { cout << root->key << " "; preorderTraversal(root->left); preorderTraversal(root->right); } } void postorderTraversal(TreeNode *root) { if (root != nullptr) { postorderTraversal(root->left); postorderTraversal(root->right); cout << root->key << " "; } } int maxDepth(TreeNode *root) { if (root == nullptr) { return 0; } int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return 1 + max(leftDepth, rightDepth); } int minDepth(TreeNode *root) { if (root == nullptr) { return 0; } int leftDepth = minDepth(root->left); int rightDepth = minDepth(root->right); return 1 + min(leftDepth, rightDepth); } public: BST() : root(nullptr) {} void insert(int key) { root = insert(root, key); } void deleteNode(int key) { root = deleteNode(root, key); } void inorderTraversal() { cout << "In-order Traversal: "; inorderTraversal(root); cout << endl; } void preorderTraversal() { cout << "Pre-order Traversal: "; preorderTraversal(root); cout << endl; } void postorderTraversal() { cout << "Post-order Traversal: "; postorderTraversal(root); cout << endl; } int getMaxDepth() { return maxDepth(root); } int getMinDepth() { return minDepth(root); } }; int main() { BST bst; bst.insert(50); bst.insert(30); bst.insert(70); bst.insert(20); bst.insert(40); bst.insert(60); bst.insert(80); bst.insert(10); bst.inorderTraversal(); bst.preorderTraversal(); bst.postorderTraversal(); cout << "Maximum Depth: " << bst.getMaxDepth() << endl; cout << "Minimum Depth: " << bst.getMinDepth() << endl; cout << " " << endl; bst.deleteNode(10); cout << "Traversal after deleting 10: " << endl; bst.inorderTraversal(); bst.preorderTraversal(); bst.postorderTraversal(); return 0; }
Editor is loading...
Leave a Comment