如何實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的二叉樹遍歷算法

今天就跟大家聊聊有關(guān)如何實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的二叉樹遍歷算法，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

今天咱們來看一種新的數(shù)據(jù)結(jié)構(gòu)，樹。

本文大綱

本文大綱

注：可能有的同學(xué)不喜歡手機(jī)閱讀，所以將這篇同步在了我的倉庫，大家可以去 Github 進(jìn)行閱讀，點(diǎn)擊文章最下方的閱讀原文即可

樹

我們先來看下百度百科對樹的定義

樹是 n (n >= 0) 個(gè)節(jié)點(diǎn)的有限集。n = 0 時(shí) 我們稱之為空樹, 空樹是樹的特例。

在任意一棵非空樹中：

• 有且僅有一個(gè)特定的節(jié)點(diǎn)稱為根(Root)的節(jié)點(diǎn)

• 當(dāng) n > 1 時(shí)，其余節(jié)點(diǎn)可分為 m (m > 0)個(gè)互不相交的有限集  T1、T2、........Tm，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹。

我們一起來拆解一下上面的兩句話，到底什么是子樹呢?見下圖

樹

例如在上面的圖中

有且僅有一個(gè)特定的節(jié)點(diǎn)稱為根節(jié)點(diǎn)，也就是上圖中的橙色節(jié)點(diǎn)。

當(dāng)節(jié)點(diǎn)數(shù)目大于 1 時(shí)，除根節(jié)點(diǎn)以外的節(jié)點(diǎn)，可分為 m 個(gè)互不相交的有限集 T1,T2........Tm。

例如上圖中，我們將根節(jié)點(diǎn)以外的節(jié)點(diǎn)，分為了 T1 (2，3，4，5，6，7)，T2(8，9)兩個(gè)有限集。

那么 T1 (綠色節(jié)點(diǎn))和 T2(藍(lán)色節(jié)點(diǎn))就是根節(jié)點(diǎn)(橙色節(jié)點(diǎn))的子樹。

我們拆解之后發(fā)現(xiàn)，我們上圖中的例子符合樹的要求，另外不知道大家有沒有注意到這個(gè)地方。

除根節(jié)點(diǎn)以外的節(jié)點(diǎn)，可分為 m 個(gè)互不相交的有限集。

那么這個(gè)互不相交又是什么含義呢?見下圖。

我們將 (A) , (B) , (C) , (D) 代入上方定義中發(fā)現(xiàn)，(A) , (B) 符合樹的定義，(C), (D) 不符合，這是因?yàn)?(C) ,  (D) 它們都有相交的子樹。

好啦，到這里我們知道如何辨別樹啦，下面我們通過下面兩張圖再來深入了解一下樹。

主要從節(jié)點(diǎn)類型，節(jié)點(diǎn)間的關(guān)系下手。

這里節(jié)點(diǎn)的高度和深度

可能容易記混，我們代入到現(xiàn)實(shí)即可。

我們求物體深度時(shí)，從上往下測量，求高度時(shí)，從下往上測量，節(jié)點(diǎn)的高度和深度也是如此。

二叉樹

我們刷題時(shí)遇到的就是二叉樹啦，下面我們一起來了解一下二叉樹

二叉樹前提是一棵樹，也就是需要滿足我們樹的定義的同時(shí)，還需要滿足以下要求

每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別是左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

注意我們這里提到的是最多，所以二叉樹并不是必須要求每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，也可以有的僅有一個(gè)左子節(jié)點(diǎn)，有的節(jié)點(diǎn)僅有一個(gè)右子節(jié)點(diǎn)。

下面我們來總結(jié)一下二叉樹的特點(diǎn)

• 每個(gè)節(jié)點(diǎn)最多有兩棵子樹，也就是說二叉樹中不存在度大于 2 的節(jié)點(diǎn)，節(jié)點(diǎn)的度可以為 0，1，2。

• 左子樹和右子樹是有順序的,有左右之分。

• 假如只有一棵子樹 ，也要區(qū)分它是左子樹還是右子樹

