[DS] 트리(Tree)와 이진트리(Binary Tree)란?

트리(Tree)란?

트리(Tree)는 node로 이루어진 계층적 종속관계를 표현하는 비선형 자료구조입니다.

- Root라는 특별한 node가 존재

- root와 연결된 n(>=0)개의 subtree로 구성

- subtree도 각각의 tree임

- 사이클(cycle)이 존재할 수 X

 

 

 

트리(Tree) 관련 용어(Terminology)

---

Node - tree에서 data를 저장하는 기본 단위 원소

Root - 가장 상위에 있는 한 개의 node

Branch - node와 node간의 연결 (parent - child)

 <Parent - child, children> - branch로 연결된 두 node의 관계

Sibling - 동일한 parent를 갖는 nodes

 

Degree - node의 차수

Degree of a node - node subtree의 개수

Degree of a tree - node 차수의 최댓값

Leaf(=terminal node) - degree가 0인 node(child가 없는 node)

Internal node - degree가 0보다 큰 node(child를 갖는 node)

Subtree - 원 tree의 부분 집합으로 이루어진 tree

 

Ancestors - 자신과 root와의 path 상에 존재하는 nodes

Descendants - 자신과 직접 또는 간접적으로 연결된 하위 nodes

Level - root를 1로 했을 때 root와의 상대적 거리

Height(=depth) - tree의 최대 상대적 거리

 

 

 

이진트리(Binary tree)란?

---

각 노드가 최대 두 개의 자식을 갖는 트리입니다.

 

- 유한개(>=0)의 node로 이루어짐

- empty이거나 root와 두개의 disjoint binary tree로 구성됨

 

이진트리(binary tree)에는 순서(order)가 있습니다.

Disjoint binary tree

- left subtree

- right subtree

 

 

 

트리(Tree)와 이진트리(binary tree)

---

트리(Tree)의 node 구조는 data를 저장하는 공간과, children을 가르키는 pointer로 구성되어 있습니다.

 

 

이진트리(Binary tree)의 node 구조는 data를 저장하는 공간과 left child, right child를 가르키는 pointer로 구성되어 있습니다.

 

 

↓↓↓     트리(tree)에서 이진트리(binary tree)로 변환하는 방법    ↓↓↓

https://yyyeji.tistory.com/369

[DS] 트리(Tree)에서 이진트리(Binary Tree)로 변환하는 방법

 

 

 

◡̈