Swift實現-Tree(樹)、BaniryTree(二叉樹)、BinarySearchTree(二叉搜索樹)

圖一

一、樹

樹是一種一對多的，一種表示對象層級關系的數據結構。

術語及特點

  • 樹是有節(jié)點組成的，上一層節(jié)點是下一次節(jié)點的雙親，下一層節(jié)點是上一層節(jié)點的孩子，同一層的節(jié)點稱為兄弟。
  • 有孩子的節(jié)點為普通的節(jié)點，沒有孩子的節(jié)點也就是最下層的節(jié)點，稱為葉子節(jié)點，沒有雙親的節(jié)點稱為根節(jié)點。
  • 節(jié)點擁有子節(jié)點或者子樹的個數，稱為這個節(jié)點的度，數的度為節(jié)點最多的度，如圖一的度為3。
  • 樹的層級稱為樹的深度或高度，如圖一的深度為4.
  • 父節(jié)點與子節(jié)點之間，子節(jié)點的兄弟之間不能有環(huán)，這樣的不稱之為樹，而是圖。

普通樹的實現

class Node<T: Comparable> {
    //節(jié)點的值
    var value: T
    //孩子
    var children = [Node]()
    //雙親
    weak var parent: Node?
    
    init(_ value: T) {
        self.value = value
    }
    
    //添加孩子
    func add(child node: Node) {
        children.append(node)
        node.parent = self
    }
    //判斷樹中是否包含某個值
    func search(_ value: T) -> Node? {
        if value == self.value {
            return self
        }
        for child in children {
            if let result = child.search(value) {
                return result
            }
        }
        return nil
    }
}
extension Node: CustomStringConvertible {
    var description: String {
        var text = "\(value)"
        
        if !children.isEmpty {
            text += "{ " + children.map({ $0.description }).joined(separator: ", ") + " }"
        }
        return text
    }
}

說明：

  • Node<T: Comparable> 的寫法是，因為在 search(_ value: ) 方法中需要對泛型T進行比較，所以T需要遵守Comparable協議，也同樣可以遵守Equatable協議，達到同樣的目的
  • 在extension擴展中遵守CustomStringConvertible 協議，從而去自己實現description屬性，這樣方便查看打印，是個很不錯的調試辦法
  • 上面是一種比較普通的實現，節(jié)點包含有孩子及雙親屬性，但是雙親是可選型，因為根節(jié)點是沒有雙親的，再有雙親用weak修飾，防止雙親和自己之間產生循環(huán)引用
  • 根據不同的需求，有多種表示數的方法，比如雙親表示法（只表示雙親，不標識孩子）、孩子表示法、孩子兄弟表示法等等

二、二叉樹

如果一個樹，每個節(jié)點都有0個或1個或兩個孩子，則稱為二叉樹。
二叉樹的子節(jié)點通常稱為左孩子和右孩子。

特點

  • 二叉樹中沒個節(jié)點最多有兩個子節(jié)點
  • 二叉樹的左右兩個節(jié)點是有序的，不能左右互換，即使有一個子節(jié)點也要區(qū)分左右
  • 有一些特殊的二叉樹如：斜樹，滿二叉樹，完全二叉樹
  • 二叉樹的第i層最多有 2的(i-1)次冪個節(jié)點
  • 深度為k的二叉樹，總共最多有2的(k)次冪 - 1個節(jié)點

二叉樹的實現

1.類方法實現

class BinaryTreeClass<T: Comparable> {
    var value: T
    var leftTChild: BinaryTreeClass?
    var rightChild: BinaryTreeClass?
    
    init(_ value: T) {
        self.value = value
    }
}

上面是用類方法實現的二叉樹，每個節(jié)點值，左孩子，及有孩子，但是也可能沒有孩子，所以兩個孩子是可選型，但是因為在Swift中是比較提倡用Struct 及 enum 代替類的，即用值類型，代替引用類型（當然要具體情況具體分析，但是總體是這樣的），所以下面就詳細的用enum來實現二叉樹

  1. 枚舉實現
