|
|
教學(xué)公告
22軟件工程《數(shù)據(jù)結(jié)構(gòu)與算法》第7周教學(xué)安排
講解第5章的內(nèi)容131、134-146頁
重點
1、樹的遍歷
2、二叉樹的邏輯結(jié)構(gòu)
3、二叉樹的性質(zhì)與練習(xí)
4、二叉樹的遍歷操作
（由中序遍歷和前（后）序遍歷推斷出一顆唯一的二叉樹）
3、二叉樹的存儲結(jié)構(gòu)和遞歸算法
（鏈?zhǔn)酱鎯Y(jié)構(gòu)的程序?qū)崿F(xiàn)）
大家可以根據(jù)自己的情況進行相應(yīng)的預(yù)習(xí)
師說
為什么要有樹
一百個數(shù)字，無序排列，我們要根據(jù)已知的某個數(shù)字a，找到a在這一百個數(shù)字中的位置（也就是下標(biāo)），如何尋找?遍歷。假設(shè)100個數(shù)字可以每次遍歷，1萬個可以每次遍歷，100萬個還可以么?再計算遍歷的頻率，不好好掌握，簡單的遍歷就可以把負責(zé)遍歷的人給忙死。
這時候人們開始思考，怎么樣可以快速定位呢?很簡單，如果插入的時候有順序，那么這樣的遍歷就變得非常簡單。我們都知道1-100中間如果要找某個數(shù)字，我們肯定第一個判斷的是50這個數(shù)值與要定位的數(shù)字a的大小對比（因為有序了，所以大小對比才有意義）。如果小于50，那么我們下一次會先判斷25，如果大于50，那么我們會判斷75……這就是常見的二分法，我們判斷出來要找的數(shù)字小于50時，我們就不需要去判斷50-100中間的這一堆數(shù)字，對比遍歷，我們就相當(dāng)于少了一半多工作量，一直循環(huán)下去，對比遍歷，遍歷的數(shù)據(jù)越多，效率越高。具體研究請自行百度 二分法 時間/空間復(fù)雜度，去得出結(jié)論。
編程中遇到這樣的問題就有更多，因為查找的效率嚴(yán)重影響我們系統(tǒng)反應(yīng)的時間。計算機中如何體現(xiàn)上文所述的二分法呢?聰明的人根據(jù)二分法的判斷順序，設(shè)計了一個有左子樹，右子樹的樹形結(jié)構(gòu)，命名為二叉樹。二叉樹必須有序，否則無序的二叉樹，數(shù)據(jù)來了都不知道要放在什么地方。
二叉樹（Binary Tree）的知識點是程序員面試的?？键c，所以平時更應(yīng)該注重這方面知識的積累。這篇文章主要涉及二叉樹的基礎(chǔ)知識和基礎(chǔ)操作，對初學(xué)者相當(dāng)于是一個引導(dǎo)。若想進一步理解二叉樹相關(guān)的知識，可以找找相關(guān)的技術(shù)書籍參考學(xué)習(xí)。
數(shù)據(jù)來源:https://blog.csdn.net/chuogangrong4739/article/details/101053059
https://zhuanlan.zhihu.com/p/121602717
二叉樹常見面試題（https://www.cnblogs.com/33debug/p/7252371.html）
1. 求兩個節(jié)點的最近公共祖先；
2. 求二叉樹中最遠的兩個結(jié)點的距離；
3. 由前序遍歷和中序遍歷重建二叉樹（如:前序序列:1 2 3 4 5 6 - 中序序列 :3 2 4 1 6 5）；
4. 判斷一棵樹是否是完全二叉樹 ；
5. 將二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向；
6.求二叉樹的寬度；
7. 判斷一棵二叉樹是否是平衡二叉樹；
8.判斷一顆二叉樹是否是另一顆樹的子樹。
推薦閱讀
- 二叉樹算法應(yīng)用案例
https://blog.csdn.net/luyaran/article/details/53992796