好啦，我們已經(jīng)了解了二叉樹的特點(diǎn)，那我們分析一下，下圖中的樹是否滿足二叉樹定義，共有幾種二叉樹。

上圖共為 5 種不同的二叉樹，在二叉樹的定義中提到，二叉樹的左子樹和右子樹是有順序的，所以 B，C 是兩個(gè)不同的二叉樹，故上圖為 5  種不同的二叉樹。

特殊的二叉樹

下面我們來說幾種比較特殊的二叉樹，可以幫助我們刷題時(shí)，考慮到特殊情況。

滿二叉樹

滿二叉樹：在一棵二叉樹中，所有分支節(jié)點(diǎn)都存在左子樹和右子樹，并且所有的葉子都在同一層,這種樹我們稱之為滿二叉樹.見下圖

我們發(fā)現(xiàn)只有 (B) 符合滿二叉樹的定義,我們發(fā)現(xiàn)其實(shí)滿二叉樹也為完全二叉樹的一種。

完全二叉樹

完全二叉樹：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹的左部。

哦!我們可以這樣理解，除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿的，而且最后一層的葉子節(jié)點(diǎn)必須靠左。

下面我們來看一下這幾個(gè)例子

上面的幾個(gè)例子中，(A)(B)為完全二叉樹，(C)(D)不是完全二叉樹

斜二叉樹

這個(gè)就很好理解啦,斜二叉樹也就是斜的二叉樹,所有的節(jié)點(diǎn)只有左子樹的稱為左斜樹,所有節(jié)點(diǎn)只有右子樹的二叉樹稱為右斜樹.

諾,下面這倆就是.

另外還有 一些二叉樹的性質(zhì), 比如第 i 層至多有多少節(jié)點(diǎn),通過葉子節(jié)點(diǎn)求度為 2 的節(jié)點(diǎn), 通過節(jié)點(diǎn)樹求二叉樹的深度等, 這些是考研?？嫉闹R(shí),  就不在這里進(jìn)行贅述,需要的同學(xué)可以看一下王道或者天勤的數(shù)據(jù)結(jié)構(gòu), 上面描述的很具體, 并附有證明過程.

好啦，我們已經(jīng)了解了二叉樹，那么二叉樹如何存儲(chǔ)呢?

如何存儲(chǔ)二叉樹

二叉樹多采用兩種方法進(jìn)行存儲(chǔ),基于數(shù)組的順序存儲(chǔ)法和基于指針的二叉鏈?zhǔn)酱鎯?chǔ)法

這里我們再來回顧一下如何用數(shù)組存儲(chǔ)完全二叉樹.

我們首先看根節(jié)點(diǎn)，也就是值為 1 的節(jié)點(diǎn)，它在數(shù)組中的下標(biāo)為 1 ,它的左子節(jié)點(diǎn)，也就是值為 4 的節(jié)點(diǎn)，此時(shí)索引為 2，右子節(jié)點(diǎn)也就是值為 2  的節(jié)點(diǎn)，它的索引為 3。

我們發(fā)現(xiàn)其中的關(guān)系了嗎?

數(shù)組中，某節(jié)點(diǎn)(非葉子節(jié)點(diǎn))的下標(biāo)為 i , 那么其左子節(jié)點(diǎn)下標(biāo)為 2*i(這里可以直接通過相乘得到左孩子, 也就是為什么空出第一個(gè)位置, 如果從 0  開始存，則需要 2i+1 才行), 右子節(jié)點(diǎn)為 2i+1，其父節(jié)點(diǎn)為 i/2 。既然我們完全可以根據(jù)索引找到某節(jié)點(diǎn)的 左子節(jié)點(diǎn)  和右子節(jié)點(diǎn)，那么我們用數(shù)組存儲(chǔ)是完全沒有問題的。

但是,我們再考慮一下這種情景,如果我們用數(shù)組存儲(chǔ)斜樹時(shí)會(huì)出現(xiàn)什么情況?

通過 2*i 進(jìn)行存儲(chǔ)左子節(jié)點(diǎn)的話,如果遇到斜樹時(shí),則會(huì)浪費(fèi)很多的存儲(chǔ)空間,這樣顯然是不合適的,

