搜尋此網誌

2013年1月7日 星期一

BST with Java implementation

The removal part is all from Algorithms and Data Structures with implementations in Java and C++ . I just add some comments.


public class BST {

    public static void main(String[] args) {
        Tree myBst = new Tree();
        Node one = new Node(1);
        Node six = new Node(6);
        Node three = new Node(3);
        Node five = new Node(5);
        Node two = new Node(2);

        myBst.insert(one);
        myBst.insert(six);
        myBst.insert(three);
        myBst.insert(five);
        myBst.insert(two);
        myBst.preOrderTraversal(myBst.root);
        System.out.println("-----------------");
        myBst.remove(3);
        myBst.preOrderTraversal(myBst.root);

    }

}

class Node {
    Node leftChild;
    Node rightChild;
    int value;

    Node(int i) {
        this.value = i;
    }

    public boolean remove(int value, Node parent) {
        if (value < this.value) {//not found, keep left search
            if (leftChild != null)
                return leftChild.remove(value, this);
            else
                return false;
        } else if (value > this.value) {//not found , keep right search.
            if (rightChild != null)
                return rightChild.remove(value, this);
            else
                return false;
        } else {//found
            if (leftChild != null && rightChild != null) {//two leafs case
                this.value = rightChild.minValue();
                rightChild.remove(this.value, this);
            } else if (parent.leftChild == this) {//left node is the only one child node
                parent.leftChild = (leftChild != null) ? leftChild : rightChild;
            } else if (parent.rightChild == this) {//right node is the only one child node
                parent.rightChild = (leftChild != null) ? leftChild    : rightChild;
            }
            return true;
        }
    }

    /*
     * The minimum value of a tree is always located in the left sub tree,
     * so recursively search from left subtree. 
     */
    public int minValue() {
        if (leftChild == null)
            return value;
        else
            return leftChild.minValue();
    }

}

class Tree {

    Node root;

    public void insert(Node node) {
        if (root == null) {
            root = node;
        } else {
            Node temp = root;
            while (temp != null) {
                if (node.value >= temp.value) {
                    if (temp.rightChild == null) {
                        temp.rightChild = node;
                        break;
                    } else {
                        temp = temp.rightChild;
                    }
                } else {
                    if (temp.leftChild == null) {
                        temp.leftChild = node;
                        break;
                    } else {
                        temp = temp.leftChild;
                    }

                }
            }

        }
    }

    public boolean remove(int value) {
        if (root == null)
            return false;
        else {
            if (root.value == value) {
                Node auxRoot = new Node(0);
                auxRoot.leftChild = root;
                boolean result = root.remove(value, auxRoot);
                root = auxRoot.leftChild;
                return result;
            } else {
                return root.remove(value, null);
            }
        }
    }

    public void preOrderTraversal(Node root) {
        System.out.println(root.value);
        if (root.leftChild != null) {
            preOrderTraversal(root.leftChild);
        }
        if (root.rightChild != null) {
            preOrderTraversal(root.rightChild);
        }
    }

}

BST with c++

沒有留言:

張貼留言