首頁人工智能技術(shù)資訊正文

怎樣理解二叉樹?二叉樹的遍歷方式

更新時間:2023-04-28 來源:黑馬程序員 瀏覽量:

IT培訓(xùn)班

二叉樹(Binary Tree) 是一種樹形數(shù)據(jù)結(jié)構(gòu),其中每個父節(jié)點最多可以有兩個子節(jié)點。 二叉樹的每個節(jié)點(node)包含三個屬性:data 數(shù)據(jù)、left 左子節(jié)點的地址、right 右子節(jié)點的地址。

滿二叉樹(Full Binary Tree):每個結(jié)點要么沒有子結(jié)點,要么有兩個子結(jié)點。

1682652995207_32.png

完美二叉樹(Pefect Binary Tree):每個結(jié)點都有兩個子結(jié)點,所有葉子結(jié)點都在同一層。

1682653046724_33.png

完全二叉樹(Complete Binary Tree):從根結(jié)點到倒數(shù)第二層為完美二叉樹,最后一層可以不完全填充,其葉子結(jié)點都靠左對齊。

完全二叉樹

二叉樹天然的具有遞歸結(jié)構(gòu),二叉樹的遞歸定義為:二叉樹是一棵空樹,或者是一棵由一個根節(jié)點和兩棵互不相交的, 分別稱作根的左子樹和右子樹組成的非空樹;左子樹和右子樹又同樣都是二叉樹。

二叉樹遞歸結(jié)構(gòu)

二叉樹的遍歷方式

LeetCode 題目中,二叉樹的遍歷方式是最基本,也是最重要的一類題目。先介紹一下二叉樹的遍歷方式。

先序遍歷(前序遍歷):按照根節(jié)點 -> 左孩子 -> 右孩子 的方式遍歷,即「先序遍歷」,每次先遍歷根節(jié)點,遍歷結(jié)果為 1 2 4 5 3 6 7;

二叉樹的遍歷

中序遍歷:按照左孩子 -> 根節(jié)點 -> 右孩子 的方式遍歷,即「中序序遍歷」,遍歷結(jié)果為 4 2 5 1 6 3 7;

1682653816102_37.png

后序遍歷:按照左孩子 -> 右孩子 -> 根節(jié)點 的方式遍歷,即「后序序遍歷」,遍歷結(jié)果為 4 5 2 6 7 3 1;

后序遍歷

層序遍歷:按照每一層從左向右的方式進(jìn)行遍歷,遍歷結(jié)果為 1 2 3 4 5 6 7。

層序遍歷

分享到:
在線咨詢 我要報名
和我們在線交談!