- 相關推薦
2023計算機二級考試《公共基礎》考點：樹和二叉樹
計算機二級考試是全國計算機等級考試四個等級中的一個等級，由教育部考試中心主辦，考核計算機基礎知識和使用一種高級計算機語言編寫程序以及上機調試的基本技能。下面是小編精心整理的2023計算機二級考試《公共基礎》考點：樹和二叉樹，歡迎大家分享。
計算機二級考試《公共基礎》考點：樹和二叉樹
1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種數據結構中，所有數據元素之間的關系具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點。沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的后件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
(1)什么是二叉樹
二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1)非空二叉樹只有一個根結點;2)每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
根據二叉樹的概念可知，二叉樹的度可以為0(葉結點)、1(只有一棵子樹)或2(有2棵子樹)。
(2)二叉樹的基本性質(學吧學吧獨家稿件)
性質1 在二叉樹的第k層上，最多有2k-1(k≥1)個結點。
性質2 深度為m的二叉樹最多有個2m-1個結點。
性質3 在任意一棵二叉樹中，度數為0的結點(即葉子結點)總比度為2的結點多一個。
性質4 具有n個結點的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示取log2n的整數部分。
3、滿二叉樹與完全二叉樹
滿二叉樹：除最后一層外，每一層上的所有結點都有兩個子結點。
完全二叉樹：除最后一層外，每一層上的結點數均達到最大值;在最后一層上只缺少右邊的若干結點。
根據完全二叉樹的定義可得出：度為1的結點的個數為0或1。
性質5 具有n個結點的完全二叉樹深度為[log2n]+1。
性質6 設完全二叉樹共有n個結點，如果從根結點開始，按層序(每一層從左到右)用自然數1，2，…，n給結點進行編號，則對于編號為k(k=1，2，…，n)的結點有以下結論：
①若k=1，則該結點為根結點，它沒有父結點;若k>1，則該結點的父結點的編號為INT(k/2)。
②若2k≤n，則編號為k的左子結點編號為2k;否則該結點無左子結點(顯然也沒有右子結點)。
③若2k+1≤n，則編號為k的右子結點編號為2k+1;否則該結點無右子結點。
4、二叉樹的存儲結構
在計算機中，二叉樹通常采用鏈式存儲結構。
與線性鏈表類似，用于存儲二叉樹中各元素的存儲結點也由兩部分組成：數據域和指針域。但在二叉樹中，由于每一個元素可以有兩個后件(即兩個子結點)，因此，用于存儲二叉樹的存儲結點的指針域有兩個：一個用于指向該結點的左子結點的存儲地址，稱為左指針域;另一個用于指向該結點的右子結點的存儲地址，稱為右指針域。
一般二叉樹通常采用鏈式存儲結構，對于滿二叉樹與完全二叉樹來說，可以按層序進行順序存儲(注釋1) 。
5、二叉樹的遍歷
二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種：
(1)前序遍歷(DLR)：若二叉樹為空，則結束返回。否則：首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹;并且，在遍歷左右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。
(2)中序遍歷(LDR)：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹;并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。
(3)后序遍歷(LRD)：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。
二級公共基礎知識之樹與二叉樹
1、什么是樹？
樹是一種簡單的非線性結構，直觀地來看，樹是以分支關系定義的層次結構。由于它呈現與自然樹類似的結構形式，所以稱它為樹。如圖所示
2、父節點（根）
一個節點只有一個前件地稱為父節點。沒有前件的節點只有一個，稱為樹的根節點，如上圖中的A即為樹的根。
3、子節點和葉子節點
一個節點可以有多個后件，其稱為該節點的子節點。沒有后件的節點稱為葉子節點，如上圖中的E、F、G即為葉子節點。
4、度
一個節點所擁有的后件樹稱為該節點的度，其中所有節點中最大的度稱為樹的度。如上圖中根節點A的度為3，節點B的度為2，節點D的度為1，節點E、F、C、G的度為0，所以該樹的度為3.
5、深度
定義一棵樹的根節點所在的層次為1，其他節點所在層次等于他的父節點所在層次加一。樹的最大層次稱為樹的深度。如上圖根節點A在第1層，節點B、C、D在第2層，節點E、F、G在第3層，所以此樹的深度為3。
6、子樹
在樹中，以某節點的一個子節點為根構成的樹稱為該節點的一顆子樹。如上圖中節點A有3棵子樹，它們分別以B、C、D為根節點。其中以C為根節點的子樹實際上只有根節點一個節點，樹的葉子節點度為0，所以沒有子樹。
7、二叉樹
二叉樹是一個有限的節點集合，該集合或者為空，或者由一個根節點及其兩顆互不相交的左右二叉子樹所組成。其中又有滿二叉樹（所有節點都有兩個子節點，葉子節點除外）和完全二叉樹(最后一層只缺少右邊的若干節點)兩種特殊形態的二叉樹。有它們的定義可知，滿二叉樹一定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。
了解了相關概念后，我們再來看看二叉樹有哪些性質吧
性質一：在二叉樹的第N層上，最多有2的n-1次方（N≥1）個節點。
性質二：深度為N的二叉樹中，最多有2的N次方-1個節點。
性質三：對任何一顆二叉樹，度為0的節點（即葉子節點）總比度為2的節點多1個。
性質四：具有n個節點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分。
最后帶你們看看二叉樹的遍歷
二叉樹的遍歷是指不重復地訪問二叉樹中的所有節點。可以分為前序遍歷、中序遍歷、后序遍歷3種。
前序遍歷中“前”的含義是訪問根節點在訪問左節點和右節點之前。即先訪問根節點，然后遍歷左子樹，最后遍歷右子樹。
中序遍歷中“中”的含義是訪問根節點在訪問左子樹和訪問右子樹兩者之間。即首先遍歷左子樹，然后訪問根節點，最后遍歷右子樹。并且在遍歷左子樹和右子樹時，仍然首先遍歷左子樹，然后訪問根節點，最后遍歷右子樹。
后序遍歷中“后”的含義是訪問根節點在訪問左子樹和訪問右子樹之后。即首先遍歷左子樹，然后遍歷右子樹，最后訪問根節點；并且在遍歷左子樹和右子樹時，仍然首先遍歷左子樹，然后遍歷右子樹，最后訪問根節點。
【計算機二級考試《公共基礎》考點：樹和二叉樹】相關文章：
計算機二級考試《公共基礎》考點：棧和隊列05-28
計算機二級考試《公共基礎知識》考點06-05
2015計算機二級考試《公共基礎》考點：程序設計風格07-25
2016年計算機二級考試公共基礎考點知識10-20
計算機二級考試《公共基礎》100題07-02
銀行從業考試公共基礎考點：貸款05-27