This is a Java Program to to delete a particular node from the tree without using recursion.
Here is the source code of the Java Program to Delete a Particular Node in a Tree Without Using Recursion. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
//This is a java program to delete a particular node from the tree without using a recursion import java.util.Scanner; class BinaryNode { private int Key; private Object Data; private BinaryNode Left; private BinaryNode Right; public BinaryNode(int k, Object d) { Key = k; Data = d; Left = null; Right = null; } // Get Operations public int gKey() { return Key; } public Object gData() { return Data; } public BinaryNode gLeft() { return Left; } public BinaryNode gRight() { return Right; } // Set Operations public void sKey(int AValue) { Key = AValue; } public void sData(Object AValue) { Data = AValue; } public void sLeft(BinaryNode AValue) { Left = AValue; } public void sRight(BinaryNode AValue) { Right = AValue; } } public class BTree { private BinaryNode Root; private int NoOfNodes; private BTree() { // constructor Root = null; NoOfNodes = 0; } public boolean IsEmpty() { return (NoOfNodes == 0); } public BinaryNode gRoot() { return Root; } public int Count() { return NoOfNodes; } public int Size(BinaryNode ATree) { if (ATree == null) return 0; else return (1 + Size(ATree.gLeft()) + Size(ATree.gRight())); } public int Height(BinaryNode ATree) { if (ATree == null) return 0; else return (1 + Math.max(Height(ATree.gLeft()), Height(ATree.gRight()))); } public void PreOrder(BinaryNode ATree) { if (ATree != null) { System.out.print(ATree.gKey() + " "); PreOrder(ATree.gLeft()); PreOrder(ATree.gRight()); } } public void InOrder(BinaryNode ATree) { if (ATree != null) { InOrder(ATree.gLeft()); System.out.print(ATree.gKey() + " "); InOrder(ATree.gRight()); } } public void PostOrder(BinaryNode ATree) { if (ATree != null) { PostOrder(ATree.gLeft()); PostOrder(ATree.gRight()); System.out.print(ATree.gKey() + " "); } } public void Insert(int AId, Object AValue) { BinaryNode Temp, Current, Parent; if (Root == null) { Temp = new BinaryNode(AId, AValue); Root = Temp; NoOfNodes++; } else { Temp = new BinaryNode(AId, AValue); Current = Root; while (true) { Parent = Current; if (AId < Current.gKey()) { Current = Current.gLeft(); if (Current == null) { Parent.sLeft(Temp); NoOfNodes++; return; } } else { Current = Current.gRight(); if (Current == null) { Parent.sRight(Temp); NoOfNodes++; return; } } } } } public BinaryNode Find(int AKey) { BinaryNode Current = null; if (!IsEmpty()) { Current = Root; // start search at top of tree while (Current.gKey() != AKey) { if (AKey < Current.gKey()) Current = Current.gLeft(); else Current = Current.gRight(); if (Current == null) return null; } } return Current; } public BinaryNode GetSuccessor(BinaryNode ANode) { BinaryNode Current, Successor, SuccessorParent; Successor = ANode; SuccessorParent = ANode; Current = ANode.gRight(); while (Current != null) { SuccessorParent = Successor; Successor = Current; Current = Current.gLeft(); } if (Successor != ANode.gRight()) { SuccessorParent.sLeft(Successor.gRight()); Successor.sRight(ANode.gRight()); } return Successor; } public boolean Delete(int AKey) { BinaryNode Current, Parent; boolean IsLeftChild = true; Current = Root; Parent = Root; while (Current.gKey() != AKey) { Parent = Current; if (AKey < Current.gKey()) { IsLeftChild = true; Current = Current.gLeft(); } else { IsLeftChild = false; Current = Current.gRight(); } if (Current == null) return false; } if (Current.gLeft() == null && Current.gRight() == null) { if (Current == Root) Root = Current.gLeft(); else if (IsLeftChild) Parent.sLeft(Current.gRight()); else Parent.sRight(Current.gRight()); } else { if (Current.gRight() == null) { if (Current == Root) Root = Current.gRight(); else if (IsLeftChild) Parent.sLeft(Current.gLeft()); else Parent.sRight(Current.gLeft()); } else { if (Current.gLeft() == null) { if (Current == Root) Root = Current.gLeft(); else if (IsLeftChild) Parent.sLeft(Current.gRight()); else Parent.sRight(Current.gRight()); } else { BinaryNode Successor = GetSuccessor(Current); if (Current == Root) Root = Successor; else if (IsLeftChild) Parent.sLeft(Successor); else Parent.sRight(Successor); Successor.sLeft(Current.gLeft()); } } } NoOfNodes--; return true; } public static void main(String[] Args) { BTree MyTree = new BTree(); BinaryNode NodeAt; System.out.println("Enter the elements in the tree"); int N = 5; Scanner sc = new Scanner(System.in); for (int i = 0; i < N; i++) MyTree.Insert(sc.nextInt(), i); System.out.print("\nInorder : "); MyTree.InOrder(MyTree.gRoot()); System.out.print("\nPreorder : "); MyTree.PreOrder(MyTree.gRoot()); System.out.print("\nPostorder : "); MyTree.PostOrder(MyTree.gRoot()); System.out.println("\nEnter the element to be deleted: "); int delete = sc.nextInt(); MyTree.Delete(delete); System.out.print("\nInorder : "); MyTree.InOrder(MyTree.gRoot()); System.out.print("\nPreorder : "); MyTree.PreOrder(MyTree.gRoot()); System.out.print("\nPostorder : "); MyTree.PostOrder(MyTree.gRoot()); sc.close(); } }
Output:
$ javac BTree.java $ java BTree Enter the elements in the tree 54 12 32 19 45 Inorder : 12 19 32 45 54 Preorder : 54 12 32 19 45 Postorder : 19 45 32 12 54 Enter the element to be deleted: 12 Inorder : 19 32 45 54 Preorder : 54 32 19 45 Postorder : 19 45 32 54
Related posts:
Java – Random Long, Float, Integer and Double
Truyền giá trị và tham chiếu trong java
Hướng dẫn Java Design Pattern – DAO
An Introduction to Java.util.Hashtable Class
Handling Errors in Spring WebFlux
Python Program to Find Factorial of Number Using Recursion
Convert Character Array to String in Java
Derived Query Methods in Spring Data JPA Repositories
Java Program to Implement LinkedTransferQueue API
Java Copy Constructor
Apache Tiles Integration with Spring MVC
Cachable Static Assets with Spring MVC
Guide to Java Instrumentation
Java Program to Implement SimpeBindings API
Receive email by java client
Java Program to Solve the Fractional Knapsack Problem
Java Program to Implement Dijkstra’s Algorithm using Set
Java Program to Implement Hopcroft Algorithm
Java Program to Implement Adjacency List
Java Program to Check whether Directed Graph is Connected using DFS
The SpringJUnitConfig and SpringJUnitWebConfig Annotations in Spring 5
Hamcrest Collections Cookbook
Tạo số và chuỗi ngẫu nhiên trong Java
Intro to Inversion of Control and Dependency Injection with Spring
Configure a RestTemplate with RestTemplateBuilder
Java Program to Implement the RSA Algorithm
Java Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers
Introduction to Java 8 Streams
Inheritance with Jackson
Using JWT with Spring Security OAuth (legacy stack)
The HttpMediaTypeNotAcceptableException in Spring MVC
Java Program to Construct an Expression Tree for an Prefix Expression