fork download
copy 
  1. class BinaryTree{
  2.     public static void main(String[] a){
  3. 	System.out.println(new BT().Start());
  4.     }
  5. }
  6.  
  7.  
  8. // This class invokes the methods to create a tree,
  9. // insert, delete and serach for  elements on it
  10. class BT {
  11.  
  12.     public int Start(){
  13. 	Tree root ;
  14. 	boolean ntb ;
  15. 	int nti ;
  16.  
  17. 	root = new Tree();
  18. 	ntb = root.Init(16);
  19. 	ntb = root.Print();
  20. 	System.out.println(100000000);
  21. 	ntb = root.Insert(8) ;
  22. 	ntb = root.Print();
  23. 	ntb = root.Insert(24) ;
  24. 	ntb = root.Insert(4) ;
  25. 	ntb = root.Insert(12) ;
  26. 	ntb = root.Insert(20) ;
  27. 	ntb = root.Insert(28) ;
  28. 	ntb = root.Insert(14) ;
  29. 	ntb = root.Print();
  30. 	System.out.println(root.Search(24));
  31. 	System.out.println(root.Search(12));
  32. 	System.out.println(root.Search(16));
  33. 	System.out.println(root.Search(50));
  34. 	System.out.println(root.Search(12));
  35. 	ntb = root.Delete(12);
  36. 	ntb = root.Print();
  37. 	System.out.println(root.Search(12));
  38.  
  39. 	return 0 ;
  40.     }
  41.  
  42. }
  43.  
  44. class Tree{
  45.     Tree left ;
  46.     Tree right;
  47.     int key ;
  48.     boolean has_left ;
  49.     boolean has_right ;
  50.     Tree my_null ;
  51.  
  52.     // Initialize a node with a key value and no children
  53.     public boolean Init(int v_key){
  54. 	key = v_key ;
  55. 	has_left = false ;
  56. 	has_right = false ;
  57. 	return true ;
  58.     }
  59.  
  60.     // Update the right child with rn
  61.     public boolean SetRight(Tree rn){
  62. 	right = rn ;
  63. 	return true ;
  64.     }
  65.  
  66.     // Update the left child with ln
  67.     public boolean SetLeft(Tree ln){
  68. 	left = ln ;
  69. 	return true ;
  70.     }
  71.  
  72.     public Tree GetRight(){
  73. 	return right ;
  74.     }
  75.  
  76.     public Tree GetLeft(){
  77. 	return left;
  78.     }
  79.  
  80.     public int GetKey(){
  81. 	return key ;
  82.     }
  83.  
  84.     public boolean SetKey(int v_key){
  85. 	key = v_key ;
  86. 	return true ;
  87.     }
  88.  
  89.     public boolean GetHas_Right(){
  90. 	return has_right ;
  91.     }
  92.  
  93.     public boolean GetHas_Left(){
  94. 	return has_left ;
  95.     }
  96.  
  97.     public boolean SetHas_Left(boolean val){
  98. 	 has_left = val ;
  99. 	 return true ;
  100.     }
  101.  
  102.     public boolean SetHas_Right(boolean val){
  103. 	 has_right = val ;
  104. 	 return true ;
  105.     }
  106.  
  107.     // This method compares two integers and
  108.     // returns true if they are equal and false
  109.     // otherwise
  110.     public boolean Compare(int num1 , int num2){
  111. 	boolean ntb ;
  112. 	int nti ;
  113.  
  114. 	ntb = false ;
  115. 	nti = num2 + 1 ;
  116. 	if (num1 < num2) ntb = false ;
  117. 	else if (!(num1 < nti)) ntb = false ;
  118. 	else ntb = true ;
  119. 	return ntb ;
  120.     }
  121.  
  122.  
  123.     // Insert a new element in the tree
  124.     public boolean Insert(int v_key){
  125. 	Tree new_node ;
  126. 	boolean ntb ;
  127. 	boolean cont ;
  128. 	int key_aux ;
  129. 	Tree current_node ;
  130.  
  131. 	new_node = new Tree();
  132. 	ntb = new_node.Init(v_key) ;
  133. 	current_node = this ;
  134. 	cont = true ;
  135. 	while (cont){
  136. 	    key_aux = current_node.GetKey();
  137. 	    if (v_key < key_aux){
  138. 		if (current_node.GetHas_Left())
  139. 		    current_node = current_node.GetLeft() ;
  140. 		else {
  141. 		    cont = false ;
  142. 		    ntb = current_node.SetHas_Left(true);
  143. 		    ntb = current_node.SetLeft(new_node);
  144. 		}
  145. 	    }
  146. 	    else{
  147. 		if (current_node.GetHas_Right())
  148. 		    current_node = current_node.GetRight() ;
  149. 		else {
  150. 		    cont = false ;
  151. 		    ntb = current_node.SetHas_Right(true);
  152. 		    ntb = current_node.SetRight(new_node);
  153. 		}
  154. 	    }
  155. 	}
  156. 	return true ;
  157.     }
  158.  
  159.  
  160.     // Delete an element from the tree
  161.     public boolean Delete(int v_key){
  162. 	Tree current_node ;
  163. 	Tree parent_node ;
  164. 	boolean cont ;
  165. 	boolean found ;
  166. 	boolean is_root ;
  167. 	int key_aux ;
  168. 	boolean ntb ;
  169.  
  170. 	current_node = this ;
  171. 	parent_node = this ;
  172. 	cont = true ;
  173. 	found = false ;
  174. 	is_root = true ;
  175. 	while (cont){
  176. 	    key_aux = current_node.GetKey();
  177. 	    if (v_key < key_aux)
  178. 		if (current_node.GetHas_Left()){
  179. 		    parent_node = current_node ;
  180. 		    current_node = current_node.GetLeft() ;
  181. 		}
  182. 		else cont = false ;
  183. 	    else 
  184. 		if (key_aux < v_key)
  185. 		    if (current_node.GetHas_Right()){
  186. 			parent_node = current_node ;
  187. 			current_node = current_node.GetRight() ;
  188. 		    }
  189. 		    else cont = false ;
  190. 		else { 
  191. 		    if (is_root) 
  192. 			if ((!(current_node.GetHas_Right())) && 
  193. 			    (!(current_node.GetHas_Left())) )
  194. 			    ntb = true ;
  195. 			else 
  196. 			    ntb = this.Remove(parent_node,current_node); 
  197. 		    else ntb = this.Remove(parent_node,current_node);
  198. 		    found = true ;
  199. 		    cont = false ;
  200. 		}
  201. 	    is_root = false ;
  202. 	}
  203. 	return found ;
  204.     }
  205.  
  206.  
  207.     // Check if the element to be removed will use the
  208.     // righ or left subtree if one exists
  209.     public boolean Remove(Tree p_node, Tree c_node){
  210. 	boolean ntb ;
  211. 	int auxkey1 ;
  212. 	int auxkey2 ;
  213.  
  214. 	if (c_node.GetHas_Left()) 
  215. 	    ntb = this.RemoveLeft(p_node,c_node) ;
  216. 	else 
  217. 	    if (c_node.GetHas_Right())
  218. 		ntb = this.RemoveRight(p_node,c_node) ;
  219. 	    else {
  220. 		auxkey1 = c_node.GetKey();
  221. 		//auxtree01 = p_node.GetLeft() ;
  222. 		//auxkey2 = auxtree01.GetKey() ;
  223. 		auxkey2 = (p_node.GetLeft()).GetKey() ;
  224. 		if (this.Compare(auxkey1,auxkey2)) {
  225. 		    ntb = p_node.SetLeft(my_null);
  226. 		    ntb = p_node.SetHas_Left(false);
  227. 		}
  228. 		else {
  229. 		    ntb = p_node.SetRight(my_null);
  230. 		    ntb = p_node.SetHas_Right(false);
  231. 		}
  232. 	    }
  233. 	return true ;
  234.     }
  235.  
  236.  
  237.     // Copy the child key to the parent until a leaf is
  238.     // found and remove the leaf. This is done with the
  239.     // right subtree
  240.     public boolean RemoveRight(Tree p_node, Tree c_node){
  241. 	boolean ntb ;
  242.  
  243. 	while (c_node.GetHas_Right()){
  244. 	    //auxtree01 = c_node.GetRight() ;
  245. 	    //auxint02 = auxtree01.GetKey();
  246. 	    //ntb = c_node.SetKey(auxint02);
  247. 	    ntb = c_node.SetKey((c_node.GetRight()).GetKey());
  248. 	    p_node = c_node ;
  249. 	    c_node = c_node.GetRight() ;
  250. 	}
  251. 	ntb = p_node.SetRight(my_null);
  252. 	ntb = p_node.SetHas_Right(false);
  253. 	return true ;
  254.     }
  255.  
  256.  
  257.     // Copy the child key to the parent until a leaf is
  258.     // found and remove the leaf. This is done with the
  259.     // left subtree
  260.     public boolean RemoveLeft(Tree p_node, Tree c_node){
  261. 	boolean ntb ;
  262.  
  263. 	while (c_node.GetHas_Left()){
  264. 	    //auxtree01 = c_node.GetLeft() ;
  265. 	    //auxint02 = auxtree01.GetKey();
  266. 	    //ntb = c_node.SetKey(auxint02);
  267. 	    ntb = c_node.SetKey((c_node.GetLeft()).GetKey());
  268. 	    p_node = c_node ;
  269. 	    c_node = c_node.GetLeft() ;
  270. 	}
  271. 	ntb = p_node.SetLeft(my_null);
  272. 	ntb = p_node.SetHas_Left(false);
  273. 	return true ;
  274.     }
  275.  
  276.     // Search for an elemnt in the tree
  277.     public int Search(int v_key){
  278. 	boolean cont ;
  279. 	int ifound ;
  280. 	Tree current_node;
  281. 	int key_aux ;
  282.  
  283. 	current_node = this ;
  284. 	cont = true ;
  285. 	ifound = 0 ;
  286. 	while (cont){
  287. 	    key_aux = current_node.GetKey();
  288. 	    if (v_key < key_aux)
  289. 		if (current_node.GetHas_Left())
  290. 		    current_node = current_node.GetLeft() ;
  291. 		else cont = false ;
  292. 	    else 
  293. 		if (key_aux < v_key)
  294. 		    if (current_node.GetHas_Right())
  295. 			current_node = current_node.GetRight() ;
  296. 		    else cont = false ;
  297. 		else { 
  298. 		    ifound = 1 ;
  299. 		    cont = false ;
  300. 		}
  301. 	}
  302. 	return ifound ;
  303.     }
  304.  
  305.     // Invoke the method to really print the tree elements
  306.     public boolean Print(){
  307. 	Tree current_node;
  308. 	boolean ntb ;
  309.  
  310. 	current_node = this ;
  311. 	ntb = this.RecPrint(current_node);
  312. 	return true ;
  313.     }
  314.  
  315.     // Print the elements of the tree
  316.     public boolean RecPrint(Tree node){
  317. 	boolean ntb ;
  318.  
  319. 	if (node.GetHas_Left()){
  320. 	    //auxtree01 = node.GetLeft() ;
  321. 	    //ntb = this.RecPrint(auxtree01);
  322. 	    ntb = this.RecPrint(node.GetLeft());
  323. 	} else ntb = true ;
  324. 	System.out.println(node.GetKey());
  325. 	if (node.GetHas_Right()){
  326. 	    //auxtree01 = node.GetRight() ;
  327. 	    //ntb = this.RecPrint(auxtree01);
  328. 	    ntb = this.RecPrint(node.GetRight());
  329. 	} else ntb = true ;
  330. 	return true ;
  331.     }
  332.  
  333. }
  334.  
  335.  
Success #stdin #stdout 0.06s 32576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
16
100000000
8
16
4
8
12
14
16
20
24
28
1
1
1
0
1
4
8
14
16
20
24
28
0
0
https://ideone.com/qYzQLb
language:
Java (12.0.1)
created:
3 years 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!