ArrayList 기반 이진 트리 - Java

Question

현재 ArrayList 기반 binary tree in Java을 구현하는 중입니다. 이 일이 어떻게 될지 알아 내려고 노력하고 있지만 벽에 뛰어 들고 있습니다. 구현하기로되어있는 class에 methods의 무리가 있지만, 시도 할 때마다 작동하지 않는 것 같습니다.

Position<E>으로 식별되는 Position objects이 있습니다. 이 class에서 우리는 private 인 array list 및 root variable 만이 class에 의해 모두 accessible, 그래서 size()method을 가지고 있고, isEmpty() 방법은 간단합니다. 그러나 다음과 같은 메서드를 구현할 때 약간의 문제가 있습니다. hasLeft(Position<E>), hasRight(Position<E>)left(Position<E>), right(Position<E>),addRoot(E e) 등 ... 왼쪽 및 오른쪽 메서드는 left child 및 right child of a node을 반환합니다. ArrayList에 익숙하지만, binary tree class을 구현할 때는 그렇지 않습니다.

어떻게하면 이러한 방법을 구현할 수 있습니까? 나는 붙어있어, 내가 얻을 수있는 도움을 주시면 감사하겠습니다.

감사합니다.

Answer 1

이진 트리를 배열로 쓸 때 일반적으로 힙 (heap)이라고 불리는 것을 만들고 있습니다. 힙은 매우 잘 설명하고이 문서는 당신에게 그들이 구현하는 방법에 대한 세부 사항을 많이 줄 것이다 :

http://en.wikipedia.org/wiki/Binary_heap

Answer 2

당신은 연속 배열의 상단에 이진 트리를 구축 할 수 있습니다. 기본적으로 배열의 i 번째 위치에있는 요소에 대해 0 기반 인덱스가 있습니다.

left(i) : 2 * i + 1 
right(i) : 2 * i + 2