重溫數據結構：樹 及 Java 實現(轉)

轉自：http://blog.csdn.net/u011240877/article/details/53193877

讀完本文你將了解到：

• • 什么是樹
  • 樹的相關術語
    • 根節點父親節點孩子節點葉子節點如上所述
    • 節點的度
    • 樹的度
    • 節點的層次
    • 樹的高度
    • 樹的深度
  • 樹的兩種實現
    • 數組表示
    • 鏈表表示的節點
  • 樹的幾種常見分類及使用場景

?

數據結構，指的是數據的存儲形式，常見的有線性結構（數組、鏈表，隊列、棧），還有非線性結構（樹、圖等）。

今天我們來學習下數據結構中的?樹。

什么是樹

線性結構中，一個節點至多只有一個頭節點，至多只有一個尾節點，彼此連接起來是一條完整的線。

比如鏈表和數組：

而樹，非線性結構的典型例子，不再是一對一，而變成了一對多（而圖則可以是 多對多），如下圖所示：

可以看到:

• 圖中的結構就像一棵倒過來的樹，最頂部的節點就是“根節點 (root 節點)”
• 每棵樹至多只有一個根節點
• 根節點生出多個孩子節點，每個孩子節點只有一個父節點，每個孩子節點又生出多個孩子
• 父親節點 (parent) 和孩子節點 (child) 是相對的
• 沒有孩子節點的節點成為葉子節點 (leaf)

樹的相關術語

根節點、父親節點、孩子節點、葉子節點如上所述。

節點的度

一個節點直接含有的子樹個數，叫做節點的度。比如上圖中的 3 的度是 2，10 的度是 1。

樹的度

一棵樹中?最大節點的度，即哪個節點的子節點最多，它的度就是 樹的度。上圖中樹的度為 2 。

節點的層次

從根節點開始算起，根節點算第一層，往后底層。比如上圖中，3 的層次是 2，4 的層次是 4。

樹的高度

樹的高度是從葉子節點開始，自底向上增加。

樹的深度

與高度相反，樹的深度從根節點開始，自頂向下增加。

整個樹的高度、深度是一樣的，但是中間節點的高度 和 深度是不同的，比如上圖中的 6 ，高度是 2 ，深度是 3。

樹的兩種實現

從上述概念可以得知，樹是一個遞歸的概念，從根節點開始，每個節點至多只有一個父節點，有多個子節點，每個子節點又是一棵樹，以此遞歸。

樹有兩種實現方式：

• 數組
• 鏈表

數組表示：

我們可以利用每個節點至多只有一個父節點這個特點，使用?父節點表示法?來實現一個節點：

public class TreeNode {private Object mData;   //存儲的數據private int mParent;   //父親節點的下標public TreeNode(Object data, int parent) {mData = data;mParent = parent;}public Object getData() {return mData;}public void setData(Object data) {mData = data;}public int getParent() {return mParent;}public void setParent(int parent) {mParent = parent;}
}

　　

上述代碼中，使用 角標 來指明父親節點的位置，使用這個節點組成的數組就可以表示一棵樹。

public static void main(String[] args){TreeNode[] arrayTree = new TreeNode[10];
}

　　

用數組實現的樹表示下面的樹，（其中一種 ）結果就是這樣的：

數組實現的樹節點使用角標表示父親的索引，下面用鏈表表示一個節點和一棵樹：

鏈表表示的節點：

public class LinkedTreeNode {private Object mData;   //存儲的數據private LinkedTreeNode mParent;   //父親節點的下標private LinkedTreeNode mChild;  //孩子節點的引用public LinkedTreeNode(Object data, LinkedTreeNode parent) {mData = data;mParent = parent;}public Object getData() {return mData;}public void setData(Object data) {mData = data;}public Object getParent() {return mParent;}public void setParent(LinkedTreeNode parent) {mParent = parent;}public LinkedTreeNode getChild() {return mChild;}public void setChild(LinkedTreeNode child) {mChild = child;}}

　　

使用引用，而不是索引表示父親與孩子節點。

使用一個 List, 元素是 LinkedTreeNode，就可以表示一棵鏈表樹：

public static void main(String[] args){LinkedList<LinkedTreeNode> linkedTree = new LinkedList<>();
}

　　

這樣只需知道 根節點就可以遍歷整個樹。知道某個節點也可以獲取它的父親和孩子。

樹的幾種常見分類及使用場景

樹，為了更好的查找性能而生。

常見的樹有以下幾種分類：

• 二叉樹
• 平衡二叉樹
• B 樹
• B+ 樹
• 哈夫曼樹
• 堆
• 紅黑樹

接下來陸續介紹完回來補使用場景。