fork download 
  1. # Example binary search tree. (1.01)
  2.  
  3. class TreeNode:
  4.     def __init__(self, data=None):
  5.         self.data = data
  6.         self.left = None
  7.         self.right = None
  8.  
  9. class Tree:
  10.     def __init__(self):
  11.         self.root = None
  12.  
  13.     def insert(self, data):
  14.         """Insert data into tree maintaining BST order."""
  15.         def _insert(root):
  16.             if not root:
  17.                 root = TreeNode(data)
  18.             elif data < root.data:
  19.                 root.left = _insert(root.left)
  20.             elif data > root.data:
  21.                 root.right = _insert(root.right)
  22.             else:
  23.                 root.data = data
  24.             return root
  25.         self.root = _insert(self.root)
  26.  
  27.     def balance(self):
  28.         """Reorder tree so all paths have near uniform depth"""
  29.         a = list(self.inorder())
  30.         self.root = None
  31.         def insert_mid(lo, hi):
  32.             if lo == hi:
  33.                 return
  34.             mid = lo + (hi - lo) // 2
  35.             self.insert(a[mid])
  36.             insert_mid(lo, mid)
  37.             insert_mid(mid + 1, hi)
  38.         insert_mid(0, len(a))
  39.  
  40.     def inorder(self):
  41.         """Generate data inorder"""
  42.         def _inorder(root):
  43.             if root:
  44.                 yield from _inorder(root.left)
  45.                 yield root.data
  46.                 yield from _inorder(root.right)
  47.         yield from _inorder(self.root)
  48.  
  49.     def levelorder(self):
  50.         """Generate data in level order."""
  51.         # @note Each valid node matches two children on the following level.
  52.         #
  53.         # Input: [10, 30, 20, 40]
  54.         #
  55.         # [10]      =     10
  56.         # ['', 30]  =    / \
  57.         # [20, 40]  =  ''   30
  58.         #           =      / \
  59.         #           =    20   40
  60.         q = [self.root]
  61.         while q.count(None) != len(q):
  62.             nodes = q
  63.             q = []
  64.             r = []
  65.             for node in nodes:
  66.                 if not node:
  67.                     r.append('') # None
  68.                 else:
  69.                     r.append(node.data)
  70.                     q.extend((node.left, node.right))
  71.             yield r
  72.  
  73. # Main.
  74.  
  75. from random import sample
  76.  
  77. def pretty_print_tree(t):
  78.     levels = iter(t.levelorder())
  79.     print('>', next(levels, None))
  80.     for level in levels:
  81.         print(' ', level)
  82.  
  83. def show(a):
  84.     t = Tree()
  85.     for x in a:
  86.         t.insert(x)
  87.     print(a)
  88.     print(list(t.inorder()))
  89.     pretty_print_tree(t)
  90.     t.balance()
  91.     pretty_print_tree(t)
  92.  
  93. # Original problem.
  94. a = [50, 40, 45, 47, 46, 41, 35]
  95. show(a)
  96.  
  97. # Degenerate tree (list).
  98. n = 2**3-1
  99. a = list(reversed(range(n)))
  100. show(a)
  101.  
  102. # Random.
  103. n = 2**3-1
  104. a = sample(range(n), k=n)
  105. show(a)
Success #stdin #stdout 0.11s 14260KB
comments (?)
stdin 
Standard input is empty
stdout 
[50, 40, 45, 47, 46, 41, 35]
[35, 40, 41, 45, 46, 47, 50]
> [50]
  [40, '']
  [35, 45]
  ['', '', 41, 47]
  ['', '', 46, '']
> [45]
  [40, 47]
  [35, 41, 46, 50]
[6, 5, 4, 3, 2, 1, 0]
[0, 1, 2, 3, 4, 5, 6]
> [6]
  [5, '']
  [4, '']
  [3, '']
  [2, '']
  [1, '']
  [0, '']
> [3]
  [1, 5]
  [0, 2, 4, 6]
[2, 1, 3, 6, 0, 5, 4]
[0, 1, 2, 3, 4, 5, 6]
> [2]
  [1, 3]
  [0, '', '', 6]
  ['', '', 5, '']
  [4, '']
> [3]
  [1, 5]
  [0, 2, 4, 6]
https://ideone.com/NarUdi
language:
Python 3 (python  3.12)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!