Java 中有哪些遍歷二叉樹的方法

 

1. 基本介紹

樹結(jié)構(gòu)多種多樣，但是最常用的還是二叉樹。二叉樹中每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，這兩個(gè)節(jié)點(diǎn)分別是左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。注意：不要求都有兩個(gè)子節(jié)點(diǎn)，可以只有左子節(jié)點(diǎn)，也可以只有右子節(jié)點(diǎn)。

 

2. 二叉樹的存儲(chǔ)

2.1. 鏈?zhǔn)酱鎯?chǔ)法

每個(gè)節(jié)點(diǎn)至少有三個(gè)字段，其中一個(gè)存儲(chǔ)數(shù)據(jù)，另外兩個(gè)是指向左右子節(jié)點(diǎn)的指針。這種存儲(chǔ)方式比較常用，大部分二叉樹代碼都是通過(guò)這種結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。

 

2.2. 數(shù)組存儲(chǔ)法

我們把根節(jié)點(diǎn)存儲(chǔ)在下標(biāo) i=1 的位置，它的左子節(jié)點(diǎn)存儲(chǔ)在下標(biāo)為 2 * i 的位置，右子節(jié)點(diǎn)存儲(chǔ)在下標(biāo)為 2*i+1 的位置。以此類推，B 節(jié)點(diǎn)、C 節(jié)點(diǎn)的左右子節(jié)點(diǎn)都按照這種規(guī)律進(jìn)行存儲(chǔ)，最終如下圖所示。

綜上，如果節(jié)點(diǎn) X 存儲(chǔ)在數(shù)組中下標(biāo)為 i 的位置，那么下標(biāo)為 2*i 的位置存儲(chǔ)的就是它的左子節(jié)點(diǎn)，下標(biāo)為 2*i+1 的位置存儲(chǔ)的就是它的右子節(jié)點(diǎn)。反過(guò)來(lái)，i/2 的位置存儲(chǔ)的就是它的父節(jié)點(diǎn)。一般情況下，為了方便計(jì)算，根節(jié)點(diǎn)會(huì)被存儲(chǔ)在下標(biāo)為 1 的位置。

 

通過(guò)上述可以看到，針對(duì)一般樹來(lái)說(shuō)，使用數(shù)組的方式存儲(chǔ)樹會(huì)浪費(fèi)比較多的存儲(chǔ)空間。但是針對(duì)下文會(huì)提到的滿二叉樹或者完全二叉樹來(lái)說(shuō)，數(shù)組存儲(chǔ)的方式是最節(jié)省內(nèi)存的一種方式。因?yàn)閿?shù)組存儲(chǔ)時(shí)，不需要再存儲(chǔ)額外的左右子節(jié)點(diǎn)的指針。

3. 二叉樹的遍歷

二叉樹的遍歷就是將二叉樹中的所有節(jié)點(diǎn)遍歷打印出來(lái)。經(jīng)典的方法有三種，前序遍歷、中序遍歷和后序遍歷，還可以按層遍歷（個(gè)人理解的按層遍歷其實(shí)就是按照?qǐng)D的廣度優(yōu)先遍歷方法來(lái)進(jìn)行遍歷）。

前、中、后是根據(jù)節(jié)點(diǎn)被打印的先后來(lái)進(jìn)行區(qū)分的：前序就是先打印節(jié)點(diǎn)本身，之后再打印它的左子樹，最后打印它的右子樹；中序就是先打印節(jié)點(diǎn)的左子樹，再打印節(jié)點(diǎn)本身，最后打印右子樹，即把節(jié)點(diǎn)放中間的位置輸出；后序就是先打印節(jié)點(diǎn)的左子樹，再打印節(jié)點(diǎn)的右子樹，最后打印節(jié)點(diǎn)本身。如下圖所示

 

按層遍歷類似于圖的廣度優(yōu)先遍歷，先打印第一層的節(jié)點(diǎn)，之后再依次打印第二層的節(jié)點(diǎn)，以此類推。

 

3.1. 代碼實(shí)現(xiàn)

實(shí)際上，二叉樹的前、中、后序遍歷是一個(gè)遞歸的過(guò)程。比如，前序遍歷，其實(shí)就是先打印根節(jié)點(diǎn)，然后遞歸遍歷左子樹，最后遞歸遍歷右子樹。遞歸遍歷左右子樹其實(shí)就跟遍歷根節(jié)點(diǎn)的方法一樣。下面先寫出這三者遍歷的遞推公式：

前序遍歷的遞推公式：
preOrder(r) = print r ---> preOrder(r->left) ---> preOrder(r->right)

中序遍歷的遞推公式：
inOrder(r) = inOrder(r--->left) ---> print r ---> inOrder(r->right)

后序遍歷的遞推公式：
postOrder(r) = postOrder(r->left) ---> postOrder(r->right) --->print r

之后將遞推公式轉(zhuǎn)化為代碼如下所示：

/**
 * 前序遍歷
 */