所以說當(dāng)存儲(chǔ)完全二叉樹時(shí),我們用數(shù)組存儲(chǔ),無疑是最省內(nèi)存的，但是存儲(chǔ)斜樹時(shí)，則就不太合適。

所以我們下面介紹一下另一種存儲(chǔ)結(jié)構(gòu),鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu).

因?yàn)槎鏄涞拿總€(gè)節(jié)點(diǎn), 最多有兩個(gè)孩子, 所以我們只需為每個(gè)節(jié)點(diǎn)定義一個(gè)數(shù)據(jù)域,兩個(gè)指針域即可

val 為節(jié)點(diǎn)的值, left 指向左子節(jié)點(diǎn), right 指向右子節(jié)點(diǎn)。

下面我們對樹 1, 2, 3, 4, 5, 6, 7 使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ),即為下面這種情況。

二叉鏈表的節(jié)點(diǎn)結(jié)構(gòu)定義代碼

public class BinaryTree {     int val;     BinaryTree left;     BinaryTree right;     BinaryTree() {}     BinaryTree(int val) { this.val = val; }     BinaryTree(int val, BinaryTree left, BinaryTree right) {         this.val = val;         this.left = left;         this.right = right;     } }

另外我們在刷題的時(shí)候, 可以自己實(shí)現(xiàn)一下數(shù)據(jù)結(jié)構(gòu), 加深我們的理解, 提升基本功, 而且面試考的也越來越多.

好啦,下面我們說一下樹的遍歷,

下面我會(huì)用動(dòng)圖的形式進(jìn)行描述,很容易理解, 我也會(huì)為大家總結(jié)對應(yīng)的題目,歡迎各位閱讀.

遍歷二叉樹

二叉樹的遍歷指從根節(jié)點(diǎn)出發(fā),按照某種次序依次訪問二叉樹的所有節(jié)點(diǎn),使得每個(gè)節(jié)點(diǎn)都被訪問且訪問一次.

我們下面介紹二叉樹的幾種遍歷方法及其對應(yīng)的題目, 前序遍歷, 中序遍歷 , 后序遍歷 , 層序遍歷 .

前序遍歷

前序遍歷的順序是, 對于樹中的某節(jié)點(diǎn),先遍歷該節(jié)點(diǎn),然后再遍歷其左子樹,最后遍歷其右子樹.

只看文字有點(diǎn)生硬, 下面我們直接看動(dòng)畫吧

前序遍歷

測試題目: leetcode 144. 二叉樹的前序遍歷

代碼實(shí)現(xiàn)(遞歸版)

class Solution {     public List<Integer> preorderTraversal(TreeNode root) {         List<Integer> arr = new ArrayList<>();         preorder(root,arr);         return arr;      }     public void preorder(TreeNode root,List<Integer> arr) {         if (root == null) {             return;         }         arr.add(root.val);         preorder(root.left,arr);         preorder(root.right,arr);     } }

時(shí)間復(fù)雜度 : O(n) 空間復(fù)雜度 : O(n) 為遞歸過程中棧的開銷,平均為 O(logn),但是當(dāng)二叉樹為斜樹時(shí)則為 O(n)

為了控制文章篇幅, 二叉樹的迭代遍歷形式, 會(huì)在下篇文章進(jìn)行介紹。

中序遍歷

中序遍歷的順序是, 對于樹中的某節(jié)點(diǎn),先遍歷該節(jié)點(diǎn)的左子樹, 然后再遍歷該節(jié)點(diǎn), 最后遍歷其右子樹

繼續(xù)看動(dòng)畫吧, 如果有些遺忘或者剛開始學(xué)數(shù)據(jù)結(jié)構(gòu)的同學(xué)可以自己模擬一下執(zhí)行步驟.

中序遍歷

測試題目: leetcode 94 題 二叉樹的中序遍歷

代碼實(shí)現(xiàn)(遞歸版)

class Solution {     public List<Integer> inorderTraversal(TreeNode root) {                    List<Integer> res = new ArrayList<>();          inorder(root, res);          return res;      }     public void inorder (TreeNode root, List<Integer> res) {         if (root == null) {             return;         }         inorder(root.left, res);         res.add(root.val);         inorder(root.right, res);      } }

