Сортировка бинарным деревом питон

Binary Tree Sort Algorithm (Python)

A Binary Tree Sort is an algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order. Average Case Time Complexity : O(N log N) adding one element to a Binary Search Tree on average takes O(log N) time (height of a tree). Therefore, adding n elements will take O(N log N) time. Worst Case Time Complexity : O(N^2). The worst case can be improved by using a self-balancing binary search tree, which will take O(N log N) time to sort the array in worst case. Just for practicing, I’ve implemented the Binary Tree Sort algorithm, and if you’d like to review the code and provide any change/improvement recommendations, please do so, and I appreciate that.

Code

""" This module creates a Binary Sort Tree ascendingly using In Order Tree Traverse; Stable Sort; Worst Case Time Complexity (For if the tree would be a chain Tree): O(N^2) Average Case Time Complexity: O(N^Log N) Memory Complexity: Not in place O(N) """ import random from typing import List, TypeVar T = TypeVar('T') # Not sure how to design and handle the exceptions here yet class ExceptionHandling(Exception): pass class Node(object): def __init__(self, node_value: int) -> None: """ Initializes a node with three attributes; `node_value` (Node Value): Must be an integer/float; `right_child` (Right Child): Initializes to `None`; Its value must be larger than the Root Node; `left_child` (Left Child): Initializes to `None`; Its value must be smaller than the Root Node; """ self.node_value = node_value self.right_child = None self.left_child = None class BinarySearchTree(object): def __init__(self) -> None: """ Initializes the Root Node of the Binary Tree to None; """ self.root = None def is_empty(self) -> bool: """ Returns True if the tree doesn't have a node; """ return self.root == None def insert(self, new_node: int) -> None: """ Inserts an integer-value Node in the Tree; """ self.root = self._insert(self.root, new_node) def _insert(self, parent: int, new_node: int) -> int: """ Inserts an integer value in the left or right Node; Returns the parent Node; """ # If tree is empty if parent is None: parent = Node(new_node) # If the new Node value is smaller than its parent Node value elif new_node < parent.node_value: parent.left_child = self._insert(parent.left_child, new_node) # If the new Node value is bigger than its parent Node value else: parent.right_child = self._insert(parent.right_child, new_node) return parent def inorder(self) ->None: """ Calls the _inorder traversing method; """ self._inorder(self.root) def _inorder(self, parent: int) -> None: """ Traverses the tree inorder (Left Node, Root Node, Right Node) """ if parent is None: return self._inorder(parent.left_child) print(f'') self._inorder(parent.right_child) if __name__ == '__main__': tree = BinarySearchTree() for i in range(random.randint(20, 30)): tree.insert(random.uniform(-10, 10)) tree.inorder() 

Sources

Источник

Sort Binary Tree by Levels using Python

Your task is to return the list with elements from tree sorted by levels, which means the root element goes first, then root children (from left to right) are second and third, and so on.

Return empty list if root is None .

Example 1 – following tree:

Should return following list:

Example 2 – following tree:

Should return following list:

Test cases#

Test.assert_equals(tree_by_levels(None), []) Test.assert_equals(tree_by_levels(Node(Node(None, Node(None, None, 4), 2), Node(Node(None, None, 5), Node(None, None, 6), 3), 1)), [1, 2, 3, 4, 5, 6]) 

The solution in Python#

# Our helper function # ..takes in `node` def tree_iterator(node: Node): # create a list to loop through nodes = [node] # loop while nodes: # yield from the list yield from nodes # internal loop for n in nodes[:]: # add to list if exists if n.left: nodes.append(n.left) if n.right: nodes.append(n.right) # remove from teh main list loop nodes.remove(n) # The primary function being called # ..passes in `node` def tree_by_levels(node): # return a list of values from our helper function # otherwise return `[]` if node is empty return [n.value for n in tree_iterator(node)] if node else [] 

def tree_by_levels(node): # create a return list, and a queue to loop p, q = [], [node] # loop while q: # take the first item from the queue v = q.pop(0) # if it is not empty if v is not None: # add it's value to the return list p.append(v.value) # add the left and right nodes to the queue q += [v.left,v.right] # return the final list, otherwise return [] is empty return p if not node is None else [] 

Top Related Articles