public void preOrder(Node tree) {
    if (tree == null) {
        return;
    }

    System.out.print(tree.data + "  ");

    preOrder(tree.left);

    preOrder(tree.right);
}

/**
 * 中序遍歷
 */
public void inOrder(Node tree) {
    if (tree == null) {
        return;
    }

    inOrder(tree.left);

    System.out.print(tree.data + "  ");

    inOrder(tree.right);
}

/**
 * 后序遍歷
 */
public void postOrder(Node tree) {
    if (tree == null) {
        return;
    }

    postOrder(tree.left);

    postOrder(tree.right);

    System.out.print(tree.data + "  ");
}

★  

遞歸代碼的關(guān)鍵，在于寫出遞推公式。而遞推公式的關(guān)鍵在于，A 問(wèn)題可以被拆解成 B、C 兩個(gè)問(wèn)題。假設(shè)要解決 A 問(wèn)題，那么假設(shè) B、C 問(wèn)題已經(jīng)解決了。那么在 B、C 已經(jīng)解決的提前下，看如何利用 B、C 來(lái)解決 A 。千萬(wàn)不要模擬計(jì)算機(jī)一層一層想下去，否則你就會(huì)發(fā)現(xiàn)你自己都不知道在哪了。

”  

下面是按層遍歷的代碼，按層遍歷需要用到隊(duì)列的入隊(duì)和出隊(duì)等操作。先將根節(jié)點(diǎn)放入到隊(duì)列中，然后循環(huán)從隊(duì)列中取節(jié)點(diǎn)（出隊(duì)），再將該節(jié)點(diǎn)的左右子節(jié)點(diǎn)入隊(duì)。出隊(duì)的順序就是層次遍歷的結(jié)果。

/**
 * 層次遍歷
 */
public void BFSOrder(Node tree) {
    if (tree == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    Node temp = null;
    queue.offer(tree);
    while (!queue.isEmpty()) {
        temp = queue.poll();
        System.out.print(temp.data + "  ");
        if (temp.left != null) {
            queue.offer(temp.left);
        }

        if (temp.right != null) {
            queue.offer(temp.right);
        }
    }
}

★  

完整的代碼可查看 github 倉(cāng)庫(kù) https://github.com/DawnGuoDev/algos ，這個(gè)倉(cāng)庫(kù)將主要包含常用數(shù)據(jù)結(jié)構(gòu)及其基本操作的手寫實(shí)現(xiàn)（Java），也會(huì)包含常用算法思想經(jīng)典例題的實(shí)現(xiàn)（Java）。在程序鍋找到工作之前，這個(gè)倉(cāng)庫(kù)將會(huì)保持更新狀態(tài)，在此之間學(xué)到的關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的知識(shí)或者實(shí)現(xiàn)也都會(huì)往里面 commit，所以趕緊來(lái) star 哦。

”  

3.2. 時(shí)間復(fù)雜度

遍歷過(guò)程中的次數(shù)就是訪問(wèn)所有節(jié)點(diǎn)的所需的次數(shù)，而每個(gè)節(jié)點(diǎn)最多被訪問(wèn)兩次，因此遍歷的時(shí)間復(fù)雜度是跟節(jié)點(diǎn)的個(gè)數(shù) n 成正比的，即遍歷的時(shí)間復(fù)雜度是 O(n)。

4. 特殊的二叉樹

4.1. 滿二叉樹

滿二叉樹是一種特殊的二叉樹，而且還是完全二叉樹的一種特殊情況。如上圖編號(hào) 2 的那棵樹所示，葉子節(jié)點(diǎn)全在底層，除了葉子節(jié)點(diǎn)之外，每個(gè)節(jié)點(diǎn)都有左右兩個(gè)子節(jié)點(diǎn)。

4.2. 完全二叉樹

完全二叉樹也是一種特殊的二叉樹。如上圖編號(hào) 3 的那棵樹所示，葉子節(jié)點(diǎn)都在最底下兩層，最后一層的葉子節(jié)點(diǎn)都靠左排列，并且除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都達(dá)到最大。

 

完全二叉樹的特征使得它可以使用數(shù)組就可以很好地存儲(chǔ)數(shù)據(jù)。完全二叉樹要求最后一層的葉子節(jié)點(diǎn)靠左排列也是因?yàn)槿绱恕?/p> 

4.2.1. 完全二叉樹的存儲(chǔ)

• 鏈?zhǔn)酱鎯?chǔ)

  就是上面提到的那種方式。

• 數(shù)組存儲(chǔ)

  完全二叉樹使用數(shù)組存儲(chǔ)時(shí)，如下圖所示。我們發(fā)現(xiàn)使用數(shù)組來(lái)存儲(chǔ)完全二叉樹是一種很節(jié)省內(nèi)存的方式。這也是完全二叉樹被作為一種特殊樹的原因，也是完全二叉樹要求最后一層的子節(jié)點(diǎn)必須都靠左的原因。

  在講解堆或者堆排序的時(shí)候，堆其實(shí)也是一種完全二叉樹，最常用的存儲(chǔ)方式就是數(shù)組。