자료구조 | Ch01. Trees

1. Tree란?

Tree는 list, stack, queue와 달리 none-linear 구조 이다. Tree는 root와 leaf, interior nodes로 구성되어있다. 

• Root node : parent node가 없는 node이다. Tree의 시작 node.
• Leaf node : child node가 없는 node이다.
• Interior node : root node나 leaf node가 아닌 node.
• Sibling node : 같은 parent node를 가진 node.
• Descendant node : 노드의 Child node의 Child를 한 node의 descendant라고 정의한다. 
• Ancestor node : 노드의 Parent node의 parent를 한 node의 ancestor라고 정의한다.
• node의 Depth(Height, Level) : root node의 Depth를 1 또는 0으로 정하여 깊이를 나타낸다.
• node의 Degree(Fanout) : node의 Child node의 개수이다. ex) A node의 Degree == 2

Tree라고 정의하기 위해서는 아래 조건을 만족해야 한다.

1. Root node가 아닌 node들은 오직 하나의 parent node를 가진다. (root node는 parent node가 없다.)
2. Leaf node가 아닌 node들은 하나 이상의 child node를 가진다. (leaf node는 child node가 없다.)

Tree는 linked list로 구성하여 서로 연결 할 수 있도록 구현한다. 또 data item을 찾을 때 특정 관계를 만족하는 다른 데이터로 나아가며 찾는다. (때문에 linked list로 구현해야하는 것!) Tree의 계층은 data item 사이의 관계를 시각적으로 나타내는데 용이하다.

2. Tree의 Traversal

Tree의 Traversal은 말 그대로 Tree의 node를 순회한다는 말이다. 순회 방법에는 여러가지가 있는데 node를 들린 후, data를 프린트 하거나 stack에 넣거나, 복사하는등 어떤 행동을 취하고 node의 다른 node로 넘어가며 순회한다.

• Breadth-First Traversal (Level Order Traversal )
  :동일한 level의 모든 node를 들린 후, 다음 level로 넘어간다. tree는 left-first-right-later이기 때문에 왼쪽 node에서 부터 오른쪽으로 이동하며 visit node한다.
• Depth-First Traversal
  :root 방문 기준으로 세가지 방법으로 나뉜다.
  
  • Inorder Traversal : Left Subtree -> Visit the Root -> Right Subtre 
    이 traversal은 오직 binary Tree에서만 가능하다.
  • Postorder Traversal : Left Subtree -> Right Subtree -> Visit the Root
  • Preorder Traversal : Visit the Root -> Left Subtree -> Right Subtree