Python-Programm zur Implementierung einer binären Baumdatenstruktur
Ein Baum ist eine Datenstruktur, die aus Knoten besteht. Die Knoten werden durch die Kanten verbunden. Der oberste Knoten wird als Wurzel bezeichnet und die untersten Knoten werden als Blätter bezeichnet. Blätter sind die Knoten, die keine untergeordneten Knoten haben.
Binärer Baum
Ein Binärbaum ist ein Baum, in dem jeder Knoten maximal zwei untergeordnete Knoten haben kann. Das heißt, jeder Knoten kann entweder 0 oder 1 oder 2 Kinder haben, aber nicht mehr. Jeder Knoten in einem Binärbaum besteht aus drei Feldern −
Daten
Zeiger auf das linke untergeordnete Element
Zeiger auf das richtige Kind
Vollständiger Binärbaum – Ein Binärbaum gilt als vollständiger Binärbaum, wenn alle Ebenen bis auf die letzte Ebene vollständig gefüllt sind und alle Knoten so weit wie möglich übrig bleiben sollten.
Strict/Proper Binary Tree – Ein Binärbaum wird als strikter oder echter Binärbaum bezeichnet, wenn jeder Knoten entweder null oder zwei Kinder hat.
Perfekter Binärbaum – Ein Binärbaum wird als perfekter Binärbaum bezeichnet, wenn alle Knoten zwei untergeordnete Knoten haben und alle Blattknoten auf derselben Ebene liegen.
Balanced Binary Tree – Ein Binärbaum gilt als ausgeglichen, wenn der Unterschied zwischen der Höhe des linken Unterbaums und der Höhe des rechten Unterbaums höchstens eins (0 oder 1) beträgt.
Konstruieren eines Binärbaums aus dem angegebenen Array
Beispiel
Wenn der Wurzelknoten am i-ten Index vorhanden ist, befindet sich das linke Kind am (2*i+1)-ten Index und das rechte Kind am (2*i-1)-ten Index. Wir werden dieses Konzept zum Aufbau des Binärbaums aus den Array-Elementen verwenden.
class TreeNode:
def __init__(self,data,left=None,right=None):
self.data=data
self.left=left
self.right=right
def insert_into_tree(root,arr,i,l):
if i<l:
print(arr[i])
temp=TreeNode(arr[i])
root=temp
root.left=insert_into_tree(root,arr,i*2+1,l)
root.right=insert_into_tree(root,arr,i*2+2,l)
return root
arr=[1,2,3,4,5]
i=0
l=len(arr)
root=TreeNode(arr[0])
insert_into_tree(root,arr,i,l)
Ausgabe
1
2
4
5
3