import java.util.*; class TNode<E> { private E value; private TNode<E> left; pri
ID: 671821 • Letter: I
Question
import java.util.*; class TNode<E> { private E value; private TNode<E> left; private TNode<E> right; public TNode() { left = right = null; value = null; } public TNode(E value) { this.value = value; left = right = null; } public TNode(E value, TNode<E> left, TNode<E> right) { this.value = value; this.left = left; this.right = right; } public void insertLChild(TNode<E> node) { left = node; } public void insertRChild(TNode<E> node) { right = node; } public TNode<E> getLChild() { return left; } public TNode<E> getRChild() { return right; } public void setValue(E value) { this.value = value; } public E getValue() { return value; } } public class Expression_Tree { public static TNode<Character> createTree(String expression) { // creating a tree Stack<TNode<Character> > myStack = new Stack<>(); for (char c: expression.toCharArray()) { if (Character.isDigit(c) || Character.isLetter(c)) { // FILL THIS PART } else { // FILL THIS PART } } TNode<Character> tree = myStack.pop(); if (!myStack.isEmpty()) { System.out.println("problem in the expression"); return null; } else return tree; } public static void printInorder(TNode<Character> root) { // FILL THIS PART } public static void printPreorder(TNode<Character> root) { // FILL THIS PART } public static void printPostorder(TNode<Character> root) { // FILL THIS PART } public static void main(String[] args) { // TODO Auto-generated method stub System.out.print("please, enter a mathematical expression: "); Scanner scnr = new Scanner(System.in); String expression = scnr.next(); TNode<Character> tree = createTree(expression); if (tree == null) return; System.out.println("printing inorder"); printInorder(tree); System.out.println("---------------------"); System.out.println("printing preorder"); printPreorder (tree); System.out.println("---------------------"); System.out.println("printing postorder"); printPostorder (tree); System.out.println("---------------------"); } }
Explanation / Answer
public class Node<T> {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
public class BinarySearchTree {
public Node root;
public BinarySearchTree insert(int value) {
Node node = new Node<>(value);
if (root == null) {
root = node;
return this;
}
insertRec(root, node);
return this;
}
private void insertRec(Node latestRoot, Node node) {
if (latestRoot.value > node.value) {
if (latestRoot.left == null) {
latestRoot.left = node;
return;
} else {
insertRec(latestRoot.left, node);
}
} else {
if (latestRoot.right == null) {
latestRoot.right = node;
return;
} else {
insertRec(latestRoot.right, node);
}
}
}
public int findMinimum() {
if (root == null) {
return 0;
}
Node currNode = root;
while (currNode.left != null) {
currNode = currNode.left;
}
return currNode.value;
}
public int findMaximum() {
if (root == null) {
return 0;
}
Node currNode = root;
while (currNode.right != null) {
currNode = currNode.right;
}
return currNode.value;
}
/
Printing the contents of the tree in an inorder way.
/
public void printInorder() {
printInOrderRec(root);
System.out.println("");
}
/
method to recursively print the contents in an inorder way
/
private void printInOrderRec(Node currRoot) {
if (currRoot == null) {
return;
}
printInOrderRec(currRoot.left);
System.out.print(currRoot.value + ", ");
printInOrderRec(currRoot.right);
}
/
Printing the contents of the tree in a Preorder way.
/
public void printPreorder() {
printPreOrderRec(root);
System.out.println("");
}
/
method to recursively print the contents in a Preorder way
/
private void printPreOrderRec(Node currRoot) {
if (currRoot == null) {
return;
}
System.out.print(currRoot.value + ", ");
printPreOrderRec(currRoot.left);
printPreOrderRec(currRoot.right);
}
/
Printing the contents of the tree in a Postorder way.
/
public void printPostorder() {
printPostOrderRec(root);
System.out.println("");
}
/
method to recursively print the contents in a Postorder way
/
private void printPostOrderRec(Node currRoot) {
if (currRoot == null) {
return;
}
printPostOrderRec(currRoot.left);
printPostOrderRec(currRoot.right);
System.out.print(currRoot.value + ", ");
}
}
public class BinarySearchTreeDemo {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst .insert(40)
.insert(25)
.insert(78)
.insert(10)
.insert(3)
.insert(17)
.insert(32)
.insert(30)
.insert(38)
.insert(78)
.insert(50)
.insert(93);
System.out.println("Inorder traversal");
bst.printInorder();
System.out.println("Preorder Traversal");
bst.printPreorder();
System.out.println("Postorder Traversal");
bst.printPostorder();
System.out.println("The minimum value in the BST: " + bst.findMinimum());
System.out.println("The maximum value in the BST: " + bst.findMaximum());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.