點擊查看：2019考研計算機專業(yè)課核心考點總結(jié)匯總

　　2019考研計算機專業(yè)課核心考點總結(jié)(3)

　　從二叉樹結(jié)構(gòu)的整體看，二叉樹可以分為根結(jié)點，左子樹和右子樹三部分，只要遍歷了這三部分，就算遍歷了二叉樹。設(shè)D表示根結(jié)點，L表示左子樹，R表示右子樹，則DLR的組合共有6種，即DLR，DRL，LDR，LRD，RDL，RLD。若限定先左后右，則只有DLR，LDR，LRD三種，分別稱為先(前)序法(先根次序法)，中序法(中根次序法，對稱法)，后序法(后根次序法)。三種遍歷的遞歸算法如下：

　　1.先序法(DLR)

　　若二叉樹為空，則空操作，否則：訪問根結(jié)點?先序遍歷左子樹?先序遍歷右子樹。

　　2.中序法(LDR)

　　若二叉樹為空，則空操作，否則：中序遍歷左子樹?訪問根結(jié)點?中序遍歷右子樹.

　　3.后序法(LRD)

　　若二叉樹為空，則空操作，否則：后序遍歷左子樹?后序遍歷右子樹?訪問根結(jié)點.

　　核心考點四：完全二叉樹中有關(guān)結(jié)點個數(shù)計算

　　完全二叉樹的定義：深度為k，有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。

　　完全二叉樹的葉子數(shù)為(n + 1) / 2取下整。

　　森林與二叉樹之間的轉(zhuǎn)換以及轉(zhuǎn)換過程中結(jié)點之間的關(guān)系

　　將一棵樹轉(zhuǎn)換為二叉樹的方法是：

　　1.樹中所有相鄰兄弟之間加一條連線。

　　2.對樹中的每個結(jié)點，只保留其與第一個孩子結(jié)點之間的連線，刪去其與其它孩子結(jié)點之間的連線。

　　3.以樹的根結(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。

　　森林轉(zhuǎn)換為二叉樹的方法如下：

　　1.將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。

　　2.第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。

　　樹和森林都可以轉(zhuǎn)換為二叉樹，二者的不同是:樹轉(zhuǎn)換成的二叉樹,其根結(jié)點必然無右孩子，而森林轉(zhuǎn)換后的二叉樹，其根結(jié)點有右孩子。將一棵二叉樹還原為樹或森林，具體方法如下：

　　1.若某結(jié)點是其雙親的左孩子，則把該結(jié)點的右孩子、右孩子的右孩子、……都與該結(jié)點 的雙親結(jié)點用線連起來。

　　2.刪掉原二叉樹中所有雙親結(jié)點與右孩子結(jié)點的連線。3.整理由1、2兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。

　　核心考點六：對無向連通圖特性的理解

　　無向圖的每條邊，在頂點計算度的過程中，都要兩次參與計算(與邊兩關(guān)聯(lián)的2個頂點)，因此所有頂點的度之和為偶數(shù)。

　　具有n個頂點的無向連通圖，其邊數(shù)大于或等于n-1。

　　在無向連通圖中，所有頂點的度數(shù)都有可能大于1。

　　對m階B樹定義的理解

　　一棵m階的B樹滿足下列條件：

　　1.每個結(jié)點至多有m棵子樹。

　　2.除根結(jié)點外，其它每個分支至少有m/2棵子樹。

　　3.根結(jié)點至少有兩棵子樹(除非B樹只有一個結(jié)點)。

　　4.所有葉結(jié)點在同一層上。B樹的葉結(jié)點可以看成一種外部結(jié)點，不包含任何信息。

　　5.有j個孩子的非葉結(jié)點恰好有j-1個關(guān)鍵碼，關(guān)鍵碼按遞增次序排列。結(jié)點中包含的信息為 ∶(p0,k1,p1,k2,p2, … ,kj-1,pj-1)，其中，ki為關(guān)鍵碼。

　　相關(guān)推薦：

　　2019年考研數(shù)學(xué)常微分方程練習(xí)題及答案

　　2019考研英語基礎(chǔ)階段完型填空練習(xí)題匯總

　　2019考研政治《思修法基》練習(xí)試題及答案匯總