CODEWITHSUNDEEP
javabinary-search-tree
Ryan Sayles
Ryan Sayles

Reputation: 3431

Searching through a BST

I created a BST that sets each node to a String value, I was wondering if there is a way to search through the tree but just one value at a time. So say the String in a node was "truck" is there a way to search through the tree and return "t"? This is the code I have for building the tree:

public class BinaryTree {

public Node root;
public BinaryTree tree;
public static int pos;
public static Node[] theArray;

private static class Node {
    Node left;
    Node right;
    String data;

    Node(String s) {
        left = null;
        right = null;
        data = s;
    }
}

public BinaryTree plantTree(ArrayList<String> dict) {

    tree = new BinaryTree();

    Collections.shuffle(dict);

    for (String s : dict) {
        s.toUpperCase();
        tree.add(s);
    }

    return tree;

}

/**
 * Creates an empty binary tree
 */
public BinaryTree() {
    root = null;
}

public void add(String data) {
    root = add(root, data);
}

private Node add(Node node, String data) {
    if (node == null) {
        node = new Node(data);
    } else {
        if (data.compareTo(node.data) > 0) {
            node.left = add(node.left, data);
        } else {
            node.right = add(node.right, data);
        }
    }

    return (node);
}

}

Upvotes: 0

Views: 281

Answers (3)

Cratylus
Cratylus

Reputation: 54074

So say the String in a node was "truck" is there a way to search through the tree and return "t"?

Really, I have no idea what this question is about.
If you have a BST then you search it using binary search. That's that.

A binary search returns true if the element is found. You can implement your own BST and not return a boolean but a Char as in t in your question and null if the value is not part of the tree.

Upvotes: 0

JohnnyK
JohnnyK

Reputation: 1102

Maybe I misunderstood your question, but it sounds like you want something to iterate through the tree. I would use the visitor pattern. (This sounds like homework anyways, so why not use standard patterns. :))

public class Node<T>{ 
...
    public void visitDepthFirst(Visitor<T> v){
        v.visit(this);
        if (left != null){
            left.visitDepthFirst(v);
        }
        if (right != null){
            right.visitDepthFirst(v);
        }
    }
}

interface Visitor<T>{
    public void visit(T t);
}
...
Node<String> root = ...;
root.visitDepthFirst(new Visitor<String>(){
    public visit(String val){
        if ("truck".equals(val)){
            // do something
        }
    }
});

I'll let you figure out breadth search. Also, your node class would be more usable using generics. And your class structure is a bit confusing. Might I suggest you just use node AS the tree itself. After all, every node in a tree, is a tree itself. (read about the composite pattern)

Upvotes: 1

woolcock66
woolcock66

Reputation: 45

So it appears that your trying to search through your tree by the first letter only. This will take just as long as returning the entire word. So you still have to use a BST traversal or search algorithem.

Upvotes: 0

Related Questions