樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)現(xiàn)這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。

它是由n（n>0）個有限節(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：

• 每個節(jié)點(diǎn)都只有有限個子節(jié)點(diǎn)或無子節(jié)點(diǎn)；

• 沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；

• 每一個非根節(jié)點(diǎn)有且只有一個父節(jié)點(diǎn)；

• 除了根節(jié)點(diǎn)外，每個子節(jié)點(diǎn)可以分為多個不相交的子樹；

• 樹里面沒有環(huán)路(cycle)

為什么需要樹

因?yàn)樗Y(jié)合了另外兩種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)：一種是有序數(shù)組，另一種是鏈表。在樹中查找數(shù)據(jù)項(xiàng)的速度和在有序數(shù)組中查找一樣快， 并且插入數(shù)據(jù)項(xiàng)和刪除數(shù)據(jù)項(xiàng)的速度也和鏈表一樣。

都有哪些樹

樹的種類有很多，我們接觸到的樹有二叉樹、平衡二叉樹、二叉查找樹、B樹、B+樹、哈夫曼樹、B*樹、紅黑樹和trie樹等。

樹的實(shí)現(xiàn)

樹是一種遞歸結(jié)構(gòu)，表示方式一般有孩子表示法和孩子兄弟表示法兩種。樹實(shí)現(xiàn)方式有很多種、有可以由廣義表的遞歸實(shí)現(xiàn)，也可以有二叉樹實(shí)現(xiàn)，其中最常見的是將樹用孩子兄弟表示法轉(zhuǎn)化成二叉樹來實(shí)現(xiàn)。

實(shí)現(xiàn)代碼：

publicclass treeNode<T> {
? public T t;
? private treeNode<T> parent;
? ?
? public List<treeNode<T>> nodelist;
? ?
? public treeNode(T stype){
? ? t ? = stype;
? ? parent = null;
? ? nodelist = new ArrayList<treeNode<T>>();
? }
?
? public treeNode<T> getParent() {
? ? return parent;
? } ?
}


publicclass tree<T> {
? ?
? public treeNode<T> root;
? ?
? public tree(){}
? ? ?
? public void addNode(treeNode<T> node, T newNode){
? ? //增加根節(jié)點(diǎn)
? ? if(null == node){
? ? ? if(null == root){
? ? ? ? root = new treeNode(newNode);
? ? ? }
? ? }else{
? ? ? ? treeNode<T> temp = new treeNode(newNode);
? ? ? ? node.nodelist.add(temp);
? ? }
? }
? ?
? /* ?查找newNode這個節(jié)點(diǎn) */
? public treeNode<T> search(treeNode<T> input, T newNode){
? ?
? ? treeNode<T> temp = null;
? ? ?
? ? if(input.t.equals(newNode)){
? ? ? return input;
? ? }
? ? ?
? ? for(int i = 0; i < input.nodelist.size(); i++){
? ? ? ?
? ? ? temp = search(input.nodelist.get(i), newNode);
? ? ? ?
? ? ? if(null != temp){
? ? ? ? break;
? ? ? } ?
? ? }
? ? ?
? ? return temp;
? }
? ?
? public treeNode<T> getNode(T newNode){
? ? return search(root, newNode);
? }
? ?
? public void showNode(treeNode<T> node){
? ? if(null != node){
? ? ? //循環(huán)遍歷node的節(jié)點(diǎn)
? ? ? System.out.println(node.t.toString());
? ? ? ?
? ? ? for(int i = 0; i < node.nodelist.size(); i++){
? ? ? ? showNode(node.nodelist.get(i));
? ? ? } ? ? ?
? ? }
? }
}


public static void main(String[] args) {

? ? tree<String> tree = new tree();
? ? tree.addNode(null, "string");
? ? tree.addNode(tree.getNode("string"), "hello");
? ? tree.addNode(tree.getNode("string"), "world");
? ? tree.addNode(tree.getNode("hello"), "sinny");
? ? tree.addNode(tree.getNode("hello"), "fredric");
? ? tree.addNode(tree.getNode("world"), "Hi");
? ? tree.addNode(tree.getNode("world"), "York");
? ? tree.showNode(tree.root);
? ? System.out.println("end of the test");
? }
??? ? ? ? ??