資料結構 -- 二元樹
資料結構簡介陣列排序與搜尋鍊節串列雜湊表二元樹紅黑樹派氏樹多元樹訊息相關網站參考文獻最新修改簡體版English |
範例:二元樹class Tree { Node root=null; // root 為本棵樹的根節點. public static void main(String[] args) { String[] keys = {"5", "7", "3", "1", "6", "4", "2", "5"}; String[] values = {"55", "77", "33", "11", "66", "44", "22", "55"}; Tree tree = new Tree(); for (int i=0; i<keys.length; i++) tree.insert(keys[i], values[i]); System.out.println(tree.toString()); System.out.println(tree.get("3")); System.out.println(tree.get("5")); System.out.println(tree.get("9")); } // 插入一組 key, value 的配對到樹中. void insert(String pKey, String pValue) { System.out.println("Insert "+pKey+":"+pValue); if (root == null) root = new Node(pKey, pValue); else root.insert(pKey, pValue); } // 取得對應到 pKey 的 value 值. String get(String pKey) { if (root == null) return null; else return root.get(pKey); } // 將整棵樹轉成字串印 public String toString() { return root.toString(); } } class Node { Node left=null, right=null; String key, value; Node(String pKey, String pValue) { key =pKey; value=pValue; } void insert(String pKey, String pValue) { if (pKey.compareTo(key)>0) { if (right == null) right = new Node(pKey, pValue); else right.insert(pKey, pValue); } else if (pKey.compareTo(key)<0) { if (left == null) left = new Node(pKey, pValue); else left.insert(pKey, pValue); } else System.out.println("Error : Duplicate Key ("+pKey+")"); } String get(String pKey) { if (pKey.compareTo(key) > 0) { if (right == null) return null; return right.get(pKey); } else if (pKey.compareTo(key) < 0) { if (left == null) return null; return left.get(pKey); } else return value; } public String toString() { String rzStr = "("+key+":"+value+" "; if (left != null) rzStr += "l="+left.toString(); if (right != null) rzStr += "r="+right.toString(); rzStr += ")"; return rzStr; } } 執行結果
|
page revision: 0, last edited: 05 Nov 2010 02:28
Post preview:
Close preview