引入

前面講到了二叉搜索樹以及它的一些基本操作（插入，搜索，刪除），可是我們要怎么知道這些操作已經(jīng)被執(zhí)行了呢？換句話說，怎樣來描述二叉樹的結(jié)構(gòu)。這里我們又用到了遍歷。

和圖的遍歷一樣，我們也需要逐個(gè)訪問每一個(gè)節(jié)點(diǎn)，但跟圖不同的是，二叉樹的遍歷是從根節(jié)點(diǎn)開始的，而非任意節(jié)點(diǎn)。根據(jù)二叉樹的結(jié)構(gòu)我們知道，每棵二叉樹都是由三部分組成的：根節(jié)點(diǎn)，左子樹和右子樹。而根節(jié)點(diǎn)的左右子樹也是由這三部分組成，所以二叉樹的遍歷問題也是可以用分治來解決的，即遍歷一顆二叉樹 = 訪問根節(jié)點(diǎn) + 遍歷根節(jié)點(diǎn)的左子樹 + 遍歷根節(jié)點(diǎn)的右子樹。

因而我們寫出下面的遞歸關(guān)系式：

其中

代表的是二叉樹 的節(jié)點(diǎn)個(gè)數(shù)。因?yàn)楫?dāng) 為空樹時(shí)，我們不執(zhí)行任何操作，所以這里的 ，即遞歸的出口。

三種遍歷法

根據(jù)左子樹、右子樹和根節(jié)點(diǎn)的遍歷順序，我們可以把遍歷方式分為前序、中序和后序遍歷。

前序遍歷

前序遍歷是先訪問根節(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。下面這張動圖展示了前序遍歷的整個(gè)過程。

代碼實(shí)現(xiàn)：

def pre_order(T):print(T.value, end=' ')if T.left:pre_order(T.left)if T.right:pre_order(T.right)

中序遍歷

中序遍歷是先遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遍歷右子樹。下面這張動圖展示了中序遍歷的整個(gè)過程。

代碼實(shí)現(xiàn)：

def in_order(T):if T.left:in_order(T.left)print(T.value, end=' ')if T.right:in_order(T.right)

后序遍歷

后序遍歷是先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點(diǎn)。下面這張動圖展示了后序遍歷的整個(gè)過程。

代碼實(shí)現(xiàn)：

def post_order(T):if T.left:post_order(T.left)if T.right:post_order(T.right)print(T.value, end=' ')

因?yàn)楸闅v需要訪問的節(jié)點(diǎn)數(shù)總是為

，所以無論是哪種遍歷方式，其復(fù)雜度都為 。

→ 本節(jié)全部代碼 ←

← 快速排序 | 算法與復(fù)雜度?zhuanlan.zhihu.com→ 最近點(diǎn)對與凸包問題（DC）| 算法與復(fù)雜度?zhuanlan.zhihu.com

總結(jié)

以上是生活随笔為你收集整理的二叉树的基本操作_二叉树的遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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