時(shí)間復(fù)雜度 : O(n) 空間復(fù)雜度 : O(n)

后序遍歷

后序遍歷的順序是,對于樹中的某節(jié)點(diǎn), 先遍歷該節(jié)點(diǎn)的左子樹, 再遍歷其右子樹, 最后遍歷該節(jié)點(diǎn).

哈哈,繼續(xù)看動(dòng)畫吧,看完動(dòng)畫就懂啦.

后序遍歷

測試題目: leetcode 145 題 二叉樹的后序遍歷

代碼實(shí)現(xiàn)(遞歸版)

class Solution {     public List<Integer> postorderTraversal(TreeNode root) {          List<Integer> res = new ArrayList<>();          postorder(root,res);          return res;     }      public void postorder(TreeNode root, List<Integer> res) {         if (root == null) {             return;         }         postorder(root.left, res);         postorder(root.right, res);         res.add(root.val);     } }

時(shí)間復(fù)雜度 : O(n) 空間復(fù)雜度 : O(n)

層序遍歷

顧名思義,一層一層的遍歷.

比如剛才那棵二叉樹的層序遍歷序列即為 1 ~ 9.

二叉樹的層序, 這里我們需要借助其他數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn), 我們思考一下, 我們需要對二叉樹進(jìn)行層次遍歷, 從上往下進(jìn)行遍歷,  我們可以借助什么數(shù)據(jù)結(jié)構(gòu)來幫我們呢 ?

我們可以利用隊(duì)列先進(jìn)先出的特性，使用隊(duì)列來幫助我們完成層序遍歷, 具體操作如下

讓二叉樹的每一層入隊(duì), 然后再依次執(zhí)行出隊(duì)操作,

對該層節(jié)點(diǎn)執(zhí)行出隊(duì)操作時(shí), 需要將該節(jié)點(diǎn)的左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)進(jìn)行入隊(duì)操作,

這樣當(dāng)該層的所有節(jié)點(diǎn)出隊(duì)結(jié)束后, 下一層也就入隊(duì)完畢,

不過我們需要考慮的就是, 我們需要通過一個(gè)變量來保存每一層節(jié)點(diǎn)的數(shù)量.

這樣做是為了防止, 一直執(zhí)行出隊(duì)操作, 使輸出不能分層

好啦,下面我們直接看動(dòng)畫吧,

測試題目: leetcode 102 二叉樹的層序遍歷

題目代碼

class Solution {     public List<List<Integer>> levelOrder(TreeNode root) {            List<List<Integer>> res = new ArrayList<>();       if (root == null) {           return res;       }        //入隊(duì) root 節(jié)點(diǎn)，也就是第一層         Queue<TreeNode> queue = new LinkedList<>();       queue.offer(root);       while (!queue.isEmpty()) {           List<Integer> list = new ArrayList<>();           int size = queue.size();           for (int i = 0; i < size; ++i) {               TreeNode temp = queue.poll();               //孩子節(jié)點(diǎn)不為空，則入隊(duì)               if (temp.left != null)  queue.offer(temp.left);               if (temp.right != null) queue.offer(temp.right);               list.add(temp.val);           }           res.add(list);       }       return res;     } }

時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)

大家如果吃透了二叉樹的層序遍歷的話，可以順手把下面幾道題目解決掉，思路一致，甚至都不用拐彎

• leetcode 107. 二叉樹的層序遍歷 II

• leetcode 103. 二叉樹的鋸齒形層序遍歷

上面兩道題僅僅是多了翻轉(zhuǎn)

• leetcode 199. 二叉樹的右視圖

• leetcode 515. 在每個(gè)樹行中找最大值

• leetcode 637. 二叉樹的層平均值

這三道題，僅僅是加了一層的一些操作

• leetcode 116 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)

• leetcode 117 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)2

這兩個(gè)題對每一層的節(jié)點(diǎn)進(jìn)行鏈接即可，兩道題目代碼一致

看完上述內(nèi)容，你們對如何實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的二叉樹遍歷算法有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。