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:
HTTP Authentification and CGI/Servlet
Java Program to Find Path Between Two Nodes in a Graph
Supplier trong Java 8
Java Program to Find Inverse of a Matrix
Find the Registered Spring Security Filters
Biểu thức Lambda trong Java 8 – Lambda Expressions
JUnit5 Programmatic Extension Registration with @RegisterExtension
Spring MVC + Thymeleaf 3.0: New Features
Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path
Java Program to Perform Preorder Recursive Traversal of a Given Binary Tree
Iterable to Stream in Java
Spring Cloud – Tracing Services with Zipkin
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm
Java Program to Implement Hash Tables Chaining with Binary Trees
Encode/Decode to/from Base64
Java Program to Check Cycle in a Graph using Topological Sort
Java Program to implement Sparse Vector
Configure a RestTemplate with RestTemplateBuilder
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Constructor Injection in Spring with Lombok
Spring Boot - Database Handling
Java Program to Implement Network Flow Problem
Quick Guide to @RestClientTest in Spring Boot
Java Program to Implement Horner Algorithm
Java Program to Implement Merge Sort Algorithm on Linked List
Extract network card address
Interface trong Java 8 – Default method và Static method
Guide to ThreadLocalRandom in Java
Spring Boot - Quick Start
Java Program to Implement Affine Cipher
Java Program to Generate Random Hexadecimal Byte
Guide to DelayQueue