이진 트리

위키백과 ― 우리 모두의 백과사전.

전산학에서 이진 트리 (binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 그래프 이론(Graph theories)에서 그래프의 특별한 형태를 우리는 이진트리(binary tree)로서 표시한다. 루트노드(Root Node)에서 시작한 각 노드는 최대한 두개의 자식노드(kindnode)가질수 있으며,그 자식노드는 정확히 왼쪽과 오른쪽노드로 분할할 수 있다.

정형적인 정의(formal definition):이진 트리는 빈 트리이거나 왼쪽과 오른쪽 자식노드-이 자식노드는 또한 재차 이진트리를 구성-를 가진 루트노드로 구성된다.

이진트리의 특징(chracteristics of the binary tree): h=높이(height>=0),n=numbers(노드수),i=level(>=0)라고 하자.

1. n=(# 외부노드=잎노드)+(# 내부노드).

2. (# 외부노드)=(#내부노드)+1.

3. (#노드 on level-i)<=2^i

4. h+1 <= (#외부노드) <= 2^h

5. log(#외부노드)<= h

6. h+1 <= (#외부노드) <= 2^h

이진 트리
이진 트리
이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.


[편집] 참고문헌(References)

...after learning how to use LaTex...