第五章、樹與二叉樹

5.1.1_樹的定義和基本術(shù)語

樹的基本概念

結(jié)點、樹的屬性描述

有序樹vs無序樹

樹vs森林

思維導(dǎo)圖

5.1.2_樹的性質(zhì)

考點1

考點2

考點3

考點4

考點5

考點6

思維導(dǎo)圖

5.2.1_二叉樹的定義和基本術(shù)語

二叉樹的基本概念

二叉樹的五種狀態(tài)

幾個特殊的二叉樹

思維導(dǎo)圖

5.2.2_二叉樹的性質(zhì)

二叉樹的常考性質(zhì)

完全二叉樹的常考性質(zhì)

思維導(dǎo)圖

5.2.3_二叉樹的存儲結(jié)構(gòu)

二叉樹的順序存儲

二叉樹的鏈式存儲

思維導(dǎo)圖

5.3.1_二叉樹的先中后序遍歷

二叉樹的遍歷

先序遍歷

中序遍歷

后序遍歷

例：求樹的深度（應(yīng)用）

5.3.2_二叉樹的層序遍歷

二叉樹的層序遍歷

代碼實現(xiàn)

5.3.3_由遍歷序列構(gòu)造二叉樹

由遍歷序列構(gòu)造二叉樹

前+中

后+中

層+中

思維導(dǎo)圖

若不要中？

5.3.4_線索二叉樹的概念

二叉樹的中序遍歷序列

中序線索二叉樹

線索二叉樹的存儲

中序線索二叉樹的存儲

先序線索二叉樹

先序線索二叉樹的存儲

后序線索二叉樹

后序線索二叉樹的存儲

三種線索二叉樹的對比

思維導(dǎo)圖

5.3.5_二叉樹的線索化

用土方法找到中序前驅(qū)

中序線索化

先序線索化

思維導(dǎo)圖

5.3.6_在線索二叉樹中找前驅(qū)后繼

中序線索二叉樹找中序后繼

中序線索二叉樹找中序前驅(qū)

先序線索二叉樹找先序后繼

先序線索二叉樹找先序前驅(qū)

后序線索二叉樹找后序前驅(qū)

后序線索二叉樹找后序后繼

思維導(dǎo)圖

5.4.1_樹的存儲結(jié)構(gòu)

樹的邏輯結(jié)構(gòu)

雙親表示法（順序存儲）

回顧 ：二叉樹的順序存儲

孩子表示法（順序+鏈式存儲）

孩子兄弟表示法（鏈式存儲）

森林和二叉樹的轉(zhuǎn)換

思維導(dǎo)圖

5.4.2_樹和森林的遍歷

樹的先根遍歷

樹的后根遍歷

樹的層次遍歷

森林的先序遍歷

森林的中序遍歷

思維導(dǎo)圖

5.5.1_二叉排序樹 BST

二叉排序樹的定義

二叉排序樹的查找

二叉排序樹的插入

二叉排序樹的構(gòu)造

二叉排序樹的刪除

查找效率分析

思維導(dǎo)圖

5.5.2_平衡二叉樹 AVL

平衡二叉樹的定義

平衡二叉樹的插入

調(diào)整最小不平衡子樹

只需要調(diào)整最小不平衡子樹

查找效率分析

思維導(dǎo)圖

5.5.3_哈夫曼樹

帶權(quán)路徑長度

哈夫曼樹的定義

哈夫曼樹的構(gòu)造

• 結(jié)點的度是指擁有子結(jié)點的數(shù)量

哈夫曼編碼

思維導(dǎo)圖

總結(jié)

以上是生活随笔為你收集整理的王道计算机考研 数据结构 （树与二叉树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。