二叉查找樹(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