如何解析數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)中的二叉樹(shù)

本篇文章給大家分享的是有關(guān)如何解析數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)中的二叉樹(shù)，小編覺(jué)得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話(huà)不多說(shuō)，跟著小編一起來(lái)看看吧。

一.二叉樹(shù)的基本知識(shí)

基本概念

一棵樹(shù)最上面的點(diǎn)稱(chēng)為根節(jié)點(diǎn)，如果一個(gè)節(jié)點(diǎn)下面連接多個(gè)節(jié)點(diǎn)，那么該節(jié)點(diǎn)稱(chēng)為父節(jié)點(diǎn)，下面的節(jié)點(diǎn)稱(chēng)為子節(jié)點(diǎn)，二叉樹(shù)的每一個(gè)節(jié)點(diǎn)最多有2個(gè)子節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)子節(jié)點(diǎn)的個(gè)數(shù)稱(chēng)為度，二叉樹(shù)每個(gè)節(jié)點(diǎn)的度只能是0,1,2中的一個(gè)，度為0的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn)。

基本特點(diǎn)

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

二.基本練習(xí)

1. 實(shí)現(xiàn)二叉查找樹(shù)(BST)

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

2. 樹(shù)的遍歷

   TIP:樹(shù)的遍歷一般分為先序遍歷，中序遍歷，后序遍歷，這里的序是指對(duì)于一個(gè)節(jié)點(diǎn)以及它的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的訪問(wèn)次序。具體使用場(chǎng)景的例子包括：先序遍歷時(shí)，可以用于查看樹(shù)結(jié)構(gòu)，中序遍歷，可以用于顯示排序結(jié)果，后序遍歷，可用于計(jì)算目錄內(nèi)文件占用的數(shù)據(jù)大小。

3. 值的查找

   3.1查找給定值

   TIP:實(shí)際上就是二分法查找

   3.2查找最小值

   TIP:BST中最左側(cè)的節(jié)點(diǎn)。

   3.3查找最大值

   TIP:BST中最右側(cè)的節(jié)點(diǎn)。

4. 刪除節(jié)點(diǎn)

   TIP:主要注意刪除同時(shí)包含左右孩子節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)邏輯，由BST插入的規(guī)則可以知道，節(jié)點(diǎn)右子樹(shù)中所有的節(jié)點(diǎn)都是大于當(dāng)前節(jié)點(diǎn)值的，所以右子樹(shù)中找出的最小值是大于當(dāng)前節(jié)點(diǎn)左子樹(shù)上所有值的，所以將其上浮至當(dāng)前待刪除節(jié)點(diǎn)位置，是不影響二叉樹(shù)特性的。

5. 計(jì)數(shù)

三.課后習(xí)題（書(shū)中第十節(jié)習(xí)題）

1. 為BST增加一個(gè)新方法，返回BST中節(jié)點(diǎn)個(gè)數(shù)。

2. 為BST增加一個(gè)新方法，返回BST中邊的個(gè)數(shù)。

3. 為BST類(lèi)增加一個(gè)新方法max( ),返回最大值。

4. 為BST類(lèi)增加一個(gè)新方法min( ),返回最小值。

5. 寫(xiě)一段程序，讀入一個(gè)較大的文本文件，并將其中的單詞保存到BST中，顯示每個(gè)單詞出現(xiàn)的次數(shù)

四.習(xí)題思路

1. 在BST構(gòu)造函數(shù)中增加一個(gè)count屬性，在增刪節(jié)點(diǎn)成功時(shí)修改count值實(shí)現(xiàn)計(jì)數(shù)即可。

2. BST邊的數(shù)量比節(jié)點(diǎn)數(shù)量少1.

3. （略）

4. （略）

5. 分解出的單詞實(shí)際上就是字符串，字符串的比較實(shí)際上就是從第一位開(kāi)始逐個(gè)比較ASCII碼，用上面實(shí)現(xiàn)的BST做練習(xí)就好，詞頻統(tǒng)計(jì)更多會(huì)用到Trie樹(shù)，也就是字典樹(shù)，感興趣的讀者可以自行查閱。

五. 根據(jù)遍歷序還原二叉樹(shù)

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

六. 關(guān)于二叉樹(shù)

二叉樹(shù)是非常重要的數(shù)據(jù)結(jié)構(gòu)，書(shū)中介紹的只是最基本的知識(shí)，更進(jìn)一步的學(xué)習(xí)會(huì)涉及二叉樹(shù)的數(shù)學(xué)特性，限制更多性能也更優(yōu)的平衡二叉樹(shù)，滿(mǎn)二叉樹(shù)，紅黑樹(shù)等等，以及相關(guān)的深度優(yōu)先和廣度優(yōu)先算法。

以上就是如何解析數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)中的二叉樹(shù)，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見(jiàn)到或用到的。希望你能通過(guò)這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注億速云行業(yè)資訊頻道。