基本數(shù)據(jù)結構：樹（tree）

作者：C小加 更新時間：2012-8-3

無論是鏈表，棧還是隊列，它們都是線性結構的，每個節(jié)點的左邊最多一個節(jié)點，右邊也最多一個節(jié)點，對于大量的輸入數(shù)據(jù)，線性表的訪問時間太慢，不宜使用。這里我要說一種非線性的數(shù)據(jù)結構，其大部分操作的運行時間平均為O(logn)。

我們涉及到的這種數(shù)據(jù)結構叫做樹。在計算機科學中，樹是非常有用的抽象概念。我們形象的去描述一棵樹，一個家族的老祖可能有兩個兒子，這兩個兒子一個有一個兒子，一個有三個兒子，像這樣發(fā)展下去的一個族譜，就是一個樹，如圖1所示。

就像一棵真正的樹一樣，我們把老祖稱為樹根,兩個字兒是分叉開的兩個樹枝，這兩棵樹枝可以繼續(xù)向下分成N個樹枝，循環(huán)下去，一直到長出葉子為止。

我們把老祖或者樹根稱為根（root）節(jié)點，老祖的兒子稱為子節(jié)點，每個兒子作為根節(jié)點又可以形成一棵樹，我們把這樣的樹稱為根節(jié)點的子樹。

樹的標準定義：

樹（tree）是包含n（n>0）個節(jié)點的有窮集合，其中：

　　（1）每個元素稱為節(jié)點（node）；

　　（2）有一個特定的節(jié)點被稱為根節(jié)點或樹根（root）。

（3）除根節(jié)點之外的其余數(shù)據(jù)元素被分為m（m≥0）個互不相交的結合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。

樹具有以下特點：

（1）    每個節(jié)點有零個或多個子節(jié)點。

（2）    每個子節(jié)點只有一個父節(jié)點。

（3）    沒有父節(jié)點的節(jié)點稱為根節(jié)點。

關于樹的一些術語

        節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度；

        葉節(jié)點或終端節(jié)點：度為零的節(jié)點稱為葉節(jié)點；

        非終端節(jié)點或分支節(jié)點：度不為零的節(jié)點；

        雙親節(jié)點或父節(jié)點：若一個結點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；

        孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；

        兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；

        樹的高度或深度：定義一棵樹的根結點層次為1，其他節(jié)點的層次是其父結點層次加1。一棵樹中所有結點的層次的最大值稱為這棵樹的深度。節(jié)點的層次：從根開始定義起，根為第1層，根的子結點為第2層，以此類推；

        樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；

        節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；

        子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。

        森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

樹的實現(xiàn)

節(jié)點的代碼如下:

樹的應用

       大部分操作系統(tǒng)的目錄結構就是采用樹結構。

       樹的種類有很多，樹所擴展出來的很多數(shù)據(jù)結構都有著很大的作用，比如說紅黑樹，B樹，后綴樹等等，這將在日后寫到。