資料結構 -- 二元樹

訊息

參考文獻

簡體版

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

執行結果

D:\myweb\teach\Algorithm>javac Tree.java

D:\myweb\teach\Algorithm>java Tree
Insert 5:55
Insert 7:77
Insert 3:33
Insert 1:11
Insert 6:66
Insert 4:44
Insert 2:22
Insert 5:55
Error : Duplicate Key (5)
(5:55 l=(3:33 l=(1:11 r=(2:22 ))r=(4:44 ))r=(7:77 l=(6:66 )))
33
55
null

Facebook

page revision: 0, last edited: 05 Nov 2010 02:28

Edit Rate (0) Tags Discuss (0) History Files Print Site tools + Options

金門大學：免費電子書、教材、程式、動畫

訊息

範例：二元樹

Facebook

Facebook

Wikidot

Post preview:

Other interesting sites