1. // Binary Search Tree - Implemenation in C++
2. // Simple program to create a BST of integers and search an element in it
3. #include<iostream>
4. using namespace std;
5. //Definition of Node for Binary search tree
6. struct BstNode {
7.         int data;
8.         BstNode* left;
9.         BstNode* right;
10. };
11.  
12. // Function to create a new Node in heap
13. BstNode* GetNewNode(int data) {
14.         BstNode* newNode = new BstNode();
15.         newNode->data = data;
16.         newNode->left = newNode->right = NULL;
17.         return newNode;
18. }
19.  
20. // To insert data in BST, returns address of root node
21. BstNode* Insert(BstNode* root, int data) {
22.         if (root == NULL) { // empty tree
23.                 root = GetNewNode(data);
24.         }
25.         // if data to be inserted is lesser, insert in left subtree.
26.         else if (data <= root->data) {
27.                 root->left = Insert(root->left, data);
28.         }
29.         // else, insert in right subtree.
30.         else {
31.                 root->right = Insert(root->right, data);
32.         }
33.         return root;
34. }
35. //To search an element in BST, returns true if element is found
36. bool Search(BstNode* root, int data) {
37.         if (root == NULL) {
38.                 return false;
39.         }
40.         else if (root->data == data) {
41.                 return true;
42.         }
43.         else if (data <= root->data) {
44.                 return Search(root->left, data);
45.         }
46.         else {
47.                 return Search(root->right, data);
48.         }
49. }
50. void inorder(BstNode* root) {
51.         if (root != NULL) { // empty tree
52.                 inorder(root->left);
53.                 cout << root->data << "  ";
54.                 inorder(root->right);
55.         }
56. }
57.  
58. int maxrek(BstNode*root)
59. {
60.         if (root->right == NULL)
61.                 return root->data;
62.         else
63.                 maxrek(root->right);
64. }
65.  
66. int minrek(BstNode* root)
67. {
68.         if (root->left == NULL)
69.                 return(root->data);
70.         else
71.                 minrek(root->left);
72. }
73.  
74. int max(BstNode* root)
75. {
76.         BstNode* temp = root;
77.         while (temp->right != NULL)
78.                 temp = temp->right;
79.         return(temp->data);
80. }
81.  
82. int min(BstNode* root)
83. {
84.         BstNode* temp = root;
85.         while (temp->left != NULL)
86.                 temp = temp->left;
87.         return(temp->data);
88. }
89.  
90. BstNode* usun(BstNode* root) {
91.         if (root == NULL)
92.                 return NULL;
93.         if (root->left == NULL&&root->right == NULL)
94.         {
95.                 delete root;
96.                 return NULL;
97.         }
98.  
99.         root->left = usun(root->left);
100.         root->right = usun(root->right);
101.  
102.         return root;
103. }
104.  
105.  
106.  
107. int main() {
108.         BstNode* root = NULL;  // Creating an empty tree
109.                                                    /*Code to test the logic*/
110.         root = Insert(root, 15);
111.         root = Insert(root, 10);
112.         root = Insert(root, 20);
113.         root = Insert(root, 25);
114.         root = Insert(root, 8);
115.         root = Insert(root, 12);
116.         // Ask user to enter a number.  
117.         inorder(root);
118.         cout << endl;
119.         root = usun(root);
120.         inorder(root);
121.  
122.         system("pause");
123.         return 0;
124. }
125.  
126. //!!!!!!!!!!!!!!!!!!!!!!!
127. //zrob poprzednik nastepnik i rotacje +
128. //implementacje drzewa w klasie i ogarnij drzewo AVL
129. //usuwanie dowolnego wezla z drzewa BST!!!!