indirect enum BinaryTree<T: Comparable> {
    case node(BinaryTree<T>, T, BinaryTree<T>)
    case empty
}
  • 二叉樹的節(jié)點分為兩種狀態(tài)，要么為空，要么不為空，同時有左右孩子

  • indirect關鍵字：在Swift中，如果創(chuàng)建一個值類型，系統(tǒng)要明確的知道這個值類型需要的內存大小，好給其分配適當的內存。但是在上面的代碼中 .node中引用了它自己，這就產生了遞歸，這樣系統(tǒng)就不能明確的知道這個值類型所需要的內存的大小，所以我們要用indirect關鍵字來標明，這樣系統(tǒng)會為循環(huán)引用之間產生一個layer，來解決這個問題（具體咋回事沒弄明白...官方文檔上也沒說清楚，估計就是分配了一個可變的內存吧）
    利用上面我們定義的BinaryTree，來表示下圖的二叉樹：


let nodeI = BinaryTree.node(.empty, "I", .empty)

let nodeG = BinaryTree.node(.empty, "G", .empty)
let nodeH = BinaryTree.node(nodeI, "H", .empty)
let nodeJ = BinaryTree.node(.empty, "J", .empty)
        
let nodeD = BinaryTree.node(nodeG, "D", nodeH)
let nodeE = BinaryTree.node(.empty, "E", nodeJ)
let nodeF = BinaryTree.node(.empty, "F", .empty)
        
let nodeB = BinaryTree.node(nodeD, "B", .empty)
let nodeC = BinaryTree.node(nodeE, "C", nodeF)
    
let nodeA = BinaryTree.node(nodeB, "A", nodeC)
print(nodeA)
//value: A, A-left: [ value: B, B-left: [ value: D, D-left: [ value: G, G-left: [  ], G-right: [  ] ], D-right: [ value: H, H-left: [ value: I, I-left: [  ], I-right: [  ] ], H-right: [  ] ] ], B-right: [  ] ], 
            A-right: [ value: C, C-left: [ value: E, E-left: [  ], E-right: [ value: J, J-left: [  ], J-right: [  ] ] ], C-right: [ value: F, F-left: [  ], F-right: [  ] ] ]

注意代碼實現的時候通常是從小向上來實現節(jié)點

  • 節(jié)點個數
func count() -> Int {
        switch self {
        case let .node(left, _, right):
            return left.count() + 1 + right.count()
        case .empty:
            return 0
        }
    }
print(nodeA.count()) 
//10
  • 二叉樹節(jié)點的遍歷
    有時需要以某種順序遍歷樹的所有節(jié)點，這就叫樹的遍歷，通常以訪問根節(jié)點的先后順序，分三種方式，前序、中序及后序遍歷
//MARK: -中序遍歷
    func traverseInOrder(process: (T) -> Void) {
        if case let .node(left, value, right) = self {
            left.traverseInOrder(process: process)
            process(value)
            right.traverseInOrder(process: process)
        }
    }
    //MARK: -前序遍歷
    func traversePreOrder(process: (T) -> Void) {
        if case let .node(left, value, right) = self {
            process(value)
            left.traversePreOrder(process: process)
            right.traversePreOrder(process: process)
        }
    }
    //MARK: -后序遍歷
    func traversePostOrder(process: (T) -> Void) {
        if case let .node(left, value, right) = self {
            left.traversePostOrder(process: process)
            right.traversePostOrder(process: process)
            process(value)
        }
    }

其中 if case let .node(left, value, right) = self 語法，同swich 語法有相同的效果，只不過現在是只判斷一種case 的情況，即如果當前樹不為空

三、二叉搜索樹

  • 特點
    二叉搜索樹是一種特殊的二叉樹，它的左孩子的值一定小于雙親的值，右孩子的值一定大于雙親的值，即整個二叉搜索樹是有序的，及時是刪除及插入節(jié)點后，也同樣保持有序
  • 插入
    在二叉搜索樹中插入新的節(jié)點，要記住及維持“左孩子的值一定小于雙親的值，右孩子的值一定大于雙親的值”的特點
//1
mutating func inset(_ newValue: T) {
        //2 
        guard case .node(var leftTree, let value, var rightTree) = self else {
            self = .node(.empty, newValue, .empty)
            return
        }

        //3
        if newValue > value {
            rightTree.inset(newValue)
        }else if newValue < value {
            leftTree.inset(newValue)
        }
    }

