Question

Problem 1: Write a Java program for traversing a Binary Search Tree in following ways: (use...

Problem 1:

Write a Java program for traversing a Binary Search Tree in following ways: (use any data structure, library functions) ---------- 20 points

i) Depth First Traversal: Inorder, LVR

ii) Depth First Traversal: Inorder, RVL

iii) Depth First Traversal: Preorder, VLR

iv) Depth First Traversal: Preorder, VRL

v) Depth First Traversal: Postorder, LRV

vi) Depth First Traversal: Postorder, RLV

No choice menu required.

Sample Input (taken from keyboard, single space separated nodes as found in a complete BFS: top-down, left to right traversal):

22 10 30 5 15 25 40 1 8

Sample Output (in console or in a file):

Depth First Traversal: Inorder, LVR -> 1 5 8 10 15 22 25 30 40

Depth First Traversal: Inorder, RVL -> 40 30 25 22 15 10 8 5 1

Depth First Traversal: Preorder, VLR -> 22 10 5 1 8 15 30 25 40

Depth First Traversal: Preorder, VRL -> 22 30 40 25 10 15 5 8 1

Depth First Traversal: Postorder, LRV -> 1 8 5 15 10 25 40 30 22

Depth First Traversal: Postorder, RLV -> 40 25 30 15 8 1 5 10 22

Upload one zipped file containing source code file (.java, .cpp or .py) and output screenshot files (in .jpeg, .bmp etc).

Homework Answers

Answer #1

CODE:

public class BinarySearchTree {

class TreeNode {
public int key;
public TreeNode p;
public TreeNode left;
public TreeNode right;

public TreeNode() {
p = left = right = null;
}

public TreeNode(int k) {
key = k;
p = left = right = null;
}
}

public TreeNode root;

public BinarySearchTree() {
root = null;
}

public void insert(int k) {
TreeNode newNode = new TreeNode(k);
  
if(root == null) {
root = newNode;
} else {
TreeNode parent = root;
while(true) {
if(parent.key == k) {
return;
}
if(parent.key > k) {
if(parent.left == null) {
parent.left = newNode;
newNode.p = parent;
return;
} else {
parent = parent.left;
}
} else {
if(parent.right == null) {
parent.right = newNode;
newNode.p = parent;
return;
} else {
parent = parent.right;
}
}
}
}
}

private void inorderLVR(TreeNode t) {
if(t != null) {
inorderLVR(t.left);
System.out.print(t.key + " ");
inorderLVR(t.right);
}
}
private void inorderRVL(TreeNode t) {
if(t != null) {
inorderRVL(t.right);
System.out.print(t.key + " ");
inorderRVL(t.left);
}
}


private void preorderVLR(TreeNode t) {
if(t != null) {
System.out.print(t.key + " ");
preorderVLR(t.left);
preorderVLR(t.right);
}
}
private void preorderVRL(TreeNode t) {
if(t != null) {
System.out.print(t.key + " ");
preorderVRL(t.right);
preorderVRL(t.left);
}
}


private void postorderLRV(TreeNode t) {
if(t != null) {
postorderLRV(t.left);
postorderLRV(t.right);
System.out.print(t.key + " ");
}
}
private void postorderRLV(TreeNode t) {
if(t != null) {
postorderRLV(t.right);
postorderRLV(t.left);
System.out.print(t.key + " ");
}
}
  

/**
* @param args
*/
public static void main(String[] args) {
int[] array = {22, 10, 30, 5, 15, 25, 40, 1, 8};
BinarySearchTree bst = new BinarySearchTree();
for (int i = 0; i < array.length; i++)
bst.insert(array[i]);
  
bst.printReport();
}

private void printReport() {
inorderLVR(root);
System.out.println();
inorderRVL(root);
System.out.println();
preorderVLR(root);
System.out.println();
preorderVRL(root);
System.out.println();
postorderLRV(root);
System.out.println();
postorderRLV(root);
System.out.println();
}

}

