Ich habe hier an den Übungen gearbeitet:
" Ссылка "
Ich habe eine Funktion geschrieben, die entscheidet, ob ein Baum ein BST (return 1) oder nicht (return 0) ist, aber ich bin mir nicht sicher, ob mein Code total gut ist, ich habe ihn für einen BST und einen Nicht-BST-Baum getestet richtig funktionieren. Ich möchte die Meinung der Community erfahren:
Aktualisierter Code :
Betrachte den Baum (keine BST):
%Vor%meine Idee ist, 2 mit 5 zu vergleichen, wenn es gut ist, dann 1 mit 5, und wenn es gut ist, dann 6 mit 5, wenn es gut ist, 1 mit 2, wenn es gut ist, dann 6 mit 2, wenn es gut ist, dann 5 mit 7; Wenn es gut ist, gibt isBST () 1 zurück. Dieser Code soll es rekursiv tun.
die Knotenstruktur:
%Vor%der Code:
%Vor% Dein Code funktioniert nicht wirklich - nicht einmal für das Beispiel, das du gezeigt hast. Man vergleicht niemals 5 bis 6. Man vergleicht im Grunde die Wurzel eines Unterbaums mit root->left , root->left->left , root->left->left->left usw. Dann vergleicht man root mit root->right , root->right->right , etc ., aber Sie vergleichen nie root mit den anderen Knoten im Teilbaum. Das Problem ist, dass Sie die Wurzel eines Baums nicht mit jedem Element auf seiner rechten und linken Unterstruktur vergleichen, und Sie sollten.
Dies ist eine bekannte Interviewfrage. Die einfachere Lösung besteht darin, die für einen Unterbaum zulässigen Mindest- und Höchstwerte als Parameter zu übergeben.
So funktioniert es mit dem Beispielbaum, den Sie gezeigt haben: Sie sehen 5, daher ist der Maximalwert für jeden Knoten in 5 im linken Teilbaum 5. Ebenso ist der Mindestwert für einen Knoten in 5 im rechten Teilbaum 5. Diese Eigenschaft wird rekursiv angewendet, um zu überprüfen, ob der Wert jedes Knotens den Anforderungen entspricht. Hier ist eine funktionierende Implementierung (geht von einem Baum ohne Duplikate aus):
%Vor%Tags und Links c recursion binary-tree