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