摘要：鏈式存儲結構由于二叉樹的每個結點最多有兩個孩子，所以為每個結點設計一個數據域和兩個指針域。最終能得到二叉樹的完整結構。

這篇文章主要介紹樹結構中的一種特殊存在——二叉樹。主要內容有：

二叉樹的概念

二叉樹的基本結構

二叉樹的操作

二叉樹： 每個結點最多有兩個子結點，兩個子結點是有次序的，且子結點次序不能顛倒。兩個子結點一般稱之為左結點及右結點。

層次： 在樹中，節(jié)點的層次從根開始定義，根為第一層。

深度： 樹中節(jié)點的最大層次為樹的深度。

度： 結點擁有的結點數。

分支結點： 度不為0的結點。

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

特殊二叉樹

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

斜樹：所有的結點都只有左子結點或者右子結點。

完全二叉樹：對一棵具有n個結點的二叉樹按層序編號，如果編號i（1<=i<=n）的結點 與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置完全相同，則稱之為完全二叉樹。

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

二叉樹的順序存儲結構就是用一維數組存儲二叉樹中的結點，并且結點的存儲位置，也就是數組的下標要能體現結點之間的邏輯關系。使用順序存儲結構表現二叉樹的時候，在其線性結構中，會存在一些空結點，但是其會占據一定的內存空間，會造成存儲空間的浪費。

由于二叉樹的每個結點最多有兩個孩子，所以為每個結點設計一個數據域和兩個指針域。

結點的結構定義：

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

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

為了能讓每個結點確認是否有左右子結點，我們將預期二叉樹進行一個擴展：

我們給每一個結點的空指針引出一個虛結點，其值為一個特定值——#。

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

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 {
        // 生成根結點
        tree = BinaryTreeNode(value)

        // 構造左子樹
        preCreateTree(&tree!.leftChild)

        // 構造右子樹
        preCreateTree(&tree!.rightChild)
    }
}

var root: BinaryTreeNode");

二叉樹的遍歷主要分為四種：

前序遍歷： 根結點-->左子樹-->右子樹。

中序遍歷： 左子樹-->根結點-->右子樹。

后序遍歷： 左子樹-->右子樹-->根結點。

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

前序遍歷

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

就是根據前序遍歷擴展二叉樹的結果得到的這個數組，并利用這個數組前序創(chuàng)建了我們預期的二叉樹。

前序遍歷代碼：

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

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

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

中序遍歷

中序遍歷代碼：

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

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

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

后序遍歷

后序遍歷代碼：

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

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

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

層序遍歷

層序遍歷代碼：

func levelOrdertraverse(_ tree: BinaryTreeNode");let root = tree else {
        return
    }
    
    var tempQueue: [BinaryTreeNode] = []
    
    // 將根節(jié)點加入數組
    if let _ = root.value {
        tempQueue.insert(root, at: 0)
    }
    
    while tempQueue.count != 0 {
    	  // 取出數組最后一個元素
        let temp = tempQueue.popLast()!
        
        // 將下一層結點依次插入到數組最前面
        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
}

遍歷特點：

前序遍歷： 根結點-->左子樹-->右子樹。

中序遍歷： 左子樹-->根結點-->右子樹。

后序遍歷： 左子樹-->右子樹-->根結點。

根據遍歷特點，得出解題思路：

找到根-->找到左右子樹

一直重復這個操作，直到最后一個子節(jié)點。

題目一：求后序遍歷

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

解答：

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

再對左右子樹進行第一步的分析。最終能得到二叉樹的完整結構。

題目二：求前序遍歷

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

解答：

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

再對左右子樹進行第一步的分析。最終能得到二叉樹的完整結構。

總結一下

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

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

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

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

可以確定 A 一定是根節(jié)點，但是接下來無法確定哪些是左子樹，哪些是右子樹。此時，這棵二叉樹有以下四種可能：