數(shù)據(jù)結(jié)構(gòu)--樹
@(數(shù)據(jù)結(jié)構(gòu))
樹是節(jié)點的有限集合
基本概念
樹.png
- 雙親(父結(jié)點) ：A是BCD的雙親棺耍，雙親指的是一個結(jié)點
- 孩子（子結(jié)點）：BCD是A的子結(jié)點
- 度：當(dāng)前結(jié)點直接的孩子拾因，A的度是3，B的度為2庄岖，C的度為0
- 葉子（葉結(jié)點）：終端結(jié)點（C许蓖、E窖杀、F漓摩、G、H）
- 根（根結(jié)點）：非終端結(jié)點（A入客、B管毙、D）
- 有序樹：如果E和F不可以換順序就是有序
- 無序樹：E和F可以換順序，不影響邏輯就是無序樹
- 祖先：E的 祖先 是 A 桌硫、B
- 子孫：下面全部結(jié)點都是A的子孫
- 深度：從上而下夭咬，為一到三層的深度
- 結(jié)點深度：A的結(jié)點深度為1，B為2铆隘，E為3
- 樹深度：當(dāng)前樹的最大深度
二叉樹
所有結(jié)點的度都小于等于2
不用的遍歷其實就是訪問根結(jié)點的順序的不同
前序遍歷
前序遍歷.png
- 首先訪問根結(jié)點
- 訪問順序 ：根結(jié)點 --> 左結(jié)點 --> 右結(jié)點
- 對于上圖的樹卓舵，前序遍歷結(jié)果為（忽略結(jié)點C）：
- A - B - E - F - D - G - H
中序遍歷
中序遍歷.png
- 中間訪問根結(jié)點
- 訪問順序：左結(jié)點 --> 根結(jié)點 --> 右結(jié)點
- 對于上圖的樹，中序遍歷結(jié)果為（忽略結(jié)點C）：
- E - B - F - A - G - D - H
后序遍歷
后序遍歷
- 最后訪問根結(jié)點
- 訪問順序： 左結(jié)點 --> 右結(jié)點 --> 根節(jié)點
- 對于上圖的樹膀钠，后序遍歷結(jié)果為（忽略結(jié)點C）：
- E - F - B - G - H - D - A
數(shù)組編碼概述
-
放入數(shù)組的順序就是從上到下掏湾，從左到右
數(shù)組與結(jié)點的轉(zhuǎn)換.png 關(guān)于使用數(shù)組來實現(xiàn)二叉樹，基本就是通過上圖的關(guān)系肿嘲，讓數(shù)組下標(biāo)和節(jié)點位置產(chǎn)生關(guān)聯(lián)忘巧，基本就和線性表中的順序表實現(xiàn)差不多
鏈表實現(xiàn)二叉樹
-
之前的文章中有寫到了關(guān)于線性表中鏈表的實現(xiàn)，而在二叉樹中睦刃，鏈表的實現(xiàn)可以把它想象成是 三鏈表的實現(xiàn)， 每一個結(jié)點都持有著
- 自己的父結(jié)點指針
- 自己的左結(jié)點指針
- 自己的右結(jié)點的指針
關(guān)鍵一點就是對于結(jié)點的查找十酣，因為無論是增加還是刪除結(jié)點都基本運用到查找方法涩拙，通過結(jié)點不斷的指向，一層一層去追溯來找到目標(biāo)結(jié)點耸采。
對于二叉樹的實現(xiàn)方面簡單略過了兴泥，因為基本和線性表中的思路是一致的，重點把握二叉樹的概率虾宇，以及三種方式的遍歷搓彻。
