Please implement pre-order and post-order binary tree walk((Recursive and non Re
ID: 3732485 • Letter: P
Question
Please implement pre-order and post-order binary tree walk((Recursive and non Recursive) on LinkedBinaryTree using stack
import net.datastructures.LinkedBinaryTree;
import net.datastructures.Position;
public class BST> extends LinkedBinaryTree {
public boolean search(E e) {
Node curr = validate(root());
while(curr!=null) {
int temp = e.compareTo(curr.getElement());
if(temp==0) {
return true;
}else if(temp <0)
curr = validate(left(curr));
else
curr = validate(right(curr));
}
return false;
}
public Position find(E e){
Position curr = root();
while(curr!=null) {
int temp = e.compareTo(curr.getElement());
if(temp==0) {
return curr;
}else if(temp <0)
curr = left(curr);
else
curr =right(curr);
}
return null;
}
public boolean insert(E e) {
Position parent = null;
Position curr = root();
if(curr == null) {
addRoot(e);
return true;
}else {
while(curr != null) {
int result = e.compareTo(curr.getElement());
if(result == 0)
return false;
else if(result < 0) {
parent = curr;
curr = left(curr);
}else {
parent = curr;
curr = right(curr);
}
}
if(e.compareTo(parent.getElement()) < 0)
addLeft(parent, e);
else
addRight(parent, e);
return true;
}
}
public boolean remove(E e) {
Node curr = validate(find(e));
if(curr == null) return false; //not found
if(numChildren(curr) > 1) {
// it has two children - find precessor
Node pre = predecessorNode(curr);
curr.setElement(pre.getElement());
remove(pre);
}else {
//it has one child or none
remove(curr);
}
return true;
}
public E min(Position curr) {
while(left(curr)!=null) {
curr = left(curr);
}
if(curr != null)
return curr.getElement();
else
return null;
}
public Node minNode(Position curr) {
while(left(curr)!=null) {
curr = left(curr);
}
if(curr != null)
return validate(curr);
else
return null;
}
public E max(Position curr) {
while(right(curr)!=null) {
curr = right(curr);
}
if(curr != null)
return curr.getElement();
else
return null;
}
public Node maxNode(Position curr) {
while(right(curr)!=null) {
curr = right(curr);
}
if(curr != null)
return validate(curr);
else
return null;
}
public E successor(Position curr) {
if(right(curr) != null)
return min(right(curr));
Position p = parent(curr);
while(p != null && curr == right(p)) {
curr = p;
p = parent(p);
}
if(p != null)
return p.getElement();
else
return null;
}
public Node successorNode(Position curr) {
if(right(curr) != null)
return minNode(right(curr));
Position p = parent(curr);
while(p != null && curr == right(p)) {
curr = p;
p = parent(p);
}
if(p != null)
return validate(p);
else
return null;
}
public E predecessor(Position curr) {
if(left(curr) != null)
return max(left(curr));
Position p = parent(curr);
while(p != null && curr == left(p)) {
curr = p;
p = parent(p);
}
if(p != null)
return p.getElement();
else
return null;
}
public Node predecessorNode(Position curr) {
if(left(curr) != null)
return maxNode(left(curr));
Position p = parent(curr);
while(p != null && curr == left(p)) {
curr = p;
p = parent(p);
}
if(p != null)
return validate(p);
else
return null;
}
public void inOrderTraversal() {
inOrderTraversal(super.root);
}
public void inOrderTraversal(Node root) {
if(root!=null) {
inOrderTraversal(root.getLeft());
System.out.print(root.getElement() + " ");
inOrderTraversal(root.getRight());
}
}
public void nonrecursiveInOrder(Node root){
if(root==null) return;
ArrayStack> stack = new ArrayStack<>();
ArrayList> list = new ArrayList<>();
stack.push(root);
while(!stack.isEmpty()) {
Node node = stack.top();
if(node.getLeft() != null && !list.contains(node.getLeft())) {
stack.push(node.getLeft());
}else {
stack.pop();
list.add(node);
if(node.getRight()!= null) {
stack.push(node.getRight());
}
}
}
for(int i=0; i System.out.print(list.get(i).getElement() + " ");
}
System.out.print(" ");
}
}
Copyright © 2012-2017, Chengyu Sun. All rights reserved.
Explanation / Answer
//Recursive method for preoder traversal
void PreorderTraversal(Node root)
{
if (root == null)
return;
/* first print element of node */
System.out.print(root.getElement() + " ");
/* recur on left */
PreorderTraversal(root.getLeft());
/* recur on right */
PreorderTravesal(root.getRight());
}
ecursive method for post-order traversal
void PostorderTraversal(Node root)
{
if (root == null)
return;
// first recur on left subtree
PostorderTravesal(root.getLeft());
// then recur on right subtree
PostorderTraversal(root.getRight());
// now deal with the node
System.out.print(root.getElement() + " ");
}
//Iterative method for preoder taversal using 1 stack
void PreorderIterative(Node root) {
if (root == null) {
return;
}
// Create an empty stack and push root to it
Stack<Node> nodeStack = new Stack<Node>();
nodeStack.push(root);
while (nodeStack.empty() == false) {
// Pop the top item from stack and print it
Node node = nodeStack.peek();
System.out.print(node.getElement() + " ");
nodeStack.pop();
// Push right and left children of the popped node to stack
if (node.getRight() != null) {
nodeStack.push(mynode.getRight());
}
if (node.getLeft() != null) {
nodeStack.push(node.getLeft());
}
}
}
//Iterative method for Post-Order Traversal using 2 stacks
void postOrderIterative(Node root)
{
// Create 2 stacks
Stack<Node>x = new Stack<Node>();
Stack<Node>y = new Stack<Node>();
if (root == null)
return;
// push root to first stack
x.push(root);
// Until first stack is not empty
while (!x.isEmpty())
{
// Pop an item from x and push it to y
Node temp = x.pop();
y.push(temp);
//Push left and right children
if (temp.getLeft() != null)
x.push(temp.getLeft());
if (temp.getRight() != null)
x.push(temp.getRight());
}
// Print all elements of second stack
while (!y.isEmpty())
{
Node temp = y.pop();
System.out.print(temp.getElement() + " ");
}
}