[Datastructure] Tree / Binary Tree

Tree

tree는 계층적인 트리 구조로, root value와 subtree(부모 노드와 자식을 가지는)를 가진다.

Binary Tree

A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

부모 노드가 자식노드 2개를 가진 자료구조를 Binary Tree(이진트리) 라고 한다. 엘리먼트들은 자식노드를 2개만 가져야 하며 보통 letf child와 right child로 불린다.

Main applications of trees include:
1. Manipulate hierarchical data.
2. Make information easy to search (see tree traversal).
3. Manipulate sorted lists of data.
4. As a workflow for compositing digital images for visual effects.
5. Router algorithms
6. Form of a multi-stage decision-making (see business chess).

 

Tree Traversals (Inorder, Preorder and Postorder)

트리의 순회는 선형적인 자료구조(array, linked list, queue, stack) 과는 다르게 순회를 하게 된다.

부모 노드와 자식노드를 하나의 depth로 한다면, 

깊이 우선 탐색(dfs)은 3가지로 나눌수 있다.

• (a) Inorder (Left, Root, Right) : 4 2 5 1 3
• (b) Preorder (Root, Left, Right) : 1 2 4 5 3
• (c) Postorder (Left, Right, Root) : 4 5 2 3 1

순회 알고리즘을보면,

Algorithm Inorder(tree)
   1. Traverse the left subtree, i.e., call Inorder(left-subtree)
   2. Visit the root.
   3. Traverse the right subtree, i.e., call Inorder(right-subtree)

Algorithm Preorder(tree)
   1. Visit the root.
   2. Traverse the left subtree, i.e., call Preorder(left-subtree)
   3. Traverse the right subtree, i.e., call Preorder(right-subtree) 

Algorithm Postorder(tree)
   1. Traverse the left subtree, i.e., call Postorder(left-subtree)
   2. Traverse the right subtree, i.e., call Postorder(right-subtree)
   3. Visit the root.

순서의 차이만 가지고 있고 3가지 모두 재귀적인 방법을써서 순회를 하고 있다.