Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
165
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.37 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement