배열에 이진 트리 저장

Question

아래에있는 것과 같은 이진 트리가 배열에 저장되어야한다고 가정합니다.

7 
/\ 
    1 10 
    /\ 
    9 11 

그리고 어레이의 노드를 저장하는 식 인덱스 i에서의 모든 노드에 대해 다음 위치 0에 루트 노드를 저장하고, 시작 것으로는, 그 아이가 인덱스 (i*2)+1 and (i*2)+2에 배치된다. 두 자식 중 하나의 인덱스가 array.length - 1보다 큰 경우 해당 노드에는 하위 노드가 없습니다.

그래서 나는 다음 위치 I2 + 1, I2 + 2에서 그 아이 1 (10)가 1, 2 될 것이라고, 위치 0에서 7을 넣어 시작 :

|7|1|10| | | |  
0 1 2 3 4 5 

을 지금, 나는이와 붙어있어 자식 노드가없는 노드 1. 자녀로서 무엇을 집어 넣어야합니까?

인가 그것과 같이, 예 -1를 들어, 노드의 부재를 표현 할 몇 가지 기본 값을 넣어 OK :

이

|7|1|10|-1|-1|9|11| 
0 1 2 3 4 5 6 7 

Answer 1

이 배열의 이진 트리를 저장하기위한이 알고리즘은 나무를 위해 설계되었습니다 루트 노드로부터 시작하는 트리의 모든 브랜치가 동일한 길이를 갖도록 배열 크기가 트리 내의 최대 깊이에 기초한 다음 동일하거나 더 작은 깊이의 모든 트리 위치에 대한 배열 위치를 할당합니다. 여러 다른 브랜치 길이가있는 경우 이것이 올바른 알고리즘이 아닐 수 있습니다. 브랜치의 길이가 거의 같지만 트리의 끝 부분에서 종종 비어있는 경우가 종종 있습니다. 예를 들어 -1 또는 Integer.MIN_VALUE과 같은 'null'값을 배치하면 대개 배치 할 필요가 없다는 것을 알고있는 한 적절한 해결책이 될 수 있습니다 나무에 -1 값.

트리의 최대 깊이 수준의 요소가 누락되어 트리의 왼쪽/오른쪽 순서가 중요하지 않다는 것을 알게되면 대신 간단하게 빈 값이 항상 배열의 끝에있는 위치 집합 인 최하위 위치에 트리를 다시 정렬하여 트리를 complete binary tree으로 만듭니다. 그런 다음 마지막으로 null이 아닌 값의 인덱스보다 큰 트리의 요소 수만 기억하면됩니다. 다이어그램 :

7 
/\ 
    10 1 
    /\ 
9 11 
--> 
|7|10|1|9|11|0|0| 
0 1 2 3 4 5 6 
length = 5 or lastIndex = 4 

Answer 2

이 시점에서 이진 트리 속성을 손상시킬 값을 사용하려고 생각했습니다. 일반 이진 트리에서 왼쪽은 항상 작고 오른쪽은 현재 노드보다 큽니다. 오른쪽에서 왼쪽 또는 아래쪽이 더 높게 나타나는 경우 엔드 노드를 의미합니다.