如何解析數據結構基礎中的二叉樹

本篇文章給大家分享的是有關如何解析數據結構基礎中的二叉樹，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

一.二叉樹的基本知識

基本概念

一棵樹最上面的點稱為根節點，如果一個節點下面連接多個節點，那么該節點稱為父節點，下面的節點稱為子節點，二叉樹的每一個節點最多有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樹，也就是字典樹，感興趣的讀者可以自行查閱。

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

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

六. 關于二叉樹

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

以上就是如何解析數據結構基礎中的二叉樹，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。