fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class BST
  6. {
  7. 	class node
  8. 	{
  9. 		int data;
  10. 		node left;
  11. 		node right;
  12. 	public node(int c)
  13. 	{
  14. 		data=c;
  15. 		left=null;
  16. 		right=null;
  17. 	}
  18. 	}
  19. public BST()
  20. {
  21. 	root=null;
  22. }
  23. node root;
  24. void insert1(int d)
  25. {
  26. 	if (root==null) {root=new node(d);return;}
  27. 	node curr=root,parent=root;
  28. 	while(curr!=null)
  29. 	{
  30. 		parent=curr;
  31. 		if (d>curr.data) curr=curr.right;
  32. 		else curr=curr.left;
  33. 	}
  34. 	if(d>parent.data) parent.right=new node(d);
  35. 	else parent.left=new node(d);
  36. }
  37. void insert2(int d)
  38. {
  39. 	root=insertR(root,d);
  40. }
  41. node insertR(node r,int d)
  42. {
  43. 	if (r==null){r=new node(d);return r;}
  44. 	else if(d>r.data) r.right=insertR(r.right,d);
  45. 	else r.left=insertR(r.left,d);
  46. 	return r;
  47. }
  48. boolean search(int d)
  49. {
  50. 	node curr=root;
  51. 	while(curr!=null)
  52. 	{
  53. 		if(d==curr.data) return true;
  54. 		else if(d>curr.data) curr=curr.right;
  55. 		else curr=curr.left;
  56. 	}
  57. 	return false;
  58. }
  59.  
  60. void print()
  61. {
  62. 	inorder(root);
  63. 	System.out.println();
  64. 	preorder(root);
  65. 	System.out.println();
  66. 	postorder(root);
  67. 	System.out.println();
  68. 	DFS();
  69. 	System.out.println();
  70. 	BFS();
  71. 	System.out.println();
  72.  
  73. }
  74. void inorder(node r)
  75. {
  76. 	if (r!=null)
  77. 	{
  78. 		inorder(r.left);
  79. 		System.out.print(r.data+" ");
  80. 		inorder(r.right);
  81. 	}
  82. }
  83. void preorder(node r)
  84. {
  85. 	if (r!=null)
  86. 	{
  87. 		System.out.print(r.data+" ");
  88. 		preorder(r.left);
  89. 		preorder(r.right);
  90. 	}
  91. }
  92. void postorder(node r)
  93. {
  94. 	if (r!=null)
  95. 	{
  96. 		postorder(r.left);
  97. 		postorder(r.right);
  98. 		System.out.print(r.data+" ");
  99. 	}
  100. }
  101. void DFS()
  102. {
  103. 	Stack<node> S=new Stack<node>();
  104. 	if(root==null) return;
  105. 	S.push(root);
  106. 	while(S.size()!=0)
  107. 	{
  108. 		node n=S.pop();
  109. 		System.out.print(n.data+" ");
  110. 		if(n.right!=null) S.push(n.right);
  111. 		if(n.left!=null) S.push(n.left);
  112. 	} 
  113. }
  114. void BFS()
  115. {
  116. 	Queue<node> Q=new LinkedList<node>();
  117. 	if(root==null) return;
  118. 	Q.add(root);
  119. 	while(Q.size()!=0)
  120. 	{
  121. 		node n=Q.remove();
  122. 		System.out.print(n.data+" ");
  123. 		if(n.left!=null) Q.add(n.left);
  124. 		if(n.right!=null) Q.add(n.right);
  125. 	} 
  126. }
  127.  
  128. void delete(int d) 
  129. { 
  130. 	root = deleteR(root, d); 
  131. }
  132.  
  133. node deleteR(node r, int d)
  134.     {
  135.         if (r == null) return null;
  136. 		if (d < r.data)
  137.             r.left = deleteR(r.left, d);
  138.         else if (d > r.data)
  139.             r.right = deleteR(r.right, d);
  140.         else {
  141.             if (r.left == null)
  142.                 return r.right;
  143.             else if (r.right == null)
  144.                 return r.left;
  145.  
  146.             r.data = min(r.right);
  147.             r.right = deleteR(r.right, r.data);
  148.     		 }
  149.  
  150.         return r;
  151.     }
  152.  
  153.     int min(node r)
  154.     {
  155.         int m = r.data;
  156.         while (r.left != null)
  157.         {
  158.             m = r.left.data;
  159.             r = r.left;
  160.         }
  161.         return m;
  162.     }
  163. }
  164. class Ideone
  165. {
  166. 	public static void main (String[] args) throws java.lang.Exception
  167. 	{
  168. 	BST b=new BST();
  169. 	b.insert1(4);
  170. 	b.insert1(5);
  171. 	b.insert2(3);
  172. 	b.insert2(1);
  173. 	b.insert2(2);
  174. 	b.insert1(7);
  175. 	b.insert1(6);
  176. 	b.print();
  177. 	b.delete(4);
  178. 	b.print();
  179. 	System.out.println(b.search(3));
  180. 	}
  181. }
Success #stdin #stdout 0.13s 48120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5 6 7 
4 3 1 2 5 7 6 
2 1 3 6 7 5 4 
4 3 1 2 5 7 6 
4 3 5 1 7 2 6 
1 2 3 5 6 7 
5 3 1 2 7 6 
2 1 3 6 7 5 
5 3 1 2 7 6 
5 3 7 1 6 2 
true
https://ideone.com/mi8DeC
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!