1. How to Split a String with Python
2. Converting to PigLatin with Python
3. Multiples of 3 and 5 with Python
4. Solving the “Catching Car Mileage Numbers” Challenge using Python
5. Counting smiley faces with Python
6. How to Convert Numeric Words into Numbers using Python
7. Solve The Triangle of Odd Numbers using Python
8. “Who likes it” code Challenge in Python
9. Python 4 New Features Planned
10. Custom RGB To Hex Conversion with Python

Источник

Русские Блоги

(Python3) Принцип структуры данных и реализация двоичного дерева сортировки

Предисловие

• Иметь основание Python
• Знать концепцию двоичного дерева можно по ссылке https://blog.csdn.net/sf9898/article/details/105007041.

принцип

• Приведенное выше определение взято из Baidu Baike. Выше есть одна точка, нет узла с равным значением ключа. Но в некоторых местах говорится, что он может быть равным, несмотря ни на что, разница в коде — не что иное, как написание большего и меньшего количества строк в операторе if.
• Согласно определению двоичного дерева сортировки, разница между ним и обычным двоичным деревом в основном заключается в части вставки, которую следует оценивать. Маленькие друзья горшка идут влево, большие друзья — вправо (большее, чем текущее значение, идет вправо, меньшее, чем текущее значение, идет влево. ), поэтому вы можете унаследовать метод двоичного дерева, а затем снова написать добавленный метод.

достичь

class Node(object): def __init__(self, item): self.item = item self.left = None self.right = None class SortedTree(object): def __init__(self): self.root = None def travel(self): if self.root is None: return q = [self.root] while q: nd = q.pop(0) print(nd.item, end=' ') if nd.left: q.append(nd.left) if nd.right: q.append(nd.right) print('') def forward(self, root): if root is None: return print(root.item, end=' ') self.forward(root.left) self.forward(root.right) def middle(self, root): if root is None: return self.middle(root.left) print(root.item, end=' ') self.middle(root.right) def back(self, root): if root is None: return self.back(root.left) self.back(root.right) print(root.item, end=' ') 

 def add(self, item): node = Node(item) if self.root is None: # Если текущий корневой узел пуст, то напрямую как корневой узел self.root = node return cur = self.root while cur: if item > cur.item: # Введенное число больше, чем элемент текущего узла, это означает, что он должен быть расположен справа от текущего узла if cur.right: cur = cur.right else: # Эта позиция пуста, поэтому просто повесьте ее прямо cur.right = node break else: # Меньше или равно левой стороне if cur.left: cur = cur.left else: # Положите трубку, если слева ничего нет cur.left = node break 

st = SortedTree() st.add(10) st.add(20) st.add(3) st.add(4) st.add(1100) st.add(1) 

• Выполните различные обходы по нему, и результаты будут следующими
  Обход уровней: 10 3 20 1 4 1100
  Обход предварительного заказа: 10 3 1 4 20 1100
  Обход в середине заказа: 1 3 4 10 20 1100
  Обход почтового заказа: 1 4 3 1100 20 10
• Проверить, заполнить код

class Node(object): def __init__(self, item): self.item = item self.left = None self.right = None class SortedTree(object): def __init__(self): self.root = None def travel(self): if self.root is None: return q = [self.root] while q: nd = q.pop(0) print(nd.item, end=' ') if nd.left: q.append(nd.left) if nd.right: q.append(nd.right) print('') def forward(self, root): if root is None: return print(root.item, end=' ') self.forward(root.left) self.forward(root.right) def middle(self, root): if root is None: return self.middle(root.left) print(root.item, end=' ') self.middle(root.right) def back(self, root): if root is None: return self.back(root.left) self.back(root.right) print(root.item, end=' ') def add(self, item): node = Node(item) if self.root is None: # Если текущий корневой узел пуст, то напрямую как корневой узел self.root = node return cur = self.root while cur: if item > cur.item: # Введенное число больше, чем элемент текущего узла, это означает, что он должен быть расположен справа от текущего узла if cur.right: cur = cur.right else: # Эта позиция пуста, поэтому просто повесьте ее прямо cur.right = node break else: # Меньше или равно левой стороне if cur.left: cur = cur.left else: # Положите трубку, если слева ничего нет cur.left = node break st = SortedTree() st.add(10) st.add(20) st.add(3) st.add(4) st.add(1100) st.add(1) st.travel() st.forward(st.root) print('') st.middle(st.root) print('') st.back(st.root) 

Источник