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