﻿

# Untitled

a guest
Dec 14th, 2019
118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2. // A utility function to search a given key in BST
3. public Node search(Node root, int key)
4. {
5. // Base Cases: root is null or key is present at root
6. if (root==null || root.key==key)
7. return root;
8.
9. // val is greater than root's key
10. if (root.key > key)
11. return search(root.left, key);
12.
13. // val is less than root's key
14. return search(root.right, key);
15. }
16.
17. Illustration to search 6 in below tree:
18. 1. Start from root.
19. 2. Compare the inserting element with root, if less than root, then recurse for left, else recurse for right.
20. 3. If element to search is found anywhere, return true, else return false.
21. bstsearch
22.
23.
24. Insertion of a key
25. A new key is always inserted at leaf. We start searching a key from root till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
26.
27. 100 100
28. / \ Insert 40 / \
29. 20 500 ---------> 20 500
30. / \ / \
31. 10 30 10 30
32. \
33. 40
34. filter_none
35. edit
36. play_arrow
37.
38. brightness_4
39. // Java program to demonstrate insert operation in binary search tree
40. class BinarySearchTree {
41.
42. /* Class containing left and right child of current node and key value*/
43. class Node {
44. int key;
45. Node left, right;
46.
47. public Node(int item) {
48. key = item;
49. left = right = null;
50. }
51. }
52.
53. // Root of BST
54. Node root;
55.
56. // Constructor
57. BinarySearchTree() {
58. root = null;
59. }
60.
61. // This method mainly calls insertRec()
62. void insert(int key) {
63. root = insertRec(root, key);
64. }
65.
66. /* A recursive function to insert a new key in BST */
67. Node insertRec(Node root, int key) {
68.
69. /* If the tree is empty, return a new node */
70. if (root == null) {
71. root = new Node(key);
72. return root;
73. }
74.
75. /* Otherwise, recur down the tree */
76. if (key < root.key)
77. root.left = insertRec(root.left, key);
78. else if (key > root.key)
79. root.right = insertRec(root.right, key);
80.
81. /* return the (unchanged) node pointer */
82. return root;
83. }
84.
85. // This method mainly calls InorderRec()
86. void inorder() {
87. inorderRec(root);
88. }
89.
90. // A utility function to do inorder traversal of BST
91. void inorderRec(Node root) {
92. if (root != null) {
93. inorderRec(root.left);
94. System.out.println(root.key);
95. inorderRec(root.right);
96. }
97. }
98.
99. // Driver Program to test above functions
100. public static void main(String[] args) {
101. BinarySearchTree tree = new BinarySearchTree();
102.
103. /* Let us create following BST
104. 50
105. / \
106. 30 70
107. / \ / \
108. 20 40 60 80 */
109. tree.insert(50);
110. tree.insert(30);
111. tree.insert(20);
112. tree.insert(40);
113. tree.insert(70);
114. tree.insert(60);
115. tree.insert(80);
116.
117. // print inorder traversal of the BST
118. tree.inorder();
119. }
120. }
RAW Paste Data