程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> JAVA綜合教程 >> [javaSE] 數據結構(二叉查找樹-插入節點),javase二叉

[javaSE] 數據結構(二叉查找樹-插入節點),javase二叉

編輯:JAVA綜合教程

[javaSE] 數據結構(二叉查找樹-插入節點),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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved