Posted on 2012-08-03 09:18
C小加 閱讀(10051)
評論(2) 編輯 收藏 引用 所屬分類:
數據結構和算法
基本數據結構：樹（tree）
作者：C小加 更新時間：2012-8-3
無論是鏈表，棧還是隊列，它們都是線性結構的，每個節點的左邊最多一個節點，右邊也最多一個節點，對于大量的輸入數據，線性表的訪問時間太慢，不宜使用。這里我要說一種非線性的數據結構，其大部分操作的運行時間平均為O(logn)。
我們涉及到的這種數據結構叫做樹。在計算機科學中，樹是非常有用的抽象概念。我們形象的去描述一棵樹，一個家族的老祖可能有兩個兒子，這兩個兒子一個有一個兒子，一個有三個兒子，像這樣發展下去的一個族譜，就是一個樹，如圖1所示。
就像一棵真正的樹一樣，我們把老祖稱為樹根,兩個字兒是分叉開的兩個樹枝，這兩棵樹枝可以繼續向下分成N個樹枝，循環下去，一直到長出葉子為止。
我們把老祖或者樹根稱為根（root）節點，老祖的兒子稱為子節點，每個兒子作為根節點又可以形成一棵樹，我們把這樣的樹稱為根節點的子樹。
樹的標準定義：
樹（tree）是包含n（n>0）個節點的有窮集合，其中：
（1）每個元素稱為節點（node）；
（2）有一個特定的節點被稱為根節點或樹根（root）。
（3）除根節點之外的其余數據元素被分為m（m≥0）個互不相交的結合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。
樹具有以下特點：
（1） 每個節點有零個或多個子節點。
（2） 每個子節點只有一個父節點。
（3） 沒有父節點的節點稱為根節點。
關于樹的一些術語
節點的度：一個節點含有的子樹的個數稱為該節點的度；
葉節點或終端節點：度為零的節點稱為葉節點；
非終端節點或分支節點：度不為零的節點；
雙親節點或父節點：若一個結點含有子節點，則這個節點稱為其子節點的父節點；
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；
兄弟節點：具有相同父節點的節點互稱為兄弟節點；
樹的高度或深度：定義一棵樹的根結點層次為1，其他節點的層次是其父結點層次加1。一棵樹中所有結點的層次的最大值稱為這棵樹的深度。節點的層次：從根開始定義起，根為第1層，根的子結點為第2層，以此類推；
樹的度：一棵樹中，最大的節點的度稱為樹的度；
節點的祖先：從根到該節點所經分支上的所有節點；
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。
森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
樹的實現
節點的代碼如下:
struct treenode
{
int data;
struct treenode *fistchild;//第一個兒子
struct treenode *nextsibling;//下一個兄弟
}
樹的應用
大部分操作系統的目錄結構就是采用樹結構。
樹的種類有很多，樹所擴展出來的很多數據結構都有著很大的作用，比如說紅黑樹，B樹，后綴樹等等，這將在日后寫到。