[javaSE] 数据结构（二叉查找树-插入节点）详解编程语言

public class BSTree<T extends Comparable<T>> { 
    private BSTNode<T> mRoot; 
 
    /** 
     * 定义二叉树 
     *  
     * @author taoshihan 
     * @param <T> 
     *  
     */ 
    public class BSTNode<T extends Comparable<T>> { 
        public T key; 
        public BSTNode parent, left, right; 
 
        public BSTNode(T key, BSTNode parent, BSTNode left, BSTNode right) { 
            this.key = key; 
            this.parent = parent; 
            this.left = left; 
            this.right = right; 
        } 
    } 
 
    public void insert(BSTree bsTree, BSTNode bstNode) { 
        BSTNode parent = null; 
        BSTNode x = bsTree.mRoot; 
        // 查找bstNode的插入位置，x的指针指对 
        while (x != null) { 
            parent = x;// 把x的位置作为节点的父类 
            int flag = bstNode.key.compareTo(x.key); 
            if (flag < 0) { 
                x = x.left; 
            }else{ 
                x=x.right; 
            } 
        } 
        // 插入 
        bstNode.parent = parent; 
        if(parent==null){ 
            bsTree.mRoot=bstNode; 
        }else{ 
            int flag = bstNode.key.compareTo(parent.key); 
            if (flag < 0) { 
                parent.left = bstNode; 
            } else { 
                parent.right = bstNode; 
            }         
        } 
 
    } 
 
    /** 
     * 插入根节点 
     *  
     * @param key 
     */ 
    public void insert(T key) { 
        BSTNode<T> z = new BSTNode<T>(key, null, null, null); 
        // 如果新建结点失败，则返回。 
        if (z != null) 
            insert(this, z); 
    } 
    /* 
     * 打印"二叉查找树" 
     * 
     * key        -- 节点的键值  
     * direction  --  0，表示该节点是根节点; 
     *               -1，表示该节点是它的父结点的左孩子; 
     *                1，表示该节点是它的父结点的右孩子。 
     */ 
    private void print(BSTNode<T> tree, T key, int direction) { 
         
        if(tree != null) { 
 
            if(direction==0)    // tree是根节点 
                System.out.printf("%2d is root/n", tree.key); 
            else                // tree是分支节点 
                System.out.printf("%2d is %2d's %6s child/n", tree.key, key, direction==1?"right" : "left"); 
 
            print(tree.left, tree.key, -1); 
            print(tree.right,tree.key,  1); 
        } 
    } 
 
    public void print(BSTree<T> tree) { 
        if (tree.mRoot != null){ 
            print(tree.mRoot, tree.mRoot.key, 0); 
        } 
    } 
    /** 
     * @param args 
     */ 
    public static void main(String[] args) { 
        BSTree tree = new BSTree(); 
        tree.insert(3); 
        tree.insert(1); 
        tree.insert(2); 
        tree.insert(5); 
        tree.insert(4); 
        tree.insert(6); 
        tree.print(tree); 
    } 
 
}