I am supposed to create a binary tree using strings typed in by the user, to build a balanced tree using recursion. When I type in letters: A, B, C, D, E, F
and the output is set up for preorder output, what I am getting is:A B D F C E
according to my understanding of preorder traversal the output should be: A B D E C F
where did I go wrong here?
first is my main class, then my tree class, then treenode class
import java.util.*;
public class TreeDriver {
public static void main(String[] args) {
Tree myTree = new Tree();
Scanner keyboard = new Scanner(System.in);
int input;
while(true){
System.out.println("\nSelect your option!");
System.out.println("\t1 - Enter a new String");
System.out.println("\t2 - Search for a String");
System.out.println("\t3 - Display Tree");
System.out.println("\t4 - Exit");
input = keyboard.nextInt();
Scanner scanner = new Scanner(System.in);
if(input == 1){
System.out.println("Enter a new string: ");
String word = scanner.next().toUpperCase();
myTree.insert(word);
System.out.println("Inserted " + "'" + word + "'" + " into tree");
}else if(input == 2){
System.out.println("Enter a string to search: ");
}else if(input == 3){
System.out.println("Display Tree: ");
myTree.preOrder();
}else if(input == 4){
System.exit(0);//exit program
}
System.out.println("\nEnter another option");
}
}
}
Tree Class
public class Tree {
public TreeNode root;
public Tree(){
root = null;
}
public TreeNode returnRoot(){
return root;
}
public boolean isEmpty(){
return root == null;
}
public void insert(String value){
if(isEmpty()){
root = new TreeNode(value);
}else{
root.add(value);
}
}
public TreeNode getRoot(){
return root;
}
public void preOrder() {
preOrder(root);
}
// using the function ...
public void preOrder(TreeNode root) {
if (root != null) {
System.out.println(root.getWord()); // root
preOrder(root.getLeft()); // left
preOrder(root.getRight()); // right
}
}
}
TreeNode class
public class TreeNode {
private String word; // The data in this node.
private TreeNode left; // Pointer to the left subtree.
private TreeNode right; // Pointer to the right subtree.
public TreeNode(String s){
word = s;
left = null;
right = null;
}
public void add(String value) {
if (left == null) {
left = new TreeNode(value);
} else if( right == null){
right = new TreeNode(value);
} else {
if(countNodes(left) <= countNodes(right)){
left.add(value);
} else {
right.add(value);
}
}
}
//Count the nodes in the binary tree to which root points, and
public static int countNodes( TreeNode root ) {
if ( root == null ){
// The tree is empty. It contains no nodes.
return 0;
}else {
// Start by counting the root.
int count = 1;
// Add the number of nodes in the left subtree.
count += countNodes(root.left);
// Add the number of nodes in the right subtree.
count += countNodes(root.right);
return count; // Return the total.
}
}
public TreeNode getLeft(){
return left;
}
public TreeNode getRight(){
return right;
}
public String getWord(){
return word;
}
}
