CSE Helper
Powered By Dream Dragon Creation
Binary Search Tree
There is some additional function for Binary Tree to implement binary search tree.
The search tree data structure supports many dynamic-set operations, including
SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and
DELETE.
Insertion
To insert a new value v into a binary search tree T, we use the procedure TREE-INSERT. The procedure takes a node Z for which z.key = v, z.lefi = NIL, and z.right = NIL. It modifies T and some of the attributes of z in such a way that it inserts z into an appropriate position in the tree.
TREE-lNsERT(T. z)
l y = NIL
2 x = T.r00t
3 while x != NIL
4 y = x
5 if z.key < x.key
6 x = x.left
7 else x = x.right
8 z.p = y
9 if y == NIL
10 T. root = z // tree T was empty
11 else if z.key < y.key
Binary Search Tree Example Code in C++
1 int BinarySearchTree::add_value(Node* root, int newvalue){
2 if (root == NULL){
3 //cout << " \n root is null and add " << newvalue << endl;
4 Node* newNode = new Node;
5 newNode->leftChild = NULL;
6 newNode->rightChild = NULL;
7 newNode->Value = newvalue;
8 this->Root = newNode;
9 return 1;
10 }
11 if (root->Value >= newvalue){
12 if (root->leftChild == NULL){
13 Node* newNode = new Node;
14 newNode->Value = newvalue;
15 newNode->leftChild = NULL;
16 newNode->rightChild = NULL;
17 root->leftChild = newNode;
18 return 1;
19 }
20 return add_value(root->leftChild, newvalue);
21 }else{
22 if (root->rightChild == NULL){
23 //cout << " add value > root (right node NULL : " << newvalue << endl;
24 Node* newNode = new Node;
25 newNode->leftChild = NULL;
26 newNode->rightChild = NULL;
27 newNode->Value = newvalue;
28 root->rightChild = newNode;
29 return 1;
30 }
31 return add_value(root->rightChild, newvalue);
32 }
33 }
34 int BinarySearchTree::delete_value(Node* root, int value){
35 bool found = false;
36 if (root == NULL){
37 return 0;
38 }
39 Node* currentNode = NULL;
40 Node* parentNode = NULL;
41 currentNode = root;
42 while (currentNode != NULL){
43 if (currentNode->Value == value){
44 found = true;
45 break;
46 }else{
47 parentNode = currentNode;
48 if (value > currentNode->Value){
49 currentNode = currentNode->rightChild;
50 }else {
51 currentNode = currentNode->leftChild;
52 }
53 }
54 }
55 if (!found){
56 return 0;
57 }
58 if ((currentNode->leftChild == NULL && currentNode->rightChild != NULL) || (currentNode->leftChild != NULL
59 && currentNode->rightChild == NULL)){
60 if (currentNode->leftChild == NULL && currentNode->rightChild != NULL){
61 if (parentNode->leftChild == currentNode){
62 parentNode->leftChild = currentNode->rightChild;
63 delete currentNode;
64 }else{
65 parentNode->rightChild = currentNode->rightChild;
66 delete currentNode;
67 }
68 }else{
69 if (parentNode->leftChild == currentNode){
70 parentNode->leftChild = currentNode->leftChild;
71 delete currentNode;
72 }else{
73 parentNode->rightChild = currentNode->leftChild;
74 delete currentNode;
75 }
76 }
77 return 0;
78 }
79 if (currentNode->leftChild == NULL && currentNode->rightChild == NULL){
80 if (parentNode->leftChild == currentNode) parentNode->leftChild = NULL;
81 else parentNode->rightChild = NULL;
82 if (currentNode->index == 0){
83 currentNode = NULL;
84 return 1;
85 }
86 delete currentNode;
87 return 1;
88 }
89 if (currentNode->leftChild != NULL && currentNode->rightChild != NULL){
90 Node* checkNode;
91 checkNode = currentNode->rightChild;
92 if ((checkNode->leftChild == NULL) && (checkNode->rightChild == NULL)){
93 currentNode = checkNode;
94 delete checkNode;
95 currentNode->rightChild = NULL;
96 }else{
97 if ((currentNode->rightChild)->leftChild != NULL){
98 Node* leftCurrentNode;
99 Node* leftCurrentParent;
100 leftCurrentParent = currentNode->rightChild;
101 leftCurrentNode = (currentNode->rightChild)->leftChild;
102 while (leftCurrentNode->leftChild != NULL)
103 { leftCurrentParent = leftCurrentNode;
104 leftCurrentNode = leftCurrentNode->leftChild;
105 }
106 currentNode->Value = leftCurrentNode->Value;
107 delete leftCurrentNode;
108 leftCurrentParent->leftChild = NULL;
109 }else{
110 Node* tmp;
111 tmp = currentNode->rightChild;
112 currentNode->Value = tmp->Value;
113 currentNode->rightChild = tmp->rightChild;
114 delete tmp;
115 }
116 }
117 return 1;
118 }
119 return 1;
120 }
121 Node* BinarySearchTree::search_value(Node* root, int value){
122 Node *temp = root;
123 while (temp != NULL){
124 if (temp->Value == value){
125 return temp;
126 }else{
127 if (temp->Value >= value){
128 temp = temp->leftChild;
129 }else{
130 temp = temp->rightChild;
131 }
132 }
133 }
134 return NULL;
135 }
136 void BinarySearchTree::print_tree(Node* root){
137 if (root){
138 print_tree(root->leftChild);
139 cout << root->Value << " ";
140 print_tree(root->rightChild);
i }
141 }