Wenn ich einen binären Suchbaum konstruieren, um die folgenden Werte, um das Hinzufügen:Erstellen von Binary Search Trees
10, 7, 16, 12, 5, 11, 2, 20, 1, 14
ich einen Baum der Höhe erhalte 5. Gibt es eine Methode (außer Versuch und Irrtum), was ich kann Verwenden Sie, um eine Reihenfolge der Ganzzahlen zu bestimmen, die einen Baum der Höhe 4 erstellen würde?
ich dies vollständig durch nicht gedacht, sondern eine Möglichkeit, einen Baum von bestimmten Tiefe zu bekommen ist Ihre Elemente zu sortieren, bevor sich das Einfügen: dh Sortierung dann N Elemente in einen binären Suchbaum eingefügt wird, einen Baum produzieren der Tiefe N.
Sie könnte der Lage sein:
K=4 von ihnen einen Baum von Tiefe erzeugen K(natürlich die Entscheidung, welche K Elemente mit zu beginnen und eine Strategie, die übrigen Elemente zum Einfügen ist der schwierige Teil - aber vielleicht wäre dies ein Anfang sein)
bearbeiten : Ich denke, eine allgemeine Lösung ist möglich, vorausgesetzt, K ist groß genug. Wie wäre es damit:
10, 7, 16, 12, 5, 11, 2, 20, 1, 141, 2, 5, 7, 10, 11, 12, 14, 16, 20beispielsweise nach dem Sortieren und das Einsetzen der letzten 4:
12
\
14
\
16
\
20
... dann nach dem Einlegen der letzten 3:
12
/\
7 14
\ \
10 16
\ \
11 20
... dann nach den letzten 2:
12
/\
7 14
/\ \
2 10 16
\ \ \
5 11 20
... und schließlich nach dem Einfügen des letzten Elements:
12
/\
7 14
/\ \
2 10 16
/\ \ \
1 5 11 20
... Sie sind mit einem BST der Höhe K = 4 übrig.
Beachten Sie, dass dieser Ansatz nur funktioniert, wenn K groß genug ist - speziell wenn K(K+1)/2 >= N.
Woher bekommen Sie die 18 im Binärbaum? – Bytemain
@Chibox: Entschuldigung, Tippfehler. Sollte jetzt behoben werden. –
Ich denke nicht, dass Ihre Methode in allen Fällen funktioniert. Sagen wir, wir haben einen Baum mit den Nummern 1-7. Wenn wir Ihre Methode verwenden, fügen wir 5,6,7, dann 3,4, dann 2, dann 1 ein. Das Endergebnis ist ein Baum der Höhe 4 mit 5 als Wurzelknoten. Es ist jedoch möglich, 7 Knoten als einen perfekt ausgeglichenen Binärbaum mit der Höhe 3 anzuordnen, wenn wir 4 als Wurzelknoten verwenden. – hugomg
Ja, Sie können zuerst einen perfekt ausgeglichenen Baum erstellen, und Sie können dann die Knoten so ausgeben, dass die übergeordneten Knoten vor ihren Kindern gedruckt werden.
Um einen perfekt ausgeglichenen Baum zu erstellen, sortieren Sie einfach die Zahlen und verwenden Sie rekursive Binärdivisionen, um einen Baum zu erstellen.
Zum Beispiel in Ihrem Fall würden wir die Zahlen sortieren
1 2 5 7 10 11 12 14 16 20
und dann einen ausgeglichenen Baum von ihnen (nehmen Sie die mittlere Zahl als die Wurzel und diesen Vorgang wiederholen, rekursiv) bauen
11
5 14
1 7 12 16
2 10 20
Wir können jetzt eine Preorder-Traversal oder eine Breast-First-Traversal verwenden, um die Knoten in einer gewünschten Reihenfolge zu drucken (solange wir die Elternknoten vor den Kindern ausgeben, werden wir in Ordnung sein).
11 5 14 1 7 12 16 2 10 20
public void testMakeBinarySearchTree() {
List<Integer> array = new ArrayList<>();
for (int i = 0; i < 10; i++) {
array.add(i+1);
}
Collections.shuffle(array);
Node root = new Node(array.get(5));
for (int value : array) {
binarySearchTreeInsertNode(root, value);
}
}
private void binarySearchTreeInsertNode(Node node, int value) {
int data = node.getData();
if (value > data) {
Node right = node.getRight();
if (right != null) {
binarySearchTreeInsertNode(right, value);
} else {
node.setRight(new Node(value));
}
} else if (value < data) {
Node left = node.getLeft();
if (left != null) {
binarySearchTreeInsertNode(left, value);
} else {
node.setLeft(new Node(value));
}
}
}
möglich Duplikat [Balancing ein Binary Tree (AVL)] (http://stackoverflow.com/questions/133610/balancing-a-binary-tree-avl) – Flexo
Sie müssen die [Balancing Binary Tree] (http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree) –
Ich bin nicht auf der Suche nach einem ausgewogenen Baum als solche, mehr bestimmen eine Reihenfolge der ganzen Zahlen, die eine Höhe von 4 bekommen würde. – Tobi3