【資料結構】樹與二叉樹的基本概念、結構特點及性質-有解無憂

前言：本章內容主要是資料結構中樹與二叉樹的基本概念、結構特點及性質的引入，

文章目錄

- - 樹的概念
  - - 樹的特點：
    - 樹的常用術語：
    - 樹的表示：
    - - 代碼創建：
    - 樹在實際中的應用：
  - 二叉樹的概念
  - 特殊的二叉樹
  - - 滿二叉樹
    - 完全二叉樹
  - 二叉樹的性質及其推導：
  - 練習題：
  - - - 習題1：
      - 習題2：
      - 習題3：

樹的概念

資料結構中的定義的樹比較有趣，它是我們所見真實樹的倒置，然后再抽象的一種結構，比較有意思，同時使用樹這種資料結構，可以描述現實生活中的很多事物，例如家譜、企業的組織架構等等，

樹是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，

樹的特點：

1.每個結點有零個或多個子結點；
2.沒有父結點的結點為根結點；
3.每一個非根結點只有一個父結點；
4.每個結點及其后代結點整體上可以看做是一棵樹，稱為當前結點的父結點的一個子樹；

樹的常用術語：

1.根結點:沒有雙親節點的結點

2.孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點

3.雙親結點：若一個節點含有子節點，則這個節點稱為其子節點的父節點

4.節點的度:一個節點含有的子樹的個數稱為該節點的度

5.葉結點：度為0的結點稱為葉結點，也可以叫做終端結點

6.分支結點：度不為0的結點稱為分支結點，也可以叫做非終端結點

7.結點的層次：從根結點開始，根結點的層次為1，根的直接后繼層次為2，以此類推

8.結點的層序編號：將樹中的結點，按照從上層到下層，同層從左到右的次序排成一個線性序列，把他們編成連續的自然數

9.樹的度：樹中所有結點的度的最大值

10.樹的高度(深度)：樹中結點的最大層次

11.森林：m（m>=0）個互不相交的樹的集合，將一顆非空樹的根結點刪去，樹就變成一個森林；給森林增加一個統一的根結點，森林就變成一棵樹

12.兄弟結點：同一雙親結點的孩子結點間互稱兄弟結點，

樹的表示：

“左孩子右兄弟”表示法

代碼創建：

typedef int DataType;

typedef struct node 
{
    struct node* child;       //指向左孩子結點
    struct node* brother;     //指向下一個兄弟結點
    DataType data;            //結構中的資料域，存盤當前結點資料
}node;

樹在實際中的應用：

比如檔案系統中的目錄結構

二叉樹的概念

一種特殊的樹,見名知意，只有兩個分叉的樹，特點是二叉樹的度最大只能為2,也就是說每個結點的子節點最多只能有兩個，

特殊的二叉樹

滿二叉樹

核心點是 “滿”

概念：每一層的結點都達到最大值**,且第n層的結點數量符合公式2^(n-1)**,層數是從1開始，

1.定義： 高度為h，并且含有(2^h)-1個結點的二叉樹
2.對于編號為 i 的結點，如果有雙親，雙親為 i/2 向下取整；如果有左孩子，左孩子編號為 2i，如果有右孩子，右孩子編號為 (2i + 1)

完全二叉樹

概念：對于層數(n>=2)的樹,其n-1層符合滿二叉樹,第n層結點必須滿足從左向右都連續，

比如：

1.若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹，
2.如果有度為 1 的結點，那只可能有一個，且該節點只有左孩子，而無右孩子

二叉樹的性質及其推導：

性質1：二叉樹第i層上的結點數目最多為 2^{i-1} (i≥1)

證明：下面用"數學歸納法"進行證明，
(01) 當i=1時，第i層的節點數目為2^{i-1}=2{0}=1，因為第1層上只有一個根結點，所以命題成立，
(02) 假設當i>1，第i層的節點數目為2^{i-1}，這個是根據(01)推斷出來的！
下面根據這個假設，推斷出"第(i+1)層的節點數目為2{i}“即可，
由于二叉樹的每個結點至多有兩個孩子，故"第(i+1)層上的結點數目” 最多是 “第i層的結點數目的2倍”，即，第(i+1)層上的結點數目最大值=2×2^{i-1}=2{i}，
故假設成立，原命題得證！

性質2：深度為k的二叉樹至多有2^{k}-1個結點(k≥1)

證明：在具有相同深度的二叉樹中，當每一層都含有最大結點數時，其樹中結點數最多，利用"性質1"可知，深度為k的二叉樹的結點數至多為：
2⁰⁺²1+…+2^k-1=2k-1
故原命題得證！

性質3：包含n個結點的二叉樹的高度至少為log2 (n+1)

證明：根據"性質2"可知，高度為h的二叉樹最多有2^h–1個結點，反之，對于包含n個節點的二叉樹的高度至少為log2(n+1)，

性質4：在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1

證明：因為二叉樹中所有結點的度數均不大于2，所以結點總數(記為n)=“0度結點數(n0)” + “1度結點數(n1)” + “2度結點數(n2)”，由此，得到等式一，
(等式一) n=n0+n1+n2
　另一方面，0度結點沒有孩子，1度結點有一個孩子，2度結點有兩個孩子，故二叉樹中孩子結點總數是：n1+2n2，此外，只有根不是任何結點的孩子，故二叉樹中的結點總數又可表示為等式二，
(等式二) n=n1+2n2+1
由(等式一)和(等式二)計算得到：n0=n2+1，原命題得證！

性質5：