Binärer Baum Monoton?

Wie kann man überprüfen ob ein binärer Baum monoton ist, also alle Zweige die selbe längen haben? Entweder einfach die Logik wäre schön oder in c.

Vielen Dank im Voraus

Answer 1

[Erzesel]

ein klein wenige Mathe...

Ausgewogener Binärbaum:

...kann nur

• 1,3,7,15,31,63,...usw. Knoten (2 hoch n -1) oder
• 2,4,8,16,32,64,...usw Enden(Leafs/Blätter) (2 hoch n) haben.

also müssen wir nur prüfen ob die Anzahl unsere Blätter/Knoten Teil der jeweiligen Mathematischen Reihe ist .

(ich verwende Powershell als Sprache für die Demos, da dies auf jedem Windowssytem verfügbar ist)

Man könnte erstmal Wert für Wert Einzel abklappern und schauen ob einer passt...:

#Anzahl der "Enden" unseres  ausgewogenen Binärbaums
$Leafs=13

$n=0
$isFullTree = $False 
while ($FullLeafs -lt $Leafs) {
    $FullLeafs = [Math]::pow(2,$n)
    "$Leafs vs $FullLeafs" #mal  Anzeigen
    if ($Leafs -eq $FullLeafs) {
        $isFullTree = $True 
    }
    $n++
}
if ($isFullTree) {
    Write-Host "alle Zweige  des Baums  haben  die gleiche Laenge"  -Foreground  green
}
else {
    Write-Host "nicht alle Zweige  des Baums  haben  die gleiche Laenge"  -Foreground  red
}

...das ist nicht sehr Effizient🙄

zum Glück haben "wir" in der Schule in Mathe aufgepasst und so wissen wir, das das Gegenstück zu x hoch n , nte Wurzel aus x ist bzw.(x hoch 1/n). ...und wenn wir wissen Wollen wie oft die Basis mit sich selbst mulipliziert werden muss um in eine Zahl zu passen. das Reziproke aus log (basis)/log(Zahl)...

die Höhe unserers Baums ist also :

1/(log(2)/log(Anzahl der Blätter)) +1

Wenn der Baum vollständig ist, ist das Ergebnis ein Ganzzahl, also müssen wir nur einmal Prüfen...

 #Anzahl der "Enden" unseres  ausgewogenen Binärbaums
$Leafs=11
 # ich vekneife mir eine  Mathestunde, bei  der Formel  sollte es   ab  der 8. Klasse  klick  machen... (ok,  ich  war 1976 in der 8. Klasse und  ich  kennenicht   die  heutigen Lehrpläne)
 #berechne die Anzahl  der Level (Höhe unseres Baumes 
$TreeHeight= 1/([math]::log(2)/[math]::log($Leafs)) +1
  #unser Logarithmus ist  "zu genau" für die Aufgabe, darum auf 10Stellen hinter dem Komma runden
$TreeHeight = [math]::round($TreeHeight,10)
 #ist  das  Ergebnis  eine ganze Zahl?
if ($TreeHeight % 1 -eq 0) {
    Write-Host "alle Zweige  des Baums  haben  die gleiche Laenge"  -Foreground  green
}
else {
    Write-Host "nicht alle Zweige  des Baums  haben  die gleiche Laenge"  -Foreground  red
}

und etwas verändert, wenn wir wissen wieviel Knoten unser Baum im ganzen hat.

  #Anzahl aller Knoten unseres  ausgewogenen Binärbaums
$AllNodes=7
$TreeHeight= 1/([math]::log(2)/[math]::log( $AllNodes+1 )) +1
$TreeHeight = [math]::round($TreeHeight,10)
if ($TreeHeight % 1 -eq 0) {
    Write-Host "alle Zweige  des Baums  haben  die gleiche Laenge"  -Foreground  green
}
else {
    Write-Host "nicht alle Zweige  des Baums  haben  die gleiche Laenge"  -Foreground  red
}

Wenn du einen (unbekannten) Searchtree abarbeitest musst #Du eben mitzählen wieviel Knoten du passiert hast, bzw, wieviel bei wievielen "Blättern" dein Algorithmus ankam. ...

Woher ich das weiß: eigene Erfahrung – Ich mach das seit 30 Jahren