摘要：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)由于二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為每個(gè)結(jié)點(diǎn)設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域。最終能得到二叉樹(shù)的完整結(jié)構(gòu)。

這篇文章主要介紹樹(shù)結(jié)構(gòu)中的一種特殊存在——二叉樹(shù)。主要內(nèi)容有：

二叉樹(shù)的概念

二叉樹(shù)的基本結(jié)構(gòu)

二叉樹(shù)的操作

二叉樹(shù)： 每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)，兩個(gè)子結(jié)點(diǎn)是有次序的，且子結(jié)點(diǎn)次序不能顛倒。兩個(gè)子結(jié)點(diǎn)一般稱之為左結(jié)點(diǎn)及右結(jié)點(diǎn)。

層次： 在樹(shù)中，節(jié)點(diǎn)的層次從根開(kāi)始定義，根為第一層。

深度： 樹(shù)中節(jié)點(diǎn)的最大層次為樹(shù)的深度。

度： 結(jié)點(diǎn)擁有的結(jié)點(diǎn)數(shù)。

分支結(jié)點(diǎn)： 度不為0的結(jié)點(diǎn)。

葉子節(jié)點(diǎn)： 度為0的結(jié)點(diǎn)。

特殊二叉樹(shù)

滿二叉樹(shù)：所有分支結(jié)點(diǎn)都存在左右兩節(jié)點(diǎn)，并且所有葉子結(jié)點(diǎn)都在同一層。

斜樹(shù)：所有的結(jié)點(diǎn)都只有左子結(jié)點(diǎn)或者右子結(jié)點(diǎn)。

完全二叉樹(shù)：對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào)，如果編號(hào)i（1<=i<=n）的結(jié)點(diǎn) 與同樣深度的滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中位置完全相同，則稱之為完全二叉樹(shù)。

二叉查找樹(shù)：左子樹(shù)中節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值，右子樹(shù)中節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值。

二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置，也就是數(shù)組的下標(biāo)要能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系。使用順序存儲(chǔ)結(jié)構(gòu)表現(xiàn)二叉樹(shù)的時(shí)候，在其線性結(jié)構(gòu)中，會(huì)存在一些空結(jié)點(diǎn)，但是其會(huì)占據(jù)一定的內(nèi)存空間，會(huì)造成存儲(chǔ)空間的浪費(fèi)。

由于二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為每個(gè)結(jié)點(diǎn)設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域。

結(jié)點(diǎn)的結(jié)構(gòu)定義：

class TreeNode {
    var value: String
    var left: TreeNode");

現(xiàn)在我們創(chuàng)建一棵如圖所示的二叉樹(shù)：

為了能讓每個(gè)結(jié)點(diǎn)確認(rèn)是否有左右子結(jié)點(diǎn)，我們將預(yù)期二叉樹(shù)進(jìn)行一個(gè)擴(kuò)展：

我們給每一個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn)，其值為一個(gè)特定值——#。

創(chuàng)建這棵二叉樹(shù)代碼：

let arr = ["A", "B", "D", "G", "#", "#", "H", "#", "#", "#", "C", "E", "#", "I", "#", "#", "F"]
var index = 0

func preCreateTree(_ tree: inout BinaryTreeNode");if index > arr.count-1 {
        return
    }

    let value = arr[index]

    index += 1

    if value == "#" {
        tree = nil
    } else {
        // 生成根結(jié)點(diǎn)
        tree = BinaryTreeNode(value)

        // 構(gòu)造左子樹(shù)
        preCreateTree(&tree!.leftChild)

        // 構(gòu)造右子樹(shù)
        preCreateTree(&tree!.rightChild)
    }
}

var root: BinaryTreeNode");

二叉樹(shù)的遍歷主要分為四種：

前序遍歷： 根結(jié)點(diǎn)-->左子樹(shù)-->右子樹(shù)。

中序遍歷： 左子樹(shù)-->根結(jié)點(diǎn)-->右子樹(shù)。

后序遍歷： 左子樹(shù)-->右子樹(shù)-->根結(jié)點(diǎn)。

層序遍歷： 從上至下一層一層遍歷。

前序遍歷

前面創(chuàng)建二叉樹(shù)時(shí)，我們有一個(gè)數(shù)組 ["A", "B", "D", "G", "#", "#", "H", "#", "#", "#", "C", "E", "#", "I", "#", "#", "F"]，這個(gè)數(shù)組是如何得到的呢？

就是根據(jù)前序遍歷擴(kuò)展二叉樹(shù)的結(jié)果得到的這個(gè)數(shù)組，并利用這個(gè)數(shù)組前序創(chuàng)建了我們預(yù)期的二叉樹(shù)。

