⑴ 數據結構樹和二叉樹有哪些實際應用
一個單位有10個部門，每個部門都有一部電話，但是整個單位只有一根外線，當有電話打過來的時候，由轉接員轉到內線電話，已知各部門使用外線電話的頻率為（次/天）
5 20 10 12 8 4 3 5 6 9
問應該如何設計個內線電話號碼，使得接線員撥號次數盡可能少？
這是哈夫曼樹的應用。
一種數據結構，用於保存和處理樹狀的數據，如家譜。
應用極為廣泛，因為根據數據結構的理論，任何復雜的樹夠可以轉換為二叉中並進行處理。
二叉樹再排序、查找、大規模數據索引方面有很多很多應用。
二叉樹排序是簡單演算法排序中速度最快的。
樹的一個大類是自平衡二叉搜索樹 (self-balanced BST), 變種特別多:RB 樹是每個節點是紅色或者黑色, 顏色隔代遺傳AVL 樹是每個節點包含平衡因子, 等於左高-右高Splay 樹是每個節點帶個父節點的指針Treap 是每個節點都帶個隨機的 priority number, parent priority >= child priority。
自平衡二叉搜索樹在面試中經常出現, 但做網頁的互聯網碼農卻很少用得上，如果是當 Map 用, 往往還不如直接上哈希表. 如果是當排序用, 不如直接用排序演算法... 不過也有有用的時候, 例如查找一個數字的上下界。
樹的另一個大類是 Trie, 特點是能保證字典序, 存儲詞典的空間壓縮率高, 能做前綴搜索. 在正則匹配, 數據壓縮, 構建索引都可能用到. Trie 也有不少變種:Double Array - trie 的一個經典實現。
每個節點可以存一段字元串而不限於一個字元Judy Array - 基於 256-ary radix tree, 用了 20 種壓縮方式, 極其復雜...Burst Trie - 如果一個子樹足夠小, 就用 binary 堆的方式存儲,。
不過壓縮效果一般HAT Trie - 壓縮率高而且不容易出現 CPU cache miss, 查速接近哈希表而耗內存少得多. 節點可以是以下三種之一: Array Hash, 序列化的 Bucket, 傳統 Trie nodeMARISA Trie - 壓縮率最高, 支持 mmap 載入, 也是用了很多壓縮技巧的復雜實現, 就是構建比較花時間, 也不能動態更新。
⑵ 用java實現二叉樹
我有很多個(假設10萬個)數據要保存起來，以後還需要從保存的這些數據中檢索是否存在某
個數據，（我想說出二叉樹的好處，該怎麼說呢？那就是說別人的缺點），假如存在數組中，
那麼，碰巧要找的數字位於99999那個地方，那查找的速度將很慢，因為要從第1個依次往
後取，取出來後進行比較。平衡二叉樹（構建平衡二叉樹需要先排序，我們這里就不作考慮
了）可以很好地解決這個問題，但二叉樹的遍歷（前序，中序，後序）效率要比數組低很多，
public class Node {
public int value;
public Node left;
public Node right;
public void store(intvalue)
right.value=value;
}
else
{
right.store(value);
}
}
}
public boolean find(intvalue)
{
System.out.println("happen" +this.value);
if(value ==this.value)
{
return true;
}
else if(value>this.value)
{
if(right ==null)returnfalse;
return right.find(value);
}else
{
if(left ==null)returnfalse;
return left.find(value);
}
}
public void preList()
{
System.out.print(this.value+ ",");
if(left!=null)left.preList();
if(right!=null) right.preList();
}
public void middleList()
{
if(left!=null)left.preList();
System.out.print(this.value+ ",");
if(right!=null)right.preList();
}
public void afterList()
{
if(left!=null)left.preList();
if(right!=null)right.preList();
System.out.print(this.value+ ",");
}
public static voidmain(String [] args)
{
int [] data =new int[20];
for(inti=0;i<data.length;i++)
{
data[i] = (int)(Math.random()*100)+ 1;
System.out.print(data[i] +",");
}
System.out.println();
Node root = new Node();
root.value = data[0];
for(inti=1;i<data.length;i++)
{
root.store(data[i]);
}
root.find(data[19]);
root.preList();
System.out.println();
root.middleList();
System.out.println();
root.afterList();
}
}
⑶ 數據結構二叉樹的好處
如果用2叉排序數來進行查找是比較方便的。二叉樹是一種最基本最典型的排序數，用於教學和研究樹的特性。