Findet das erste Null in binären Baum mit begrenztem Speicher

Question

Ich habe einen binären Baum, in dem jeder Knoten einen Wert haben kann.

Ich will den Knoten im Baum finden, die den Wert null hat und am nächsten an der Wurzel. Wenn zwei Knoten mit der gleichen Entfernung von der Wurzel sind, wird entweder tun. Ich brauche die Anzahl der Lesezugriffe auf den binären Baum zu minimieren. Es sei angenommen, dass Arbeitsspeicher beschränkt sich auf nur k Knoten.

DFS Tiefen k ist erschöpfend, sondern den nächsten Knoten nicht finden, wenn ich zum ersten Mal durch den ganzen Baum laufen. BFS findet in der Nähe, aber es könnte scheitern, weil DFS tiefer nulls mit dem gleichen Speicher finden kann.

Ich möchte die geringste Anzahl von Lese haben, um den Baum zugreift und die nächste Null-Knoten finden.

(Ich werde dies schließlich in n-Wege-Bäume implementieren müssen, zu, so dass eine allgemeine Lösung wäre gut. Kein Schreibzugriff auf den Baum, nur lesen).

Answer 1

Sie können unter Iterative-Vertiefung Tiefensuche suchen. Es wird den nächsten Knoten automatisch finden, aber die gleiche Tiefe wie DFS erreichen kann. Es verwendet mehr Lesezugriffe though.

Sie können auch mit BFS beginnen, und wenn Sie nicht über eine Null mit dem erlaubten Speicher finden, führte die DFS.

Answer 2

Ich würde eine DFS mit einem einfachen Baumschnitt implementieren. Also, es ist nicht wahr, dass Sie den ganzen Baum laufen haben.
Wenn Sie zum Beispiel einen Nullwert in der Höhe h gelegen haben, können Sie Überspringen Knoten, die in der gleichen oder tiefere Position.

Answer 3

Wenn Sie nicht die Datenstruktur ändern dann werden Sie jeden Knoten lesen müssen -. Breite beginn

Wenn Sie die Datenstruktur ändern können, dann jeder Knoten die relative Tiefe des ersten Null-Kind-Knoten aufnehmen könnte. (Jede äquivalente Werte der von seinen Kindern arbeiten).

Sie dann wissen, welche Zeile in dem Baum zu jagen, wenn für die frühest null suchen.

Answer 4

Es ist ein einfacher Weg, wenn Sie bereit sind, Ihren Baum in einem Array zu speichern. Anstatt jeder Knoten Zeiger zu seiner linken und rechten Kinder zu haben, die Kinder des Knotens n 2n + 1 und 2n + 2 in der Anordnung. (Und Knoten n der Eltern sind (n-1) / 2, wenn n! = 0).

Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};

einfach durch das Array Iterieren linear entspricht eine BFS, aber mit dem Platzbedarf von O (1).

Dies kann leicht zu n-ary Bäume erweitert werden. beispielsweise in einem ternären Baum, das linke Kind ist 3n + 1, Zentrum 3n + 2, rechts 3n + 3 und Eltern sind (n-1) / 3, wenn n! = 0 ist.