1

I am trying to quickly implement a Binary search tree in Java. What is the best class to use that has methods for in-order traversal? (I have heard of TreeMap class. But it looks like the class does not contain any methods to do in-order traversal).

Kara
  • 6,115
  • 16
  • 50
  • 57
  • see also this question: http://stackoverflow.com/q/205945/2170192 – Alex Shesterov Mar 31 '13 at 16:18
  • I dont think any standard library is available for this. Check this link for sample implementation http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html – Lokesh Mar 31 '13 at 15:56

3 Answers3

0

Use LinkedHashMap to traverse in insertion order or TreeMap to traverse in comparison order http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html

user2088476
  • 603
  • 6
  • 15
  • Culd you tell me more about comparison order? –  Mar 31 '13 at 15:58
  • The keys are orderd by comparing them - either using the compareTo method of the class of the key - or you can specify a comparator on map creation time – user2088476 Mar 31 '13 at 16:03
0

You could always just make your own class and that implements the algo using said class.

public class Node {
    Node leftChild;
    Node rightChild;
    int parent;

    Node(int parent) {
        this.parent = parent;
    }
}

And then implement the Binary Search Tree class. This was made very fast, but it's to give you an idea.

public class BSTree {
Node root;

BSTree() {
    root = null;
}

public void insert(Node node, int value) {
    if (value >= node.parent) {
        if (!(node.rightChild == null)) {
            insert(node.rightChild, value);
        } else {
            node.rightChild = new Node(value);
        }
    } else if (value < node.parent) {
        if (!(node.leftChild == null)) {
            insert(node.leftChild, value);
        } else {
            node.leftChild = new Node(value);
        }
    } else {
        root = new Node(value);
    }
}


public boolean delete(Node node, int value) {
    if (root == null) {
        return false;
    } else if (value > root.parent) {
        return delete(root.rightChild, value);
    } else if (value < root.parent) {
        return delete(root.leftChild, value);
    } else {
        if (root.leftChild == null && root.rightChild == null) {
            root = null;
            return true;
        } else if (root.leftChild == null && root.rightChild != null) {
            root = root.rightChild;
            return true;
        } else if (root.leftChild != null && root.rightChild == null) {
            root = root.leftChild;
            return true;
        } else {
                            Node minRight = minNode(root.rightChild);
                            root = minRight;
                            delete(minRight, minRight.parent);
                            return true;
        }
    }
}

public Node minNode(Node node) {
    if (node.leftChild == null) {
        return node;
    } else {
        return minNode(node.leftChild);
    }
}
}
Franklin
  • 1,771
  • 3
  • 17
  • 35
0

The TreeSet class might be what you want

class Node implements Comparable<Node>;   // implements your Node class
TreeSet<Node> set = new TreeSet<Node>();

// after adding a bunch of nodes into set
Iterator<Node> it = set.iterator();
while(it.hasNext()){
    Node current = it.next();
    System.out.println(current); // operate on current node
}

Node first = set.first();    // smallest element in set
Node second = set.ceiling(first);    // the successor method
ssynhtn
  • 1