java数据结构：二叉查找树添加 删除 遍历，java数据结构,二叉查找树 添加、删除

java数据结构：二叉查找树添加 删除 遍历，java数据结构,二叉查找树 添加、删除

二叉查找树 添加、删除 、遍历 Java语言实现

Searchtree.java

package com.structures.tree;import java.util.ArrayList;import java.util.NoSuchElementException;import java.util.Stack;/* * Binary Search Tree  */public class Searchtree {    public Integer data;    public Searchtree left;    public Searchtree right;    public void setData(Integer data) {        this.data = data;    }    public Searchtree(Integer number) {        this.data = number;    }    public void setLeft(Searchtree left) {        this.left = left;    }    public void setRight(Searchtree right) {        this.right = right;    }    // add    public void add(int number) {        if (number <= this.data)            add(number, this, this.left, 0);        else            add(number, this, this.right, 1);    }    private void add(int number, Searchtree father, Searchtree child, int tag) {        if (child == null) {            child = new Searchtree(number);            if (tag == 0)                father.setLeft(child);            else                father.setRight(child);        } else {            // attention: here must be child            if (number <= child.data)// add to left                add(number, child, child.left, 0);            else                // add to right                add(number, child, child.right, 1);        }    }    // find    public Searchtree find(int number) {        if (number < data) {            return find(number, this);        } else if (number > data) {            return find(number, this);        } else {            return find(number, this);        }    }    private Searchtree find(int number, Searchtree tree) {        if (tree == null)            throw new NoSuchElementException(                    "no such element in the binary search tree");        if (number < tree.data) {            return find(number, tree.left.left);        } else if (number > tree.data) {            return find(number, tree.right);        } else            return tree;    }    // findPrevious    private ArrayList<Searchtree> trees = new ArrayList<Searchtree>();    private Searchtree findPrevious(int number, Searchtree tree) {        if (tree == null)            throw new NoSuchElementException(                    "no such element in the binary search tree");        trees.add(tree);        if (number < tree.data) {            return findPrevious(number, tree.left);        } else if (number > tree.data) {            return findPrevious(number, tree.right);        } else {            Searchtree pre = trees.get(trees.size() - 2);            trees = null;            return pre;        }    }    // min    public Searchtree findMin(Searchtree tree) {        if (tree == null)            throw new NoSuchElementException(                    "no such element in the binary search tree");        else if (tree.left == null)            return tree;        else            return findMin(tree.left);    }    // max    public Searchtree findMax(Searchtree tree) {        if (tree == null)            throw new NoSuchElementException(                    "no such element in the binary search tree");        else if (tree.right == null)            return tree;        else            return findMax(tree.right);    }    public Searchtree remove(int number) {        return remove(number, this);    }    /*remove     *  是最困难的，请大家参考一下，递归有点晕。大家阅读书理解吧。     *  参考代码：《数据结构与算法分析》-C语言描述 英文版     *  第102-103页      * ISBN: 9787115139849      * detail：http://book.douban.com/subject/1444648/     */    public Searchtree remove(int number, Searchtree tree) {        Searchtree delete = null;        if (tree == null)            throw new IndexOutOfBoundsException("tree size is 0");        else if (number < tree.data) {            // go left            tree.left = remove(number, tree.left);        } else if (number > tree.data) {            // go right            tree.right = remove(number, tree.right);            // found element to be remove        } else if (tree.left != null && tree.right != null) {            // two children            // replace with the smallest in right tree            delete = findMin(tree.right);            tree.setData(delete.data);            tree.setRight(remove(tree.data, tree.right));            delete = null;        } else {            // one or zero child            delete = tree;            if (delete.left == null) {                tree = tree.right;            } else if (delete.right == null) {                tree = tree.left;            }            delete = null;        }        return tree;    }    // 先序遍历 preorder traversal    public void preorder() {        System.out.print(data + " ");        if (left != null)            left.preorder();        if (right != null)            right.preorder();    }    // 中序遍历 inorder traversal    public void inorder() {        if (left != null)            left.inorder();        System.out.print(data + " ");        if (right != null)            right.inorder();    }    // 后序遍历 postorder traversal    public void postorder() {        if (left != null)            left.postorder();        if (right != null)            right.postorder();        System.out.print(data + " ");    }    public int getDepth(Searchtree root) {        int depth;        if (root == null)            return 0;        else {            depth = 1 + Math.max(getDepth(root.left), getDepth(root.right));            return depth;        }    }    public static void main(String[] args) {        Searchtree tree = new Searchtree(5);        tree.add(3);        tree.add(7);        tree.add(2);        tree.add(4);        tree.add(6);        tree.add(8);        tree.add(1);        tree.add(1);        tree.remove(1);        // tree.remove(2, tree);        //tree.remove(tree.data);        tree.preorder();        System.out.println();        tree.inorder();        System.out.println();        System.out.println(tree.getDepth(tree));        System.out.println(tree.find(7).data);        System.out.println(tree.findPrevious(8, tree).data);    }}