Бинарные деревья в Python

Деревья — это нелинейные структуры данных, которые представляют узлы, соединенные ребрами. Каждое дерево состоит из корневого узла в качестве родительского узла и левого и правого узлов в качестве дочерних узлов.

Двоичное дерево

Дерево, элементы которого имеют большинство двух дочерних элементов называется двоичным деревом. У каждого элемента в двоичном дереве может быть только два дочерних элемента. Левый дочерний элемент узла должен иметь значение меньше, чем значение его родительского элемента, а правый дочерний элемент узла должен иметь значение больше, чем его родительское значение.

xml version = «1.0» encoding = «UTF -8 «standalone =» no «?> % 0 node_1 27 node_2 14 node_2 -> node_1-> node_2 node_3 35 node_3 -> node_1-> node_3 node_ 1593094743478 10 node_1593094743478 -> node_2-> node_1593094743478 node_1593094742584 9 node_1593094742584 -> node_2-> node_1593094742584 node_1593094803425 31 node_1593094803425 -> node_3-> node_1593094803425 node_1593094773584 42 node_1593094773584 -> node_3-> node_1593094773584

Реализация

Здесь мы создали класс node и присвоили значение узлу.

  • python
  • python
  • python
 # node classclass Node: def __init __ (self, data): # левый дочерний элемент self.left = None # правый дочерний элемент self.right = None # значение узла self.data  = data # print function def PrintTree (self): print (self.data) root = Node (27) root.PrintTree () 

Приведенный выше код создаст узел 27 в качестве родительского узла.

Вставка

Метод insert сравнивает значение узла с родительским n ode и решает, добавить ли его как левый или правый узел.

Помните: если узел больше родительского узла, он вставляется как правый узел; в противном случае он вставляется слева.

Наконец, для печати дерева используется метод PrintTree .

  • Python
  • Python
  • Python
 class Node: def __init __ (self, data): self.left = None self.right = None self.data = data def insert (self, data): # Сравните новое значение с родительским узлом, если  self.data: if data  self.data: if self.right is None:  self.right = Node (data) else: self.right.insert (data) else: self.data = data # Распечатать дерево def PrintTree (self): if self.left: self.left.PrintTree () print (self  .data), если self.right: self.right.PrintTree () # Используйте метод вставки, чтобы добавить  noderoot = Узел (27) root.insert (14) root.insert (35) root.insert (31) root.insert (10) root.insert (19) root.PrintTree () 

Приведенный выше код создаст корневой узел как 27, левый дочерний элемент как 14 и правый дочерний элемент как 35.

Поиск

При поиске значения в дереве нам нужно пройти узел слева направо и с родительским.

  • Python
  • Python
  • Python
 class Node: def __init __ (self, data): self.left = None self.right = None self.data = data # Insert метод для создания узлов def insert (  self, data): if self.data: if data  self.data: if  self.right is None: self.right = Node (data) else: self.right.insert (data) else: self.data = data # findval метод для сравнения значения с узлами def findval (self, lkpval): if lkpval   self.data: if self.right is None: return str (lkpval)  ) + «не найдено» return self.right.findval (  lkpval) else: return str (self.data) + "is found" # Распечатать дерево def PrintTree (self): if self.left: self.left.PrintTree () print (self.data), if self.right:  self.right.PrintTree () root = Node (27) root.insert (14) root.insert (35) root.insert (31) root.insert (10) root.insert (19) print (root.findval (7  )) print (root.findval (14)) 

Здесь создается дерево из 10 19 14 27 31 35 узлов. В этом дереве 7 узлов нет, поэтому на выходе получается 7 не найденных. 14 — левый дочерний корень.
Оцените статью
nanomode.ru
Добавить комментарий