二叉搜索树的一个简单实现（不平衡）。

/**来自 时代Java公众号**/

import java.util.ArrayDeque;



public class BinaryTree {


    TreeNode root;


    public void insert(int value) {

        if (root == null) {

            root = new TreeNode();

            root.data = value;

        } else {

            insertNode(value, root);

        }

    }


    private void insertNode(int value, TreeNode current) {//时 代 J a v a - N o w J a v a . c o m

        if (value < current.data) {

            if (current.left == null) {

                current.left = new TreeNode();

                current.left.data = value;

            } else {

                insertNode(value, current.left);

            }

        } else {

            if (current.right == null) {

                current.right = new TreeNode();

                current.right.data = value;

            } else {

                insertNode(value, current.right);

            }

        }

    }


    public boolean contains(int value) {

        if (findNode(value) != null) {

            return true;

        } else {

            return false;

        }

    }


    private boolean containsRecursion(int value, TreeNode current) {

        if (current == null) {

            return false;

        } else if (current.data == value) {

            return true;

        } else {

            if (value > current.data) {

                return containsRecursion(value, current.right);

            } else {

                return containsRecursion(value, current.left);

            }

        }

    }



    public TreeNode findNode(int value) {

        return findNodeRecursion(value, root);

    }


    private TreeNode findNodeRecursion(int value, TreeNode current) {

        if (current == null) {

            return null;

        } else if (current.data == value) {

            return current;

        } else {

            if (value > current.data) {

                return findNodeRecursion(value, current.right);

            } else {

                return findNodeRecursion(value, current.left);

            }

        }


    }


    public TreeNode findParent(int value) {

        return findParentRecursion(value, root);

    }



    private TreeNode findParentRecursion(int value, TreeNode current) {

        if (root.data == value) {

            return null;

        }

        if (value < current.data) {

            if (current.left == null) {

                return null;

            } else if (current.left.data == value) {

                return current;

            } else {

                return findParentRecursion(value, current.left);

            }

        } else {

            if (current.right == null) {

                return null;

            } else if (current.right.data == value) {

                return current;

            } else {

                return findParentRecursion(value, current.right);

            }

        }

    }


    public boolean remove(int value) {

        TreeNode nodeToRemove = findNode(value);

        if (nodeToRemove == null) {

            return false;

        }

        TreeNode parent = findParent(value);

        if (root.left == null && root.right == null) {

            root = null;

        } else if (nodeToRemove.left == null && nodeToRemove.right == null) {

            if (value < parent.data) {

                parent.left = null;

            } else {

                parent.right = null;

            }

        } else if (nodeToRemove.left == null) {

            if (value < parent.data) {

                parent.left = nodeToRemove.right;

            } else {

                parent.right = nodeToRemove.right;

            }

        } else if (nodeToRemove.right == null) {

            if (value < parent.data) {

                parent.left = nodeToRemove.left;

            } else {

                parent.right = nodeToRemove.left;

            }

        } else {


            TreeNode largestValue = nodeToRemove.left;


            while (largestValue.right != null) {

                largestValue = largestValue.right;

            }


            TreeNode parentOfLargest = findParent(largestValue.data);

            if (parentOfLargest.left == largestValue) {

                if (largestValue.left == null) {

                    parentOfLargest.left = null;

                } else {

                    parentOfLargest.left = largestValue.left;

                }

            } else {

                parentOfLargest.right = null;

            }


            nodeToRemove.data = largestValue.data;

        }


        return true;

    }


    public TreeNode findMin() {

        if (root == null) {

            return null;

        }

        return findMinRecursion(root);


    }



    private TreeNode findMinRecursion(TreeNode current) {

        if (current.left == null) {

            return current;

        } else {

            return findMinRecursion(current.left);

        }

    }


    public TreeNode findMax() {

        if (root == null) {

            return null;

        }

        return findMaxRecursion(root);


    }


    private TreeNode findMaxRecursion(TreeNode current) {

        if (current.right == null) {

            return current;

        } else {

            return findMaxRecursion(current.right);

        }

    }



    public void traversePreorder() {

        traversePreorderHelper(root);

    }


    private void traversePreorderHelper(TreeNode current) {

        if (current != null) {

            System.out.println(current.data);

            traversePreorderHelper(current.left);

            traversePreorderHelper(current.right);

        }

    }


    public void traversePostorder() {

        traversePostorderHelper(root);

    }


    private void traversePostorderHelper(TreeNode current) {

        if (current != null) {

            traversePostorderHelper(current.left);

            traversePostorderHelper(current.right);

            System.out.println(current.data);

        }

    }


    public void traverseInorder() {

        traverseInorderHelper(root);

    }


    private void traverseInorderHelper(TreeNode current) {

        if (current != null) {

            traverseInorderHelper(current.left);

            System.out.println(current.data);

            traverseInorderHelper(current.right);

        }

    }



    public void traverseBreadth() {

        traverseBreadthHelper(root);

    }


    private void traverseBreadthHelper(TreeNode current) {

        ArrayDeque<TreeNode> deq = new ArrayDeque<TreeNode>();

        while (current != null) {

            System.out.println(current.data);

            if (current.left != null) {

                deq.add(current.left);

            }

            if (current.right != null) {

                deq.add(current.right);

            }

            if (!deq.isEmpty()) {

                current = deq.remove();

            } else {

                current = null;

            }

        }

    }


    public static void main(String[] args) {


        BinaryTree bt = new BinaryTree();

        bt.insert(42);

        bt.insert(13);

        bt.insert(666);

        bt.insert(10);

        bt.insert(11);

        bt.insert(7);

        bt.insert(9);

        bt.insert(4);


        System.out.println("1: " + bt.contains(1));

        System.out.println("10: " + bt.contains(10));

        System.out.println("42: " + bt.contains(42));

        System.out.println(