10000 Merge pull request #499 from remlostime/decode-tree · jerrytdev/swift-algorithm-club@84aaeb6 · GitHub
[go: up one dir, main page]
Skip to content

Commit 84aaeb6

Browse files
kelvinlauKLkelvinlauKL
authored
Merge pull request kodecocodes#499 from remlostime/decode-tree
Encode and Decode A Binary Tree
2 parents 7cb6cf6 + 074dac2 commit 84aaeb6

File tree

6 files changed

+449
-0
lines changed

6 files changed

+449
-0
lines changed

‎Encode and Decode Tree/EncodeAndDecodeTree.playground/Contents.swift

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
//: Playground - noun: a place where people can play
2+
3+
func printTree(_ root: BinaryNode<String>?) {
4+
guard let root = root else {
5+
return
6+
}
7+
8+
let leftVal = root.left == nil ? "nil" : root.left!.val
9+
let rightVal = root.right == nil ? "nil" : root.right!.val
10+
11+
print("val: \(root.val) left: \(leftVal) right: \(rightVal)")
12+
13+
printTree(root.left)
14+
printTree(root.right)
15+
}
16+
17+
let coder = BinaryNodeCoder<String>()
18+
19+
let node1 = BinaryNode("a")
20+
let node2 = BinaryNode("b")
21+
let node3 = BinaryNode("c")
22+
let node4 = BinaryNode("d")
23+
let node5 = BinaryNode("e")
24+
25+
node1.left = node2
26+
node1.right = node3
27+
node3.left = node4
28+
node3.right = node5
29+
30+
let encodeStr = try coder.encode(node1)
31+
print(encodeStr)
32+
// "a b # # c d # # e # #"
33+
34+
35+
let root: BinaryNode<String> = coder.decode(from: encodeStr)!
36+
print("Tree:")
37+
printTree(root)
38+
/*
39+
Tree:
40+
val: a left: b right: c
41+
val: b left: nil right: nil
42+
val: c left: d right: e
43+
val: d left: nil right: nil
44+
val: e left: nil right: nil
45+
*/
46+

‎Encode and Decode Tree/EncodeAndDecodeTree.playground/Sources/EncodeAndDecodeTree.swift

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
//
2+
// EncodeAndDecodeTree.swift
3+
//
4+
//
5+
// Created by Kai Chen on 19/07/2017.
6+
//
7+
//
8+
9+
import Foundation
10+
11+
protocol BinaryNodeEncoder {
12+
func encode<T>(_ node: BinaryNode<T>?) throws -> String
13+
}
14+
15+
protocol BinaryNodeDecoder {
16+
func decode<T>(from string: String) -> BinaryNode<T>?
17+
}
18+
19+
public class BinaryNodeCoder<T: Comparable>: BinaryNodeEncoder, BinaryNodeDecoder {
20+
21+
// MARK: Private
22+
23+
private let separator: Character = ","
24+
private let nilNode = "X"
25+
26+
private func decode<T>(from array: inout [String]) -> BinaryNode<T>? {
27+
guard !array.isEmpty else {
28+
return nil
29+
}
30+
31+
let value = array.removeLast()
32+
33+
guard value != nilNode, let val = value as? T else {
34+
return nil
35+
}
36+
37+
let node = BinaryNode<T>(val)
38+
node.left = decode(from: &array)
39+
node 10000 .right = decode(from: &array)
40+
41+
return node
42+
}
43+
44+
// MARK: Public
45+
46+
public init() {}
47+
48+
public func encode<T>(_ node: BinaryNode<T>?) throws -> String {
49+
var str = ""
50+
node?.preOrderTraversal { data in
51+
if let data = data {
52+
let string = String(describing: data)
53+
str.append(string)
54+
} else {
55+
str.append(nilNode)
56+
}
57+
str.append(separator)
58+
}
59+
60+
return str
61+
}
62+
63+
public func decode<T>(from string: String) -> BinaryNode<T>? {
64+
var components = string.split(separator: separator).reversed().map(String.init)
65+
return decode(from: &components)
66+
}
67+
}
68+
69+
public class BinaryNode<Element: Comparable> {
70+
public var val: Element
71+
public var left: BinaryNode?
72+
public var right: BinaryNode?
73+
74+
public init(_ val: Element, left: BinaryNode? = nil, right: BinaryNode? = nil) {
75+
self.val = val
76+
self.left = left
77+
self.right = right
78+
}
79+
80+
public func preOrderTraversal(visit: (Element?) throws -> ()) rethrows {
81+
try visit(val)
82+
83+
if let left = left {
84+
try left.preOrderTraversal(visit: visit)
85+
} else {
86+
try visit(nil)
87+
}
88+
89+
if let right = right {
90+
try right.preOrderTraversal(visit: visit)
91+
} else {
92+
try visit(nil)
93+
}
94+
}
95+
}

