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

數(shù)組缺點(diǎn): 增刪慢
鏈表缺點(diǎn): 查找慢

二叉排序樹結(jié)合了兩者的優(yōu)點(diǎn);

二叉排序樹

Paste_Image.png

二叉排序樹的特點(diǎn):

1棚点、若它的左子樹不空, 則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)構(gòu)的值;
2早处、若它的右子樹不空, 則右子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)構(gòu)的值;
3、它的左子樹和右子樹都是二叉排序樹;

關(guān)于二叉排序樹的增刪改查:

二分查找:

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);
    }
}

最壞情形下二叉排序樹的查找時(shí)間復(fù)雜度為O(n), 即如下圖所示的worst case:

二叉排序樹的三種情形.png

所以實(shí)際應(yīng)用中并不會(huì)使用二叉排序樹,會(huì)使用二叉排序樹的幾種衍生樹;

增刪查:

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);
        }
    }
    //刪除
    /**
     * 在整個(gè)樹中, 查找指定數(shù)據(jù)節(jié)點(diǎn)的父節(jié)點(diǎn);
     */
    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);
        }
    }
    /**
     * 刪除指定數(shù)據(jù)的節(jié)點(diǎn):
     */
    public void delete(int data) {
        if (mRoot == null || mRoot.mData == data) {//根節(jié)點(diǎn)為空或者要?jiǎng)h除的就是根節(jié)點(diǎn), 直接刪除掉 
            mRoot = null;
            return;
        }
        // 在刪除之前需要找到他的父節(jié)點(diǎn)
        // 感覺這行代碼有些多余, 如果節(jié)點(diǎn)存在, 父節(jié)點(diǎn)肯定也是存在的.
        BinaryTreeNode parent  = searchParent(data);
        if (parent  == null) {//如果父節(jié)點(diǎn)為空, 說明這個(gè)樹是空樹, 沒法刪;
            return;
        }
        //找到要?jiǎng)h除的節(jié)點(diǎn)
        BinaryTreeNode deleteNode = search(parent, data);
        //1.如果該樹左右孩子均為空, 說明該節(jié)點(diǎn)為葉子節(jié)點(diǎn), 直接刪除
        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;
        }
    }
}