여기에서 우리는 컴퓨터 메모리에서 이진 트리를 표현하는 방법을 볼 것입니다. 나타내는 두 가지 방법이 있습니다. 배열을 사용하고 연결 리스트를 사용하고 있습니다.
다음과 같은 트리가 하나 있다고 가정해 보겠습니다. -
배열 표현은 레벨 순서 방식을 사용하여 요소를 스캔하여 트리 데이터를 저장합니다. 따라서 레벨별로 노드를 저장합니다. 일부 요소가 누락된 경우 공백이 남습니다. 위 트리의 표현은 아래와 같다 -
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 10 | 5 | 16 | - | 8 | 15 | 20 | - | - | - | - | - | - | - | 23 |
인덱스 1은 루트를 유지하고 있으며 두 개의 하위 5와 16이 있으며 위치 2와 3에 배치됩니다. 일부 하위가 누락되어 해당 위치가 공백으로 남습니다.
이 표현에서 우리는 다음 공식을 사용하여 한 노드의 두 자식 위치를 쉽게 얻을 수 있습니다 -
$$child_{1}=2*부모$$
$$child_{2}=\lgroup2*parent\rgroup+1$$
자식으로부터 부모 인덱스를 얻으려면 다음 공식을 따라야 합니다 -
$$parent=\begin{bmatrix}\frac{child}{2} \end{bmatrix}$$
이 접근 방식은 훌륭하고 부모와 자식의 인덱스를 쉽게 찾을 수 있지만 메모리 효율적이지 않습니다. 그것은 사용하지 않는 많은 공간을 차지할 것입니다. 이 표현은 완전한 이진 트리 또는 전체 이진 트리에 좋습니다.
또 다른 접근 방식은 연결 목록을 사용하는 것입니다. 각 요소에 대한 노드를 생성합니다. 이것은 아래와 같을 것입니다 -