前序遍歷代碼：

func preOrderTraverse(_ tree: BinaryTreeNode");if let node = tree {
        print("value is (node.value)")

        // 先序遍歷左子樹(shù)
        preOrderTraverse(node.leftChild)

        // 再先序遍歷右子樹(shù)
        preOrderTraverse(node.rightChild)
    }
}

中序遍歷

中序遍歷代碼：

func inOrdertraverse(_ tree: BinaryTreeNode");if let node = tree {
        // 中序遍歷左子樹(shù)
        inOrdertraverse(node.leftChild)

        print("value is (node.value)")

        // 中序遍歷右子樹(shù)
        inOrdertraverse(node.rightChild)
    }
}

后序遍歷

后序遍歷代碼：

func lastOrdertraverse(_ tree: BinaryTreeNode");if let node = tree {
        // 后序遍歷左子樹(shù)
        lastOrdertraverse(node.leftChild)

        // 后序遍歷右子樹(shù)
        lastOrdertraverse(node.rightChild)

        print("value is (node.value)")
    }
}

層序遍歷

層序遍歷代碼：

func levelOrdertraverse(_ tree: BinaryTreeNode");let root = tree else {
        return
    }
    
    var tempQueue: [BinaryTreeNode] = []
    
    // 將根節(jié)點(diǎn)加入數(shù)組
    if let _ = root.value {
        tempQueue.insert(root, at: 0)
    }
    
    while tempQueue.count != 0 {
    	  // 取出數(shù)組最后一個(gè)元素
        let temp = tempQueue.popLast()!
        
        // 將下一層結(jié)點(diǎn)依次插入到數(shù)組最前面
        if let l = temp.leftChild, l.value != nil {
            tempQueue.insert(l, at: 0)
        }
        
        if let r = temp.rightChild, r.value != nil {
            tempQueue.insert(r, at: 0)
        }
        
        print(temp.value)
    }
}

func maxDepth(_ tree: BinaryTreeNode");let root = tree else {
        return 0
    }
    
    return max(maxDepth(root.leftChild), maxDepth(root.rightChild)) + 1
}

遍歷特點(diǎn)：

前序遍歷： 根結(jié)點(diǎn)-->左子樹(shù)-->右子樹(shù)。

中序遍歷： 左子樹(shù)-->根結(jié)點(diǎn)-->右子樹(shù)。

后序遍歷： 左子樹(shù)-->右子樹(shù)-->根結(jié)點(diǎn)。

根據(jù)遍歷特點(diǎn)，得出解題思路：

找到根-->找到左右子樹(shù)

一直重復(fù)這個(gè)操作，直到最后一個(gè)子節(jié)點(diǎn)。

題目一：求后序遍歷

題目： 已知前序遍歷 ABDGHCEIF 及中序遍歷 GDHBAEICF，求出后序遍歷順序？

解答：

先序遍歷的結(jié)果是ABDGHCEIF，根據(jù)先序得到根節(jié)點(diǎn)是A；中序遍歷的結(jié)果是GDHBAEICF，根據(jù)中序得到A之前的節(jié)點(diǎn)都是左子樹(shù)，A之后的節(jié)點(diǎn)都是右子樹(shù)。

再對(duì)左右子樹(shù)進(jìn)行第一步的分析。最終能得到二叉樹(shù)的完整結(jié)構(gòu)。

題目二：求前序遍歷

題目： 已知后序遍歷 GHDBIEFCA 及中序遍歷 GDHBAEICF，求出后序遍歷順序？

解答：

后序遍歷的結(jié)果是GHDBIEFCA，根據(jù)先序得到根節(jié)點(diǎn)是A；中序遍歷的結(jié)果是GDHBAEICF，根據(jù)中序得到A之前的節(jié)點(diǎn)都是左子樹(shù)，A之后的節(jié)點(diǎn)都是右子樹(shù)。

再對(duì)左右子樹(shù)進(jìn)行第一步的分析。最終能得到二叉樹(shù)的完整結(jié)構(gòu)。

總結(jié)一下

已知前序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹(shù)。

已知后序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹(shù)。

但是，已知前序和后序是不能確定一棵二叉樹(shù)的。

例如：前序遍歷序列為 ABC 及后序遍歷序列為 CBA。

可以確定 A 一定是根節(jié)點(diǎn)，但是接下來(lái)無(wú)法確定哪些是左子樹(shù)，哪些是右子樹(shù)。此時(shí)，這棵二叉樹(shù)有以下四種可能：