[Data Structure / Algorithms] Binary Trees (2)

전성훈·2023년 11월 4일

Algorithms datastructure swift

Data Structure-Algorithm

목록 보기

12/35

주제: 이진 트리

특징

이진 트리는 각 노드가 최대 두 개의 자식(왼쪽, 오른쪽)을 가지는 트리이다.
이진 트리는 많은 트리 구조와 알고리즘의 기초 역할을 한다.
이진 트리는 이진 탐색 트리와 AVL 트리와 같이 삽입/삭제 동작에 제한을 두는 이진 트리이다.
중위(In-order), 전위(Pre-order) 및 후위(Post-order) 순회는 이진 트리뿐만 아니라 다른 모든 트리 구조에서 중요하며, 트리에서 데이터를 처리할 때 이러한 순회 방법을 자주 사용한다.

구현

public class BinaryNode<Element> { 
	public var value: Element
	public var leftChild: BinaryNode?
	public var rightChild: BinaryNode?
	
	public init(value: Element) { 
		self.value = value
	}
}

var tree: BinaryNode<Int> = {
  let zero = BinaryNode(value: 0)
  let one = BinaryNode(value: 1)
  let five = BinaryNode(value: 5)
  let seven = BinaryNode(value: 7)
  let eight = BinaryNode(value: 8)
  let nine = BinaryNode(value: 9)

  seven.leftChild = one
  one.leftChild = zero
  one.rightChild = five
  seven.rightChild = nine
  nine.leftChild = eight

  return seven
}()

extension BinaryNode: CustomStringConvertible { 
	public var description: String { 
		diagram(for: self)
	}
	
	private func diagram(for node: BinaryNode?, 
										_ top: String = "",
										_ root: String = "",
										_ bottom: String = "" 
	) -> String { 
		guard let node = node else { 
			return root + "nil \n"
		}
		if node.leftChild == nil && node.rightChild == nil { 
			return root + "\(node.value)\n"
		}
		return diagram(for: node.rightChild, top + " ", top + "┌──", top + "| " ) + root + "\(node.value)\n" + diagram(**for**: node.leftChild, bottom + "│ ", bottom + "└──", bottom + " ")
	}
}

print(tree)

 ┌──nil
┌──9
| └──8
7
│ ┌──5
└──1
 └──0

Traversal algorithms

In-order traversal(중위 순회)

루트 노드부터 시작히며, 현재 노드가 왼쪽 자식을 가지고 있다면, 먼저 이 자식을 재귀적으로 방문한다.
그런 다음, 노드 자체를 방문한다.
현재 노드가 오른쪽 자식을 가지고 있다면, 이 자식을 재귀적으로 방문한다.
- 예제 트리를 오름차순으로 방문하는 것을 알 수 있다. 트리가 AVL 트리(자가 균형 이진 탐색 트리)일 경우, 중위 순회는 오름차순으로 노드를 방문한다.

extension BinaryNode { 
	public func traverseInOrder(visit: (Element) -> Void) { 
		leftChild?.traverseInOrder(visit: visit)
		visit(value)
		rightChild?.traverseInOrder(visit: visit)
	}
}

tree.traverseInOrder { print($0, terminator: " ")}

0 1 5 7

Pre-order traversal(전위 순회)

전위 순회는 현재 노드를 방문하고 그 다음 재귀적으로 왼쪽 자식과 오른쪽 자식을 방문한다.

extension BinaryNode { 
	public func traversePreOrder(visit: (Element?) -> Void) { 
		visit(value)
		if let leftChild = leftChild { 
			leftChild.traversePreOrder(visit: visit)
		} else { 
			visit(nil)
		}
		if let rightChild = rightChild { 
			rightChild.traversePreOrder(visit: visit)
		} else { 
			visit(nil)
		}
	}
}

tree.traversePreOrder { print($0, terminator: " ") }
print()

7 1 0 nil nil 5 nil nil 9 8 nil nil nil

Post-order traversal(후위 순회)

현재 노드의 왼쪽, 오른쪽 자식 노드를 먼저 재귀적으로 방문 후 현재 노드를 방문한다.

extension BinaryNode { 
	public func traversePostOrder(visit: (Element) -> Void) { 
		leftChild?.traversePostOrder(visit: visit)
		rightChild?.traversePostOrder(visit: visit)
		visit(value)
	}
}

tree.traversePostOrder { print($0, terminator: " ")}
print()

0 5 1 8 9 7

Tree 높이 찾기

func height<T>(of node: BinaryNode<T>? ) -> Int { 
	guard let node = node else { 
		return 0
	}
	return 1 + max(height(of:node.leftChild), height(of:node.rightChild))
}

height(of: tree)

3