說明：
1.當我們在值類型(枚舉和結構體)的實例方法中，改變其屬性或者self的時候，我們需要在這個方法前面的顯性的標注mutating關鍵字
2.如果為空節(jié)點，則給self一個新的值
3.如果當前節(jié)點不為空，則比較大小，到左或右孩子中插入

/好的我們的實現完成了，但是運行代碼我們會發(fā)現，結果和我們的預期是有出入的，你所要插入的新節(jié)點并沒有出現在樹中/
這是因為當前的樹是通過值類型實現的，當我們調用 rightTree.inset(newValue) 或 leftTree.inset(newValue) 方法時，程序會重新復制一份新的 rightTree 和 leftTree，接著去新的樹上執(zhí)行方法，而不是在當前樹的孩子上執(zhí)行。如果我們是用通過類來實現樹的結構的，那么當前的方法就完全沒有問題了

  • 插入-改
mutating func inset(_ newValue: T) {
     self = newTreeWithNewValue(newValue)
 }

private func newTreeWithNewValue(_ newValue: T) -> BinaryTree {
        switch self {
        case .empty:
            return .node(.empty, newValue, .empty)
        case let .node(leftTree, value, rightTree):
            if newValue < value {
                return .node(leftTree.newTreeWithNewValue(newValue), value, rightTree)
            }else {
                return .node(leftTree, value, rightTree.newTreeWithNewValue(newValue))
            }
        }
    }

//當每次新值插入時，都創(chuàng)建一棵新樹，來重新賦值替代原來的樹，這樣就不會出問題了
但是由于每次插入都需要創(chuàng)建一顆新的樹，所以插入時的時間復雜度為O(n)，效率比較低下，如果是通過類方法創(chuàng)建的樹，插入的時間復雜度則為O(log n)

  • 搜索
func search(_ sValue: T) -> BinaryTree? {
        guard case let .node(leftTree, value, rightTree) = self else {
            return nil
        }
        if sValue == value {
            return self
        }
        if sValue > value {
            return rightTree.search(sValue)
        }else {
            return leftTree.search(sValue)
        }
    }
  • 刪除節(jié)點
    刪除節(jié)點后，如果該節(jié)點有子數，需要將子樹重新連接到原來的樹上，即從原來的子樹中找一個接地，替代當前的節(jié)點，替換的原則是，從該節(jié)點的左子樹中，找一個最大的，或者從該節(jié)點的右子樹中，找一個最小的，替代原有的位置。如果該節(jié)點沒有子節(jié)點，則直接刪除這個節(jié)點就好了，如果實現該方法，我們需要在節(jié)點的結構中增加對父母節(jié)點的記錄，這里我們就不做實現了

前面說過，二叉樹因為不同功能需要，有多重實現辦法，當前這種實現知識最近本的實現方法，如果需要其他更多的功能，可以給樹添加更多的屬性來實現具體的功能，后面會用類實現一個更完整的方法，敬請期待??

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

  • 樹的概述 樹是一種非常常用的數據結構，樹與前面介紹的線性表，棧，隊列等線性結構不同，樹是一種非線性結構 1.樹的定...
    Jack921閱讀 4,758評論 1贊 31
  • 提示：本篇的原文已經在github上有所更新，想看最新版的朋友們抱歉了... 二叉查找樹（英語：Binary Se...
    云抱住陽光太陽沒放棄發(fā)亮閱讀 1,163評論 0贊 2
  • 概述# 二叉樹是一種特殊的樹型結構，它由結點的有限集合構成。 二叉樹是由唯一的起始結點引出的結點集合。這個起始節(jié)點...
    長胖的魚閱讀 1,227評論 0贊 8
  • 在談具體的激勵措施之前，我覺得應該探討一下激勵或懲罰的本質。 商鞅變法后的秦朝，老百姓聞戰(zhàn)則喜，因為“能得甲首一者...
    思想磨坊閱讀 453評論 0贊 0
  • 找工作被拒、相親失敗，恩美的開啟了失眠模式。人生到底該怎樣走，成了她日落以后、日出之前整夜思考的問題。 早上6點半...
    THISIMPLE閱讀 550評論 0贊 0

友情鏈接更多精彩內容