考研計算機沖刺講解:數(shù)據(jù)結(jié)構(gòu)之二叉樹遍歷_跨考網(wǎng)
?????? 二叉樹是數(shù)據(jù)結(jié)構(gòu)中的重點內(nèi)容,在這兩年的考試中也將二叉樹作為重點內(nèi)容來考查。二叉樹這部分內(nèi)容要求大家掌握二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)、遍歷、線索化、森林和二叉樹的轉(zhuǎn)換等內(nèi)容。算法的重點是二叉樹的遍歷及其應用,這也是二叉樹這部分的重點和難點。遍歷是二叉樹各種操作的基礎(chǔ),可以在遍歷過程中對結(jié)點進行各種操作。例如:求二叉樹結(jié)點總數(shù),建立二叉樹,建立二叉樹的存儲結(jié)構(gòu)等。二叉樹的很多算法是在遍歷算法基礎(chǔ)上改造完成的,這就要求大家在復習時,熟練掌握二叉樹遍歷的遞歸和非遞歸算法。
下面,介紹一下二叉樹的幾種遍歷方法:
由二叉樹的定義可知,一顆二叉樹由根節(jié)點及左、右子樹三個基本部分組成,因此,只要依次遍歷這三部分,就可以遍歷整個二叉樹。
1.先序遍歷
先序遍歷的遞歸過程為:若二叉樹為空,遍歷結(jié)束。否則,
(1)訪問根節(jié)點;
(2)先序遍歷根節(jié)點的左子樹;
(3)先序遍歷根節(jié)點的右子樹。
2.中序遍歷
中序遍歷的遞歸過程為:若二叉樹為空,遍歷結(jié)束。否則,
(1)中序遍歷根節(jié)點的左子樹;
(2)訪問根節(jié)點;
(3)中序遍歷根節(jié)點的右子樹。
3.后序遍歷
后序遍歷的遞歸過程為:若二叉樹為空,遍歷結(jié)束。否則,
(1)后序遍歷根節(jié)點的左子樹;
(2)后序遍歷根節(jié)點的右子樹;
(3)訪問根節(jié)點。
層次遍歷
二叉樹的層次遍歷,是指從二叉樹的第一層(根結(jié)點)開始,從上至下逐層遍歷,在同一層中,則按從左到右的順序?qū)Y(jié)點逐個訪問。在進行層次遍歷時,對一層結(jié)點訪問完后,再按照它們的訪問次序?qū)Ω鱾€結(jié)點的左孩子和右孩子順序訪問,這樣一層一層進行,先遇到的結(jié)點先訪問,這與隊列的操作原則比較吻合。因此,在進行層次遍歷時,可設置一個隊列結(jié)構(gòu),遍歷從二叉樹的根結(jié)點開始,首先將根結(jié)點指針入隊列,然后從對頭取出一個元素,每取一個元素,執(zhí)行下面兩個操作:
(1)訪問該元素所指結(jié)點;
(2)若該元素所指結(jié)點的左、右孩子結(jié)點非空,則將該元素所指結(jié)點的左孩子指針和右孩子指針順序入隊。
此過程不斷進行,當隊列為空時,二叉樹的層次遍歷結(jié)束。
下面大家來看二叉樹遍歷這部分在考試中常考題型:
1.由二叉樹的兩個遍歷序列的組合(先序序列和中序序列)、(中序序列和后序序列)、(層次序列和中序序列)構(gòu)造該二叉樹或求其他遍歷序列是一種常見的題型。需要注意的是已知二叉樹的先序序列和后序序列不能唯一確定該二叉樹。
2.以遍歷為基礎(chǔ)的二叉樹算法設計是考試的重點和難點。常見的試題有以下幾類:
(1)基于二叉樹遍歷的遞歸算法
這類題目的特點是直接根據(jù)三種遞歸算法改寫,修改訪問語句來實現(xiàn)。例如:求二叉樹的結(jié)點個數(shù)。
(2)基于二叉樹層次遍歷的算法
這類題目有求二叉樹的高度,求二叉樹最大寬度等。
(3)基于順序存儲的二叉樹遍歷算法
例如:求順序存儲的滿二叉樹中序遍歷的非遞歸算法。
(4)其他二叉樹遍歷算法
例如:左、右子樹交換等。
大家要重點掌握這些以遍歷為基礎(chǔ)的二叉樹算法題目,這就要求大家多做練習,通過習題訓練加深理解,掌握解題思路和技巧,提高解題能力。針對以上幾種算法題,大家可通過計算機學科專業(yè)基礎(chǔ)綜合輔導講義同步練習來準備相應的練習題并配有詳細的解答,掌握此部分內(nèi)容。
另外,現(xiàn)在大家開始沖刺復習了,選擇一本涵蓋全面、與真題題型一致、題目難度和真題難度高度相近,并對這兩年的考試試題進行了詳細分析的全真模擬試題集,是此時沖刺的最佳幫手,可以幫助你查缺補漏,顯著提高應試能力。
?
2022考研初復試已經(jīng)接近尾聲,考研學子全面進入2023屆備考,跨考為23考研的考生準備了10大課包全程準備、全年復習備考計劃、目標院校專業(yè)輔導、全真復試模擬練習和全程針對性指導;2023考研的小伙伴針也已經(jīng)開始擇校和復習了,跨考考研暢學5.0版本全新升級,無論你在校在家都可以更自如的完成你的考研復習,暑假集訓營帶來了院校專業(yè)初步選擇,明確方向;考研備考全年規(guī)劃,核心知識點入門;個性化制定備考方案,助你贏在起跑線,早出發(fā)一點離成功就更近一點!
點擊右側(cè)咨詢或直接前往了解更多
考研院校專業(yè)選擇和考研復習計劃 | |||
2023備考學習 | 2023線上線下隨時學習 | 34所自劃線院校考研復試分數(shù)線匯總 | |
2022考研復試最全信息整理 | 全國各招生院??佳袕驮嚪謹?shù)線匯總 | ||
2023全日制封閉訓練 | 全國各招生院??佳姓{(diào)劑信息匯總 | ||
2023考研先知 | 考研考試科目有哪些? | 如何正確看待考研分數(shù)線? | |
不同院校相同專業(yè)如何選擇更適合自己的 | 從就業(yè)說考研如何擇專業(yè)? | ||
手把手教你如何選專業(yè)? | 高校研究生教育各學科門類排行榜 |
相關(guān)推薦
跨考考研課程
班型 | 定向班型 | 開班時間 | 高定班 | 標準班 | 課程介紹 | 咨詢 |
秋季集訓 | 沖刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+專業(yè)課1對1+專業(yè)課定向輔導+協(xié)議加強課程(高定班)+專屬規(guī)劃答疑(高定班)+精細化答疑+復試資源(高定班)+復試課包(高定班)+復試指導(高定班)+復試班主任1v1服務(高定班)+復試面授密訓(高定班)+復試1v1(高定班) | |
2023集訓暢學 | 非定向(政英班/數(shù)政英班) | 每月20日 | 22800起(協(xié)議班) | 13800起 | 先行階在線課程+基礎(chǔ)階在線課程+強化階在線課程+真題階在線課程+沖刺階在線課程+專業(yè)課針對性一對一課程+班主任全程督學服務+全程規(guī)劃體系+全程測試體系+全程精細化答疑+擇校擇專業(yè)能力定位體系+全年關(guān)鍵環(huán)節(jié)指導體系+初試加強課+初試專屬服務+復試全科標準班服務 |