Future Design

Download 1,46 Mb.

bet	2/2
Sana	16.06.2022
Hajmi	1,46 Mb.
	#677142

1 2

Bog'liq
RUFAT 5

C++ Code for searching and insertion in Binary Search Tree
// if root is equals to target, return true

if x.right ≠ NIL then
return Tree-Minimum(x.right)
end if
y := x.parent
while y ≠ NIL and x = y.right then
x := y
y := y.parent
repeat return y
Tree-Predecessor(x)
if x.left ≠ NIL then
return Tree-Maximum(x.left)
end if
y := x.parent
while y ≠ NIL and x = y.left then
x := y
y := y.
repeat
return y

C++ Code for searching and insertion in Binary Search Tree

#include

using namespace std;

// class representing node of a binary tree

class Node {

public:

int data;

Node *left;

Node *right;

Node(int d) {

data = d; left = right = NULL; } }; Node* insertToBST(Node root, Node node) { // if root is null, then make root as node and return if (root == NULL) { root = node; return root; } // if node's value is less than root, insert it to left subtree if (node->data < root->data) { root->left = insertToBST(root->left, node); } // else insert it to right subtree else {

root->right = insertToBST(root->right, node); } // return the updated root return root; } Node* insert(Node root, int value) { // allocate memory for new node Node node = new Node(value); // insert the new node to tree return insertToBST(root, node); } bool search(Node *root, int value) { // if root is null, return false if (root == NULL) { return false; }

// if root is equals to target, return true

if (root->data == value) {

return true;

}

// else if val is less than root, search in left subtree

else if (value < root->data) {

return search(root->left, value);

}

// else search in right subtree

else {

return search(root->right, value);

}

int main() {

// Example

Node *root = NULL;

root = insert(root, 10);

root = insert(root, 15);

if (search(root, 5)) {

cout<<"true"<<endl;

} else {

cout<<"false"<<endl; } root = insert(root, 5); root = insert(root, 18); if (search(root, 5)) { cout<<"true"<<endl; } else { cout<<"false"<<endl; } root = insert(root, 12); if (search(root, 10)) { cout<<"true"<<endl; } else { cout<<"false"<<endl; } return 0; }

Broadly speaking, nodes with children are harder to delete. As with all binary trees, a node’s inorder successor is its right subtree’s leftmost child, and a node’s inorder predecessor is the left subtree’s rightmost child. In either case, this node will have zero or one child. Delete it according to one of the two simpler cases above.

Thank You!

Download 1,46 Mb.

Do'stlaringiz bilan baham: