This is my code Can you make Traversal part not using Recursive Using Stack plz
ID: 3804201 • Letter: T
Question
This is my code
Can you make Traversal part not using Recursive
Using Stack plz
--------------------------------------------------------------------
RBTree.java
public class RBTree{
private Node current;
private Node parent;
private Node grandparent;
private Node header;
private Node great;
private static Node nil;
// set the nil null cuz java cannot directly use nil
// set the int color for RED & BLACK
private static final int RED = 0;
private static final int BLACK = 1;
// static initializer for nil
static{
nil = new Node(0);
nil.left = nil;
nil.right = nil;
}
// constructor
public RBTree(int neglnf){
header = new Node(neglnf);
header.left = nil;
header.right = nil;
}
// This function check if the tree is empty or not
public boolean isEmpty(){
return header.right == nil;
}
// this function make tree empty
public void makeEmpty(){
header.right = nil;
}
// this function insert element(node)
public void insert(int keyvalue){
current = parent = grandparent = header;
nil.element = keyvalue;
while(current.element != keyvalue){
great = grandparent;
grandparent = parent;
parent= current;
current = keyvalue < current.element ? current.left : current.right;
// next step, check children = RED
if(current.left.color == RED && current.right.color == RED){
handleRotate(keyvalue);
}
}
// fail insertion if present already
if(current != nil){
return;
}
current = new Node(keyvalue, nil, nil);
// next linked with parent
if(keyvalue < parent.element){
parent.left = current;
}
else{
parent.right = current;
}
handleRotate(keyvalue);
}
// this function do rotation ( if i can - -)
private void handleRotate(int keyvalue){
// color flip
// property : insert red Node with 2 nil children
current.color = RED;
current.left.color = BLACK;
current.right.color = BLACK;
if(parent.color == RED){
//rotate
grandparent.color = RED;
if(keyvalue < grandparent.element != keyvalue < parent.element){
parent = checkRotate(keyvalue, grandparent); /////////
}
current = checkRotate(keyvalue, great);
current.color = BLACK;
}
// this part make sure Root is always BLACK
header.right.color = BLACK;
}
// this function check rotation
private Node checkRotate(int keyvalue, Node parent){
if(keyvalue < parent.element){
return parent.left = keyvalue < parent.left.element ?
rotateLeftChild(parent.left) : rotateRightChild(parent.right);
}
else{
return parent.right = keyvalue < parent.right.element ?
rotateLeftChild(parent.right) : rotateRightChild(parent.right);
}
}
// this function do binary tree left rotate
private Node rotateLeftChild(Node k2){
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
// this function do binart tree right rotate
private Node rotateRightChild(Node k1){
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
// this function count tree nodes
public int countNodes(){
return countNodes(header.right);
}
// +1 if its not nil node
// check left, right
// and return total
private int countNodes(Node n){
if(n == nil){
return 0;
}
else{
int i = 1;
i += countNodes(n.left);
i += countNodes(n.right);
return i;
}
}
// this function search element
public boolean search(int value){
return search(header.right, value);
}
// bigger then go left
// smaller then go right
// return found
private boolean search(Node n, int value){
boolean found = false;
while(( n != nil) && !found){
int nvalue = n.element;
if(value < nvalue){
n = n.left;
}
else if( value > nvalue){
n = n.right;
}
else{
found = true;
break;
}
}
return found;
}
/////////////////////////////////////////////////////////////////////
/////////////////////// Traversal part ////////////////////////////
public void inorder(){
inorder(header.right);
}
private void inorder(Node n){
if( n != nil){
inorder(n.left);
char c = 'B';
if(n.color == 0){
c = 'R';
}
// --------------- adjust later -----------------
System.out.println(n.element + " " + c + " ");
inorder(n.right);
}
}
public void preorder(){
preorder(header.right);
}
private void preorder(Node n){
if( n != nil){
char c = 'B';
if( n.color == 0){
c = 'R';
}
System.out.println(n.element + " " + c + " ");
preorder(n.right);
}
}
public void postorder(){
postorder(header.right);
}
private void postorder(Node n){
if( n != nil){
postorder(n.left);
postorder(n.right);
char c = 'B';
if(n.color == 0){
c = 'R';
}
System.out.println(n.element + " " + c + " ");
}
}
}
--------------------------------------------------------------------------------
RBTree Main.java
public class RBTreeMain {
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
// Creating Object
RBTree rbt = new RBTree(Integer.MIN_VALUE);
System.out.println(" Showing the RED BLACK TREE" );
char ch;
// switch showing option
do{
System.out.println(" RBTree Operations ");
System.out.println(" 1. insert ");
System.out.println(" 2. search ");
System.out.println(" 3. count nodes ");
System.out.println(" 4. check empty ");
System.out.println(" 5. clear tree ");
int choice = scan.nextInt();
switch(choice){
case 1:
System.out.println("Enter Integer ");
rbt.insert(scan.nextInt());
break;
case 2:
System.out.println("Enter integer to search ");
System.out.println(" Result : " + rbt.search(scan.nextInt()));
break;
case 3:
System.out.println("Total Nodes: " + rbt.countNodes());
break;
case 4:
System.out.println("Empty state: " + rbt.isEmpty());
break;
case 5:
System.out.println(" Tree Cleared ");
rbt.makeEmpty();
break;
default:
System.out.println(" WRONG ENTRY ");
break;
}
// show Traversal
System.out.println(" inorder ");
rbt.inorder();
System.out.println(" postorder ");
rbt.postorder();
System.out.println(" preorder ");
rbt.preorder();
System.out.println(" Continue ? (y/n) ");
ch = scan.next().charAt(0);
}while(ch == 'Y' || ch == 'y');
}
}
--------------------------------------------------------
Node.java
public class Node{
Node left, right;
int element;
//private final int RED = 0;
//private final int BLACK = 1;
//this part souhld set on RBTree class
int color;
// Constructor
public Node(int node){
// this.element = node;
// well, people using lots on code in this way
this(node, null, null);
}
public Node(int node, Node lt, Node rt){
left = lt;
right = rt;
element = node;
color = 1;
}
}
Explanation / Answer
Made changes only in RBTree.java file.
PROGRAM CODE:
package rbtree;
import java.util.Stack;
public class RBTree{
private Node current;
private Node parent;
private Node grandparent;
private Node header;
private Node great;
private static Node nil;
// set the nil null cuz java cannot directly use nil
// set the int color for RED & BLACK
private static final int RED = 0;
private static final int BLACK = 1;
// static initializer for nil
static{
nil = new Node(0);
nil.left = nil;
nil.right = nil;
}
// constructor
public RBTree(int neglnf){
header = new Node(neglnf);
header.left = nil;
header.right = nil;
}
// This function check if the tree is empty or not
public boolean isEmpty(){
return header.right == nil;
}
// this function make tree empty
public void makeEmpty(){
header.right = nil;
}
// this function insert element(node)
public void insert(int keyvalue){
current = parent = grandparent = header;
nil.element = keyvalue;
while(current.element != keyvalue){
great = grandparent;
grandparent = parent;
parent= current;
current = keyvalue < current.element ? current.left : current.right;
// next step, check children = RED
if(current.left.color == RED && current.right.color == RED){
handleRotate(keyvalue);
}
}
// fail insertion if present already
if(current != nil){
return;
}
current = new Node(keyvalue, nil, nil);
// next linked with parent
if(keyvalue < parent.element){
parent.left = current;
}
else{
parent.right = current;
}
handleRotate(keyvalue);
}
// this function do rotation ( if i can - -)
private void handleRotate(int keyvalue){
// color flip
// property : insert red Node with 2 nil children
current.color = RED;
current.left.color = BLACK;
current.right.color = BLACK;
if(parent.color == RED){
//rotate
grandparent.color = RED;
if(keyvalue < grandparent.element != keyvalue < parent.element){
parent = checkRotate(keyvalue, grandparent); /////////
}
current = checkRotate(keyvalue, great);
current.color = BLACK;
}
// this part make sure Root is always BLACK
header.right.color = BLACK;
}
// this function check rotation
private Node checkRotate(int keyvalue, Node parent){
if(keyvalue < parent.element){
return parent.left = keyvalue < parent.left.element ?
rotateLeftChild(parent.left) : rotateRightChild(parent.right);
}
else{
return parent.right = keyvalue < parent.right.element ?
rotateLeftChild(parent.right) : rotateRightChild(parent.right);
}
}
// this function do binary tree left rotate
private Node rotateLeftChild(Node k2){
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
// this function do binart tree right rotate
private Node rotateRightChild(Node k1){
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
// this function count tree nodes
public int countNodes(){
return countNodes(header.right);
}
// +1 if its not nil node
// check left, right
// and return total
private int countNodes(Node n){
if(n == nil){
return 0;
}
else{
int i = 1;
i += countNodes(n.left);
i += countNodes(n.right);
return i;
}
}
// this function search element
public boolean search(int value){
return search(header.right, value);
}
// bigger then go left
// smaller then go right
// return found
private boolean search(Node n, int value){
boolean found = false;
while(( n != nil) && !found){
int nvalue = n.element;
if(value < nvalue){
n = n.left;
}
else if( value > nvalue){
n = n.right;
}
else{
found = true;
break;
}
}
return found;
}
/////////////////////////////////////////////////////////////////////
/////////////////////// Traversal part ////////////////////////////
public void inorder(){
inorder(header.right);
}
private void inorder(Node n){
if(n != nil)
{
Stack<Node> stack = new Stack<Node>();
Node node = n;
while (node != nil) {
stack.push(node);
node = node.left;
}
while (stack.size() > 0) {
// visit the top node
node = stack.pop();
char c = 'B';
if(node.color == 0){
c = 'R';
}
System.out.println(node.element + " " + c + " ");
if (node.right != nil) {
node = node.right;
// the next node to be visited is the leftmost
while (node != nil) {
stack.push(node);
node = node.left;
}
}
}
}
/*if( n != nil){
inorder(n.left);
char c = 'B';
if(n.color == 0){
c = 'R';
}
// --------------- adjust later -----------------
System.out.println(n.element + " " + c + " ");
inorder(n.right);
}*/
}
public void preorder(){
preorder(header.right);
}
private void preorder(Node n){
Stack<Node> nodes = new Stack<Node>();
nodes.push(n);
while (!nodes.isEmpty())
{
Node node = nodes.pop();
char c = 'B';
if( node.color == 0){
c = 'R';
}
System.out.println(node.element + " " + c + " ");
if (current.right != nil)
{
nodes.push(current.right);
}
if (current.left != nil)
{
nodes.push(current.left);
}
}
/*if( n != nil){
char c = 'B';
if( n.color == 0){
c = 'R';
}
System.out.println(n.element + " " + c + " ");
preorder(n.right);
}*/
}
public void postorder(){
postorder(header.right);
}
private void postorder(Node n){
Node cur = n;
Node pre = n;
Stack<Node> s = new Stack<Node>();
if(n!=nil)
s.push(n);
while(!s.isEmpty()){
cur = s.peek();
if(cur==pre||cur==pre.left ||cur==pre.right){// we are traversing down the tree
if(cur.left!=nil){
s.push(cur.left);
}
else if(cur.right!=nil){
s.push(cur.right);
}
if(cur.left==nil && cur.right==nil){
Node node = s.pop();
char c = 'B';
if(node.color == 0){
c = 'R';
}
System.out.println(node.element + " " + c + " ");
}
}else if(pre==cur.left){// we are traversing up the tree from the left
if(cur.right!=nil){
s.push(cur.right);
}else if(cur.right==nil){
Node node = s.pop();
char c = 'B';
if(node.color == 0){
c = 'R';
}
System.out.println(node.element + " " + c + " ");
}
}else if(pre==cur.right){// we are traversing up the tree from the right
Node node = s.pop();
char c = 'B';
if(node.color == 0){
c = 'R';
}
System.out.println(node.element + " " + c + " ");
}
pre=cur;
}
}
/* if( n != nil){
postorder(n.left);
postorder(n.right);
char c = 'B';
if(n.color == 0){
c = 'R';
}
System.out.println(n.element + " " + c + " ");
}
}*/
}
OUTPUT:
Showing the RED BLACK TREE
RBTree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter Integer
12
inorder
12 B
postorder
12 B
preorder
12 B
Continue ? (y/n)
y
RBTree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter Integer
45
inorder
12 B
45 R
postorder
45 R
12 B
preorder
12 B
Continue ? (y/n)
y
RBTree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
76
WRONG ENTRY
inorder
12 B
45 R
postorder
45 R
12 B
preorder
12 B
Continue ? (y/n)
y
RBTree Operations
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter Integer
1
inorder
1 R
12 B
45 R
postorder
1 R
45 R
12 B
preorder
12 B
Continue ? (y/n)
n
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.