OUTPUT:

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
1) Put these integers into a binary search tree and then state the output of a...
1) Put these integers into a binary search tree and then state the output of a preorder traversal. Put EXACTLY ONE SPACE between each integer, so your output looks like this: 1 2 3 4 5 These are the integers to put into the tree: 41 17 80 25 8 11 50 60 100 Output: ____ 2) Put these integers into a binary search tree and then state the output of a preorder traversal. Put EXACTLY ONE SPACE between each...
Java Program: You will be traversing through an integer tree to print the data. Given main(),...
Java Program: You will be traversing through an integer tree to print the data. Given main(), write the methods in the 'IntegerBinaryTree' class specified by the // TODO: sections. There are 6 methods in all to write. Ex: If the input is: 70 86 60 90 49 62 81 85 38 -1 the output should be: Enter whole numbers to insert into the tree, -1 to stop Inorder: 38 - 49 - 60 - 62 - 70 - 81 -...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
Create a program using Binary Trees in Java to do the following 1. Verify a given...
Create a program using Binary Trees in Java to do the following 1. Verify a given expression is balanced in regards to parentheses 2. covert an infix expression to a postfix expression 3. Evaluate the expression Given expressions: String s[] = {"5 + ) * ( 2", " 2 + ( - 3 * 5 ) ", "(( 2 + 3 ) * 5 ) * 8 ", "5 * 10 + ( 15 - 20 ) ) - 25",...
Write a complete Java program to solve the following problem. Read two positive integers from the...
Write a complete Java program to solve the following problem. Read two positive integers from the user and print all the multiple of five in between them. You can assume the second number is bigger than the first. For example if the first number is 1 and the second number is 10, then your program should output 5 10 Note: There is a white space in between the numbers. Java programming please answer ASAP before 2:30
Write the Java(Java 7 or Java 8) program for this problem:- Thanos, in his mission to...
Write the Java(Java 7 or Java 8) program for this problem:- Thanos, in his mission to restore the ecological balance in the universe, has reached planet earth. He considers a planet ecologically balanced if more than half of the people on the planet have the same Consumption Capacity There are N people on planet earth, each having Consumption Capacity C1, C2, ...CN and Strength S1, S2... Sn . Thanos will make earth ecological balanced by killing some people(Possibly None). To...
Intro to JAVA Problem 1: Summing It Up Write a program, which takes two distinct integers...
Intro to JAVA Problem 1: Summing It Up Write a program, which takes two distinct integers separated by space as input and prints the sum of all the integers between them, including the two given numbers. Note that the numbers can appear in either order. You may assume that both numbers are between –10, 000 and 10, 000. For example, if the input is as follows: 10 4 the output should be 49, since 10+9+8+7+6+5+4=49. Similarly, if the input is...
JAVA Problem 1: Summing It Up Write a program, which takes two distinct integers separated by...
JAVA Problem 1: Summing It Up Write a program, which takes two distinct integers separated by space as input and prints the sum of all the integers between them, including the two given numbers. Note that the numbers can appear in either order. You may assume that both numbers are between –10, 000 and 10, 000. For example, if the input is as follows: 10 4 the output should be 49, since 10+9+8+7+6+5+4=49. Similarly, if the input is -3 10...
KNAPSACK Optimization Problem using Greedy Method Problem 1: Item Weight Value 1    14 20 2...
KNAPSACK Optimization Problem using Greedy Method Problem 1: Item Weight Value 1    14 20 2     6 16 3   10 8 4     5 10 5   4 12 Allowed weight = 24 Kg Problem 2: Item Weight Value 1 6 30 2 8 40 3 15 45 4 22 88 5 25 80 Allowed weight = 60 Kg Problem 3: Item Weight Value 1     6 30 2     8 40 3    15 45 4    22 88...
Use the relative frequency distribution in the table below to determine the following. (See Example 1...
Use the relative frequency distribution in the table below to determine the following. (See Example 1 in this section.) A Relative Frequency Distribution Download Time (in seconds) Percent of Subscribers 0–5 0.4 5–10 1.7 10–15 4.3 15–20 9.2 20–25 15.1 25–30 19.4 30–35 19.0 35–40 14.9 40–45 9.0 45–50 4.5 50–55 1.5 55–60 1.0 (a) the percent of subscribers who required less than 20 s to download the file % (b) the probability that a subscriber chosen at random will...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT