遍历 http://blog.csdn.net/baoendemao/article/details/39007627

数组缺点: 增删慢
链表缺点: 查找慢

二叉排序树结合了两者的优点;

二叉排序树

Paste_Image.png

二叉排序树的特点:

1、若它的左子树不空, 则左子树上所有结点的值均小于它的根结构的值;
2、若它的右子树不空, 则右子树上所有结点的值均小于它的根结构的值;
3、它的左子树和右子树都是二叉排序树;

关于二叉排序树的增删改查:

二分查找:

public Node find(Node root,Key k){
    if (root==null){
        return null;
    }
    if (key==null){
        return null;
    }
    if(key.compareTo(root.key)==0){
        return root;
    }
    if(key.compareTo(root.key)<0){
        return find(root.left,key);
    }
    if(key.compareTo(root.key)>0){
        return find(root.right,key);
    }
}

最坏情形下二叉排序树的查找时间复杂度为O(n), 即如下图所示的worst case:

二叉排序树的三种情形.png

所以实际应用中并不会使用二叉排序树,会使用二叉排序树的几种衍生树;

增删查:

public class BinaryTreeNode{
    int mData;
    BinaryTreeNode mLeft;
    BinaryTreeNode mRight;
    BinaryTreeNode mParent;
}
public class BinarySearchTree {
    private BinaryTreeNode mRoot;
    public BinarySearchTree(BinaryTreeNode root){
        mRoot = root;
    }
    //查找
    public BinaryTreeNode search(int data){
        return search(mRoot,data);
    }
    public BinaryTreeNode search(BinaryTreeNode node,int data) {
        if (node == null || node.mData == data){
            return node;
        }
        if (data < node.mData){
            return search(node.mLeft, data);
        } else {
            return search(node.mRight, data);
        }
    }
    
    //插入
    public void insert(int data){
        if (mRoot == null){
            mRoot = new BinaryTreeNode();
            mRoot.mData = data;
            return;
        }
        searchAndInsert(null,mRoot,data);
    }
    private BinaryTreeNode searchAndInsert(BinaryTreeNode parent, BinaryTreeNode node, int data){
        if (node == null){
            node = new BinaryTreeNode();
            node.mData = data;
            if (parent != null) {
                if (data < parent.mData) {
                    parent.mLeft = node;
                } else {
                    parent.mRight = node;
                }
            }
            return node;
        }
        if (data == node.mData){
            return node;
        } else if (data < node.mData) {
            return searchAndInsert(node, node.mLeft, data);
        } else if (data > node.mData) {
            return searchAndInsert(node, node.mRight, data);
        }
    }
    //删除
    /**
     * 在整个树中, 查找指定数据节点的父节点;
     */
    public BinaryTreeNode searchParent(int data) {
        return searchParent(null, mRoot, data);
    }
    public BinaryTreeNode searchParent(BinaryTreeNode parent, BinaryTreeNode node, int data) {
        if (node == null) {
            return;
        }
        if (data == node.mData) {
            return parent;
        } else if (data < node.mData) {
            return searchParent(node, node.mLeft, data);
        } else if (data > node.mData) {
            return searchParent(node, node.mRight, data);
        }
    }
    /**
     * 删除指定数据的节点:
     */
    public void delete(int data) {
        if (mRoot == null || mRoot.mData == data) {//根节点为空或者要删除的就是根节点, 直接删除掉 
            mRoot = null;
            return;
        }
        // 在删除之前需要找到他的父节点
        // 感觉这行代码有些多余, 如果节点存在, 父节点肯定也是存在的.
        BinaryTreeNode parent  = searchParent(data);
        if (parent  == null) {//如果父节点为空, 说明这个树是空树, 没法删;
            return;
        }
        //找到要删除的节点
        BinaryTreeNode deleteNode = search(parent, data);
        //1.如果该树左右孩子均为空, 说明该节点为叶子节点, 直接删除
        if (deleteNode.mLeft == null && deleteNode.mRight == null) {
            deleteNode = null;
            if (parent.mLeft != null && parent.mLeft.mData == data) {
                parent.mLeft = null;
            } else if (parent.mRight != null && parent.mRight.mData == data) {
                parent.mRight = null;
            }
            return;
        } else if (deleteNode.mLeft != null && deleteNode.mRight == null) {
            //2.左孩子不为空, 右孩子为空
            parent.mLeft = deleteNode.mLeft;
            deleteNode = null;
            return;
        } else if () {
            //3.左孩子为空, 右孩子不为空
            parent.mRight = deleteNode.mRight;
            deleteNode = null;
            return;
        } else if () {
            //4.左右孩子均不为空
            BinaryTreeNode right = parent.mRight;   
            while (right.mLeft != null) {
                right = right.mLeft;
            }   
            deleteNode = right;
            parent.mLeft = right;
            deleteNode = null;
            return;
        }
    }
}