樹(shù)：

目前學(xué)過(guò)的基本數(shù)據(jù)結(jié)構(gòu)

1.數(shù)組 鏈表 哈希表

哈希表本身是數(shù)組加鏈表? ?達(dá)到O(1)

不管存儲(chǔ)什么數(shù)字，根據(jù)數(shù)除以數(shù)組長(zhǎng)度的余數(shù)

考慮一個(gè)鏈表，是O(n),短的話是O(1)

能不能降低時(shí)間復(fù)雜度

循環(huán)減半logn —— > 折半查找

有一個(gè)有序數(shù)組

進(jìn)行查詢可以用一個(gè)折半查找法

?找到中間位置：首尾相加/2

數(shù)組必須有序才能達(dá)到logn

鏈表是可以達(dá)到logn時(shí)間復(fù)雜度

樹(shù)也是鏈?zhǔn)酱鎯?chǔ)，特殊的樹(shù)可以達(dá)到logn

先學(xué)一個(gè)，有序二叉樹(shù)

樹(shù)的根節(jié)點(diǎn)必須大于等于左子樹(shù)

必須小于等于右子樹(shù)

?畫(huà)一個(gè)特殊的樹(shù)

每次查詢折掉一半的數(shù)據(jù)，O(1)

樹(shù)的存取和讀取效率比較高。

樹(shù)的概念：

（樹(shù)可能有很多叉）

1.節(jié)點(diǎn) 根節(jié)點(diǎn) 父節(jié)點(diǎn) 子節(jié)點(diǎn) 葉子結(jié)點(diǎn)

2.節(jié)點(diǎn)的權(quán)（節(jié)點(diǎn)的值）

3.路徑：（從根節(jié)點(diǎn)到該節(jié)點(diǎn)走過(guò)的節(jié)點(diǎn)）

4.層

5.子樹(shù)

例如：畫(huà)圈的

6.樹(shù)的高度：有幾層

7.森林：多顆子樹(shù)構(gòu)成森林

二叉樹(shù)：每個(gè)節(jié)點(diǎn)上最多有兩個(gè)節(jié)點(diǎn)稱為二叉樹(shù)。

滿二叉樹(shù)：最后一層的數(shù)據(jù)也是鋪滿的。

完全二叉樹(shù)：從上到下從左到右依次進(jìn)行平鋪。

===================================================

二叉樹(shù)的遍歷說(shuō)明

• • 深度優(yōu)先遍歷：

• • 先序遍歷：先輸出父節(jié)點(diǎn)，再遍歷輸出左子樹(shù)，再遍歷輸出右子樹(shù)

• • • 中序遍歷 ：先左再父再右

• • • 后序遍歷 2?3?4??6?8?7?5

• • 廣度優(yōu)先遍歷
    • 層次遍歷 一層一層遍歷

總結(jié)

以上是生活随笔為你收集整理的树、树、树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。