[javaSE] 數據結構（二叉查找樹-插入節點）

二叉查找樹（Binary Search Tree），又被稱為二叉搜索樹，它是特殊的二叉樹，左子樹的節點值小於右子樹的節點值。

定義二叉查找樹

定義二叉樹BSTree，它保護了二叉樹的根節點BSTNode類型的mRoot，定義內部類BSTNode

包含二叉樹的幾個基本信息：

key——關鍵字用來對二叉查找樹的節點進行排序

left——指向當前節點的左孩子

right——指向當前節點的右孩子

parent——指向當前節點的父節點

定義插入節點方法insert(T key)，參數：T key要插入的對象

創建節點對象，實例化BSTNode對象，構造參數：T對象

定義重載方法insert(BSTree bsTree,BSTNode bstNode)方法，參數：BSTree樹對象，BSTNode節點對象

插入節點，分兩步，

1.找到節點的父節點位置

2.插入節點到父節點的左位置或者右位置

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

}

輸出：

3 is root
1 is 3's left child
2 is 1's right child
5 is 3's right child
4 is 5's left child
6 is 5's right child