6.1 樹的概念
樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)卜高，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合殴瘦。它是由n（n>=1）個有限節(jié)點組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹慰技，也就是說它是根朝上阴挣，而葉朝下的年栓。它具有以下的特點：
每個節(jié)點有零個或多個子節(jié)點；沒有父節(jié)點的節(jié)點稱為根節(jié)點糜烹；每一個非根節(jié)點有且只有一個父節(jié)點违诗；除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹
樹的術(shù)語：
（1）節(jié)點的度：各個節(jié)點所含有的子樹的個數(shù)
（2）樹的度：最大的節(jié)點的度
（3）葉節(jié)點：度為0的節(jié)點
（4）父節(jié)點：一個節(jié)點含有子節(jié)點疮蹦，則這個節(jié)點為父節(jié)點
（5）孩子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點诸迟。
（6）兄弟節(jié)點：具有相同父節(jié)點的節(jié)點成為兄弟節(jié)點。
（7）節(jié)點的層次；
（8）樹的高度或深度：樹節(jié)點的最大層次阵苇。
（9）堂兄弟節(jié)點：父節(jié)點在同一層的節(jié)點互為堂兄弟壁公。
（10）節(jié)點的祖先；子孫绅项；森林等
樹的種類：
（1）無序樹
（2）有序樹
? ? ? ? 二叉樹紊册，每個節(jié)點最多含有兩個子樹的樹
? ? ? ? 完全二叉樹：深度為d的樹，除了最后一層外趁怔，其它各層的節(jié)點數(shù)目已經(jīng)達到了最大值湿硝。
? ? ? ? 滿二叉樹：除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹
? ? ? ? 平衡二叉樹：任何節(jié)點的兩棵子樹的高度差不大于1。
? ? ? ? 排序二叉樹：二叉搜索樹润努、有序二叉樹.
霍夫曼樹：帶權(quán)路徑最短的二叉樹关斜，稱為了哈夫曼樹或最優(yōu)二叉樹。
B樹：一種對讀寫操作進行優(yōu)化的自平衡的二叉樹铺浇。
樹可以和我們的順序存儲與鏈式存儲相互結(jié)合痢畜。
6.2 二叉樹
二叉樹是指：每個節(jié)點最多有兩個子樹的結(jié)構(gòu)
二叉樹的性質(zhì)：
（1）在二叉樹的第i層上最多有 2^(i-1) 棵樹
（2）深度為k的二叉樹最多有? 2^k-1 個節(jié)點
（3）具有n個結(jié)點的完全二叉樹的深度必為 log2(n+1)
（4）具有n個結(jié)點的完全二叉樹的深度必為 log2(n+1)
（5）對完全二叉樹，若從上至下鳍侣、從左至右編號丁稀，則編號為i 的結(jié)點，其左孩子編號必為2i倚聚，其右孩子編號必為2i＋1线衫；其雙親的編號必為i/2（i＝1 時為根,除外
6.3 二叉樹的節(jié)點表示以及樹的創(chuàng)建
樹的遍歷包括了
前序遍歷（根節(jié)點，左節(jié)點惑折，右節(jié)點）
中序遍歷（左節(jié)點授账，根節(jié)點，右節(jié)點）
后序遍歷（左節(jié)點惨驶，右節(jié)點白热，根節(jié)點）
層次遍歷（從上到下，從左到右）
