野生前端的數據結構基礎練習（7）——二叉樹

網上的相關教程非常多，基礎知識自行搜索即可。

習題主要選自Orelly出版的《數據結構與演算法javascript描述》一書。

參考代碼可見:https://github.com/dashnowords/blogs/tree/master/Structure/btree

一.二叉樹的基本知識

基本概念

一棵樹最上面的點稱為根節點，如果一個節點下麵連接多個節點，那麼該節點稱為父節點，下麵的節點稱為子節點，二叉樹的每一個節點最多有2個子節點，一個節點子節點的個數稱為度，二叉樹每個節點的度只能是0,1,2中的一個，度為0的節點稱為葉節點。

基本特點

二叉查找樹是一種特殊的二叉樹，其插入查找和刪除都非常高效。

二.基本練習

1. 實現二叉查找樹(BST)

   TIP:BST在插入數據時的邏輯，本身就是一種二分法思維。

2. 樹的遍歷

   TIP:樹的遍歷一般分為先序遍歷，中序遍歷，後序遍歷，這裡的序是指對於一個節點以及它的左子節點和右子節點的訪問次序。具體使用場景的例子包括：先序遍歷時，可以用於查看樹結構，中序遍歷，可以用於顯示排序結果，後序遍歷，可用於計算目錄內文件占用的數據大小。

3. 值的查找

   3.1查找給定值

   TIP:實際上就是二分法查找

   3.2查找最小值

   TIP:BST中最左側的節點。

   3.3查找最大值

   TIP:BST中最右側的節點。

4. 刪除節點

   TIP:主要註意刪除同時包含左右孩子節點的節點時邏輯，由BST插入的規則可以知道，節點右子樹中所有的節點都是大於當前節點值的，所以右子樹中找出的最小值是大於當前節點左子樹上所有值的，所以將其上浮至當前待刪除節點位置，是不影響二叉樹特性的。

5. 計數

三.課後習題（書中第十節習題）

1. 為BST增加一個新方法，返回BST中節點個數。
2. 為BST增加一個新方法，返回BST中邊的個數。
3. 為BST類增加一個新方法max( ),返回最大值。
4. 為BST類增加一個新方法min( ),返回最小值。
5. 寫一段程式，讀入一個較大的文本文件，並將其中的單詞保存到BST中，顯示每個單詞出現的次數

四.習題思路

1. 在BST構造函數中增加一個count屬性，在增刪節點成功時修改count值實現計數即可。
2. BST邊的數量比節點數量少1.
3. （略）
4. （略）
5. 分解出的單詞實際上就是字元串，字元串的比較實際上就是從第一位開始逐個比較ASCII碼，用上面實現的BST做練習就好，詞頻統計更多會用到Trie樹，也就是字典樹，感興趣的讀者可以自行查閱。

五. 根據遍歷序還原二叉樹

【先序+中序】或者【後序+中序】都可以還原出唯一的二叉樹，只根據【先序+後序】還原出的二叉樹不是唯一的（感興趣的可以看看這篇《 為什麼只給出前序和後序，不能唯一確定一個二叉樹 》），這裡的二叉樹指的是一般二叉樹，不是二叉搜索樹。或者相關的文章已經很多了，隨手貼一篇帶圖的《由遍歷序列還原二叉樹結構》,理解難度並不高，同樣建議自己編碼實現一下。

六. 關於二叉樹

二叉樹是非常重要的數據結構，書中介紹的只是最基本的知識，更進一步的學習會涉及二叉樹的數學特性，限制更多性能也更優的平衡二叉樹，滿二叉樹，紅黑樹等等，以及相關的深度優先和廣度優先演算法，路還很長，靜下心慢慢走。