2019計算機考研專業(yè)課核心考點梳理(三)
從二叉樹結(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)鍵碼。
2022考研初復(fù)試已經(jīng)接近尾聲,考研學(xué)子全面進(jìn)入2023屆備考,跨考為23考研的考生準(zhǔn)備了10大課包全程準(zhǔn)備、全年復(fù)習(xí)備考計劃、目標(biāo)院校專業(yè)輔導(dǎo)、全真復(fù)試模擬練習(xí)和全程針對性指導(dǎo);2023考研的小伙伴針也已經(jīng)開始擇校和復(fù)習(xí)了,跨考考研暢學(xué)5.0版本全新升級,無論你在校在家都可以更自如的完成你的考研復(fù)習(xí),暑假集訓(xùn)營帶來了院校專業(yè)初步選擇,明確方向;考研備考全年規(guī)劃,核心知識點入門;個性化制定備考方案,助你贏在起跑線,早出發(fā)一點離成功就更近一點!
點擊右側(cè)咨詢或直接前往了解更多
考研院校專業(yè)選擇和考研復(fù)習(xí)計劃 | |||
2023備考學(xué)習(xí) | 2023線上線下隨時學(xué)習(xí) | 34所自劃線院??佳袕?fù)試分?jǐn)?shù)線匯總 | |
2022考研復(fù)試最全信息整理 | 全國各招生院??佳袕?fù)試分?jǐn)?shù)線匯總 | ||
2023全日制封閉訓(xùn)練 | 全國各招生院校考研調(diào)劑信息匯總 | ||
2023考研先知 | 考研考試科目有哪些? | 如何正確看待考研分?jǐn)?shù)線? | |
不同院校相同專業(yè)如何選擇更適合自己的 | 從就業(yè)說考研如何擇專業(yè)? | ||
手把手教你如何選專業(yè)? | 高校研究生教育各學(xué)科門類排行榜 |
跨考考研課程
班型 | 定向班型 | 開班時間 | 高定班 | 標(biāo)準(zhǔn)班 | 課程介紹 | 咨詢 |
秋季集訓(xùn) | 沖刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+專業(yè)課1對1+專業(yè)課定向輔導(dǎo)+協(xié)議加強課程(高定班)+專屬規(guī)劃答疑(高定班)+精細(xì)化答疑+復(fù)試資源(高定班)+復(fù)試課包(高定班)+復(fù)試指導(dǎo)(高定班)+復(fù)試班主任1v1服務(wù)(高定班)+復(fù)試面授密訓(xùn)(高定班)+復(fù)試1v1(高定班) | |
2023集訓(xùn)暢學(xué) | 非定向(政英班/數(shù)政英班) | 每月20日 | 22800起(協(xié)議班) | 13800起 | 先行階在線課程+基礎(chǔ)階在線課程+強化階在線課程+真題階在線課程+沖刺階在線課程+專業(yè)課針對性一對一課程+班主任全程督學(xué)服務(wù)+全程規(guī)劃體系+全程測試體系+全程精細(xì)化答疑+擇校擇專業(yè)能力定位體系+全年關(guān)鍵環(huán)節(jié)指導(dǎo)體系+初試加強課+初試專屬服務(wù)+復(fù)試全科標(biāo)準(zhǔn)班服務(wù) |