【自考】資料結構第四章樹和二叉樹，期末不掛科指南，第6篇-有解無憂

章節簡介

前5篇博客寫的都是線性結構，對于有層級結構的資料需要用樹形結構來描述

本章的重要知識點

理解有關樹的基本概念和二叉樹的基本概念
掌握二叉樹的存盤結構以及遍歷方法
掌握樹的存盤結構以及樹、森林、二叉樹的相互轉換方法
梳理掌握哈夫曼樹構造方法和哈夫曼編碼的設計方法

樹的基本概念

核心一句話

線性結構中一個結點至多只有一個直接后繼，樹形結構一個結點可以有一個或多個直接后繼

認識樹

看圖即可，你要能區分出來哪些是樹，哪些不是樹

樹的相關術語

結點的度：樹上任意結點所擁有的子樹的數目稱為該結點的度
葉子：度為0的結點稱為葉子或者終端結點
樹的度：一棵樹中所有結點的度的最大值稱為該樹的度，就是把所有結點的度求和
結點的層次：從根算起，根的層次為1，其余結點的層次為其雙親的層次加1
樹的高度：一棵樹中所有結點層次數的最大值稱為該樹的高度或深度
還有一些小概念：有序樹、無序樹

樹的相關術語，一定要一開始就明確清晰，后面才好學習

二叉樹

官方概念：二叉樹是n(n≥0)個元素的有限集合，該集合或者為空，或者由一個根及兩棵互不相交的左子樹和右子樹組成，其中左子樹和右子樹也均為二叉樹，二叉樹的任一結點都有兩棵子樹（它們中的任何一個都可以是空子樹），并且這兩棵子樹之間有次序關系，交換位置就成為一棵不同的二叉樹，

左子樹和右子樹，也有的叫做左孩子和右孩子

二叉樹五種基本形態，方塊表示子樹

二叉樹的基本運算（不寫代碼，了解重點函式即可）

初始化
求雙親
求左孩子
求右孩子
建二叉樹
先序遍歷！！！
中序遍歷！！！
后序遍歷！！！
層次遍歷！！！
先序遍歷，中序遍歷，后序遍歷在考試中一般不要求手寫代碼，但是需要你能通過一棵樹結構，輸出最終的結果，這個博客結尾給大家看一下例題

二叉樹性質（很重要，細碎知識點很多）

性質1：二叉樹第i(i≥1)層上至多有2^i-1個結點，

不需要死記硬背，實際需要的時候畫一個二叉樹就可以求出來了

性質2：深度為k（k≥1）的二叉樹至多有2^k-1個結點

依舊可以推匯出來
深度為1的二叉樹結點最多為1
深度為2的二叉樹結點最多為3
深度為3的二叉樹結點最多為7
深度為k的二叉樹結點最多為2^k-1

性質3：對任何一棵二叉樹，若度數為0的結點（葉結點）個數為n₀，度數為2的結點個數為n₂，則n₀ = n₂+1

這個性質需要稍微推導一下
先回答一個問題，你知道樹的度數，怎么計算樹的結點數
例如樹的度數為2，結點樹為幾，這個不難想象，會出現如下情況

看到這里不難發現，存在一個公式為樹的度數+1=樹的結點樹
那么我們開始推導上述公式
假設二叉樹的0度，1度，2度結點個數為n₀，n₁，n₂，結點總數為T
T = n₀+n₁+n₂
樹的度數+1 = T
樹的度數怎么求？n₀0+n₁1+n₂2 是樹的度數
繼續n₀0+n₁1+n₂2 +1 = T = n₀+n₁+n₂
===> 2n₂+1=n₀+n₂
===>n₀=n₂+1

好了，上述程序，爭取看明白吧

性質4：含有n個結點的完全二叉樹的深度為??log₂n??+1

這個地方引出了一個新的概念完全二叉樹

說明什么是完全二叉樹之前，需要理解什么是滿二叉樹

滿二叉樹
深度為k(k≥1)且有2^k-1個結點的二叉樹稱為滿二叉樹

完全二叉樹
如果對滿二叉樹按從上到下，從左到右的順序編號，并在最下一層洗掉去部分結點（洗掉最后一層仍有結點），如果洗掉的這些結點的編號是連續的且洗掉的結點中含有最大編號的結點，那么這棵二叉樹就是完全二叉樹
注意 ??x?? 這個符號，表示不大于x的最大整數

教材中，給了幾個范例，偷懶我用一下

關于性質4的證明，有興趣的自行研究一下吧

性質5：如果將一棵有n個結點的完全二叉樹按層編號，按層編號是指：將一棵二叉樹中的所有n個結點按照從第一層到最大層，每層從左到右的順序依次標記為1,2，....，n，則對任意編號i(1≤i≤n)的結點A有：
（1）若i=1，則結點A是根；若i＞1，則A的雙親編號為 ??i/2?? ，（注意 ??x?? 這個符號，表示不大于x的最大整數）
（2）若2*i＞n，則結點A既無左孩子，也無右孩子；否則A的左孩子的編號為2*i，
（3）若2*i+1＞n，則結點A無右孩子；否則，A的右孩子編號為2*i+1；

這個性質5有點意思，先驗證一下