2020年計算機考研復習已經開始，新東方在線在此整理了2020考研計算機《數據結構(C語言版)》復習筆記(6)，希望能幫助大家!

第六章 樹知識點整理

樹是n個結點的有限集合，非空時必須滿足：只有一個稱為根的結點;其余結點形成m個不相交的子集，并稱根的子樹。

根是開始結點;結點的子樹數稱度;度為0的結點稱葉子(終端結點);度不為0的結點稱分支結點(非終端結點);除根外的分支結點稱內部結點;

有序樹是子樹有左，右之分的樹;無序樹是子樹沒有左，右之分的樹;森林是m個互不相交的樹的集合;

樹的四種不同表示方法：·樹形表示法;·嵌套集合表示法;·凹入表示法·廣義表表示法。

二叉樹的定義：是n≥0個結點的有限集，它是空集(n=0)或由一個根結點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成。

二叉樹不是樹的特殊情形，與度數為2的有序樹不同。

二叉樹的4個重要性質： ·二叉樹上第i層上的結點數目最多為2^(i-1)(i≥1)。;

·深度為k的二叉樹至多有(2^k)-1個結點(k≥1);

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

·具有n個結點的完全二叉樹的深度為int(log2n)+1.

滿二叉樹是一棵深度為k，結點數為(2^k)-1的二叉樹;完全二叉樹是滿二叉樹在最下層自右向左去處部分結點;

二叉樹的順序存儲結構就是把二叉樹的所有結點按照層次順序存儲到連續的存儲單元中。(存儲前先將其畫成完全二叉樹)

樹的存儲結構多用的是鏈式存儲。BinTNode的結構為lchild|data|rchild，把所有BinTNode類型的結點，加上一個指向根結點的BinTree型頭指針就構成了二叉樹的鏈式存儲結構，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域，n+1個空指針。

根據訪問結點的次序不同可得三種遍歷：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。時間復雜度為O(n)。

利用二叉鏈表中的n+1個空指針域來存放指向某種遍歷次序下的前趨結點和后繼結點的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡單有效，但對于查找指定結點的前序前趨和后序后繼并沒有什么作用。

樹和森林及二叉樹的轉換是唯一對應的。

轉換方法： ·樹變二叉樹：兄弟相連，保留長子的連線。

·二叉樹變樹：結點的右孩子與其雙親連。

·森林變二叉樹：樹變二叉樹，各個樹的根相連。

樹的存儲結構：·有雙親鏈表表示法：結點data | parent，對于求指定結點的雙親或祖先十分方便，但不適于求指定結點的孩子及后代。

·孩子鏈表表示法：為樹中每個結點data | next設置一個孩子鏈表firstchild，并將data |

firstchild存放在一個向量中。

·雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結合。

·孩子兄弟鏈表表示法：結點結構leftmostchild |data |

rightsibing，附加兩個分別指向該結點的最左孩子和右鄰兄弟的指針域。

樹的前序遍歷與相對應的二叉樹的前序遍歷一致;樹的后序遍歷與相對應的二叉樹的中序遍歷一致。

樹的帶權路徑長度是樹中所有葉結點的帶權路徑長度之和。樹的帶權路徑長度最小的二叉樹就稱為最優二叉樹(即哈夫曼樹)。

在葉子的權值相同的二叉樹中，完全二叉樹的路徑長度最短。

哈夫曼樹有n個葉結點，共有2n-1個結點，沒有度為1的結點，這類樹又稱為嚴格二叉樹。

變長編碼技術可以使頻度高的字符編碼短，而頻度低的字符編碼長，但是變長編碼可能使解碼產生二義性。如00、01、0001這三個碼無法在解碼時確定是哪一個，所以要求在字符編碼時任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼(其實是非前綴碼)。

哈夫曼樹的應用最廣泛地是在編碼技術上，它能夠容易地求出給定字符集及其概率分布的最優前綴碼。哈夫曼編碼的構造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼0，右路徑上寫代碼1，然后從上到下到葉結點的相應路徑上的代碼的序列就是該結點的最優前綴碼。

總結

以上是生活随笔為你收集整理的数据结构(c语言版)笔记6,2020考研计算机《数据结构(C语言版)》复习笔记(6)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。