‎Encode and Decode Tree/EncodeAndDecodeTree.playground/contents.xcplayground

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
2+
<playground version='5.0' target-platform='ios'>
3+
<timeline fileName='timeline.xctimeline'/>
4+
</playground>

‎Encode and Decode Tree/EncodeAndDecodeTree.swift

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
//
2+
// EncodeAndDecodeTree.swift
3+
//
4+
//
5+
// Created by Kai Chen on 19/07/2017.
6+
//
7+
//
8+
9+
import Foundation
10+
11+
protocol BinaryNodeEncoder {
12+
func encode<T>(_ node: BinaryNode<T>?) throws -> String
13+
}
14+
15+
protocol BinaryNodeDecoder {
16+
func decode<T>(from string: String) -> BinaryNode<T>?
17+
}
18+
19+
public class BinaryNodeCoder<T: Comparable>: BinaryNodeEncoder, BinaryNodeDecoder {
20+
21+
// MARK: Private
22+
23+
private let separator: Character = ","
24+
private let nilNode = "X"
25+
26+
private func decode<T>(from array: inout [String]) -> BinaryNode<T>? {
27+
guard !array.isEmpty else {
28+
return nil
29+
}
30+
31+
let value = array.removeLast()
32+
33+
guard value != nilNode, let val = value as? T else {
34+
return nil
35+
}
36+
37+
let node = BinaryNode<T>(val)
38+
node.left = decode(from: &array)
39+
node.right = decode(from: &array)
40+
41+
return node
42+
}
43+
44+
// MARK: Public
45+
46+
public init() {}
47+
48+
public func encode<T>(_ node: BinaryNode<T>?) throws -> String {
49+
var str = ""
50+
node?.preOrderTraversal { data in
51+
if let data = data {
52+
let string = String(describing: data)
53+
str.append(string)
54+
} else {
55+
str.append(nilNode)
56+
}
57+
str.append(separator)
58+
}
59+
60+
return str
61+
}
62+
63+
public func decode<T>(from string: String) -> BinaryNode<T>? {
64+
var components = string.split(separator: separator).reversed().map(String.init)
65+
return decode(from: &components)
66+
}
67+
}
68+
69+
public class BinaryNode<Element: Comparable> {
70+
public var val: Element
71+
public var left: BinaryNode?
72+
public var right: BinaryNode?
73+
74+
public init(_ val: Element, left: BinaryNode? = nil, right: BinaryNode? = nil) {
75+
self.val = val
76+
self.left = left
77+
self.right = right
78+
}
79+
80+
public func preOrderTraversal(visit: (Element?) throws -> ()) rethrows {
81+
try visit(val)
82+
83+
if let left = left {
84+
try left.preOrderTraversal(visit: visit)
85+
} else {
86+
try visit(nil)
87+
}
88+
89+
if let right = right {
90+
try right.preOrderTraversal(visit: visit)
91+
} else {
92+
try visit(nil)
93+
}
94+
}
95+
}

0 commit comments

Comments
 (0)
0