CS)ツリー、グラフィック

13144 ワード
avl BST Red-black tree CS Graph テキストリンク
https://github.com/raywenderlich/swift-algorithm-club/blob/master/Tree/README.markdown

木。


ツリーは、オブジェクト間の階層関係を表します.
ツリーは노드で構成され、ノードはサブノードに接続されています.子供は何人もいます.
親ノードなしはroot node、子ノードなしはleaf nodeです.

ツリーは階層構造なので、ループは形成されません.
以下のループを形成する構造をグラフと呼ぶ.

インプリメンテーション


次のコードは普通の木です.
class TreeNode<T> {
    var value: T
    
    weak var parent: TreeNode<T>?
    var child: [TreeNode<T>] = []
    
    init(value: T) {
        self.value = value
    }
    
    func addChild(_ node: TreeNode<T>) {
        child.append(node)
        node.parent = self
    }
}
次に定義すると、ツリーを構築できます.
let tree = TreeNode<String>(value: "beverages")

let hotNode = TreeNode<String>(value: "hot")
let coldNode = TreeNode<String>(value: "cold")

let teaNode = TreeNode<String>(value: "tea")
let coffeeNode = TreeNode<String>(value: "coffee")
let chocolateNode = TreeNode<String>(value: "cocoa")

let blackTeaNode = TreeNode<String>(value: "black")
let greenTeaNode = TreeNode<String>(value: "green")
let chaiTeaNode = TreeNode<String>(value: "chai")

let sodaNode = TreeNode<String>(value: "soda")
let milkNode = TreeNode<String>(value: "milk")

let gingerAleNode = TreeNode<String>(value: "ginger ale")
let bitterLemonNode = TreeNode<String>(value: "bitter lemon")

tree.addChild(hotNode)
tree.addChild(coldNode)

hotNode.addChild(teaNode)
hotNode.addChild(coffeeNode)
hotNode.addChild(chocolateNode)

coldNode.addChild(sodaNode)
coldNode.addChild(milkNode)

teaNode.addChild(blackTeaNode)
teaNode.addChild(greenTeaNode)
teaNode.addChild(chaiTeaNode)

sodaNode.addChild(gingerAleNode)
sodaNode.addChild(bitterLemonNode)

こうしん


木の高さは根から子線までの数、木の高さは3です.
ツリーの深さは、ノードからルートノードへの線の数です.teaを例にとると、ルートまで2本の線があり、深さは2である.

構成


木はいろいろな方法で構築できます.親プロパティを変更する必要がない場合があります.バイナリツリーでは、最大2つのサブツリーしか与えられません.非常に一般的な形式はバイナリ検索ツリーです.
ここに示す一般的なツリーは、階層化データの説明に役立ちますが、実際に必要な追加機能はアプリケーションによって異なります.

探索する

extension Node {
  // 1
  func search(value: String) -> Node? {
    // 2
    if value == self.value {
      return self
    }
    // 3
    for child in children {
      if let found = child.search(value: value) {
        return found
      }
    }
    // 4
    return nil
  }
}
リデス・ミデルWare
Into the Typescript 3