이진트리(binary tree), 이진트리 순회방법

이진트리(binary tree), 이진트리 순회방법

이진트리 : 부모 하나에 자식이 둘 딸린 구조

이진트리 구조

1.1 이진트리 종류

Binary Tree(기본)

다른 조건 없이 자식노드가 2개씩만 붙어 있음됌

Binary Search Tree

안에 데이터가 왼쪽 노드와 그 이하의 자식 도드들은 현재 노드 보다 작아야 함

오른쪽 노드와 그 이하 자식 노드들은 현재노드(8) 보다 커야함

Balance

UnBalance

Complete Bianry Tree(완전이진트)

모든 노드들이 왼쪽부터 채워져 있고 마지막 레벨은 왼쪽부터 채워져 있다

Full Bianry Tree

자식노드가 아예 없거나 2개로 구성된 Tree

Perfect Bianry Tree

모든 노드가 2개의 자식노드로 구성된 트리

1.2 이진트리 순회방법

Root(==N)

PreOrder(전위 순회)

현재노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회하는 방식

Root(==N) Left Right

InOrder(중위 순회)

왼쪽 서브 트리 -> 현재노드 -> 오른쪽 서브 트리 순으로 순회하는 방식

Left Root right

PostOrder(후위 순회)

왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 현재노드 순회하는 방식

Left Right Root

from http://wwit5073.tistory.com/147 by ccl(A) rewrite - 2021-08-25 21:26:18