22軟件工程《數(shù)據(jù)結(jié)構(gòu)與算法》第7周教學(xué)安排

講解第5章的內(nèi)容131、134-146頁(yè)

重點(diǎn)

1、樹(shù)的遍歷

2、二叉樹(shù)的邏輯結(jié)構(gòu)

3、二叉樹(shù)的性質(zhì)與練習(xí)

4、二叉樹(shù)的遍歷操作

（由中序遍歷和前（后）序遍歷推斷出一顆唯一的二叉樹(shù)）

3、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和遞歸算法

（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的程序?qū)崿F(xiàn)）

大家可以根據(jù)自己的情況進(jìn)行相應(yīng)的預(yù)習(xí)

師說(shuō)

為什么要有樹(shù)

一百個(gè)數(shù)字，無(wú)序排列，我們要根據(jù)已知的某個(gè)數(shù)字a，找到a在這一百個(gè)數(shù)字中的位置（也就是下標(biāo)），如何尋找?遍歷。假設(shè)100個(gè)數(shù)字可以每次遍歷，1萬(wàn)個(gè)可以每次遍歷，100萬(wàn)個(gè)還可以么?再計(jì)算遍歷的頻率，不好好掌握，簡(jiǎn)單的遍歷就可以把負(fù)責(zé)遍歷的人給忙死。

這時(shí)候人們開(kāi)始思考，怎么樣可以快速定位呢?很簡(jiǎn)單，如果插入的時(shí)候有順序，那么這樣的遍歷就變得非常簡(jiǎn)單。我們都知道1-100中間如果要找某個(gè)數(shù)字，我們肯定第一個(gè)判斷的是50這個(gè)數(shù)值與要定位的數(shù)字a的大小對(duì)比（因?yàn)橛行蛄?，所以大小?duì)比才有意義）。如果小于50，那么我們下一次會(huì)先判斷25，如果大于50，那么我們會(huì)判斷75……這就是常見(jiàn)的二分法，我們判斷出來(lái)要找的數(shù)字小于50時(shí)，我們就不需要去判斷50-100中間的這一堆數(shù)字，對(duì)比遍歷，我們就相當(dāng)于少了一半多工作量，一直循環(huán)下去，對(duì)比遍歷，遍歷的數(shù)據(jù)越多，效率越高。具體研究請(qǐng)自行百度 二分法 時(shí)間/空間復(fù)雜度，去得出結(jié)論。

編程中遇到這樣的問(wèn)題就有更多，因?yàn)椴檎业男蕠?yán)重影響我們系統(tǒng)反應(yīng)的時(shí)間。計(jì)算機(jī)中如何體現(xiàn)上文所述的二分法呢?聰明的人根據(jù)二分法的判斷順序，設(shè)計(jì)了一個(gè)有左子樹(shù)，右子樹(shù)的樹(shù)形結(jié)構(gòu)，命名為二叉樹(shù)。二叉樹(shù)必須有序，否則無(wú)序的二叉樹(shù)，數(shù)據(jù)來(lái)了都不知道要放在什么地方。

二叉樹(shù)（Binary Tree）的知識(shí)點(diǎn)是程序員面試的?？键c(diǎn)，所以平時(shí)更應(yīng)該注重這方面知識(shí)的積累。這篇文章主要涉及二叉樹(shù)的基礎(chǔ)知識(shí)和基礎(chǔ)操作，對(duì)初學(xué)者相當(dāng)于是一個(gè)引導(dǎo)。若想進(jìn)一步理解二叉樹(shù)相關(guān)的知識(shí)，可以找找相關(guān)的技術(shù)書(shū)籍參考學(xué)習(xí)。

數(shù)據(jù)來(lái)源:https://blog.csdn.net/chuogangrong4739/article/details/101053059

https://zhuanlan.zhihu.com/p/121602717

二叉樹(shù)常見(jiàn)面試題（https://www.cnblogs.com/33debug/p/7252371.html）

1. 求兩個(gè)節(jié)點(diǎn)的最近公共祖先；

2. 求二叉樹(shù)中最遠(yuǎn)的兩個(gè)結(jié)點(diǎn)的距離；

3. 由前序遍歷和中序遍歷重建二叉樹(shù)（如:前序序列:1 2 3 4 5 6 - 中序序列 :3 2 4 1 6 5）；

4. 判斷一棵樹(shù)是否是完全二叉樹(shù) ；

5. 將二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向；

6.求二叉樹(shù)的寬度；

7. 判斷一棵二叉樹(shù)是否是平衡二叉樹(shù)；

8.判斷一顆二叉樹(shù)是否是另一顆樹(shù)的子樹(shù)。

推薦閱讀

1. 二叉樹(shù)算法應(yīng)用案例

https://blog.csdn.net/luyaran/article/details/53992796

2. 算法——二叉樹(shù) - 說(shuō)故事的五公子

https://www.cnblogs.com/wugongzi/p/11216814.html

3. 二叉樹(shù)的前世今生

https://zhuanlan.zhihu.com/p/121602717