Advertisement
uopspop

Untitled

Jan 24th, 2022
1,155
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. class BT_Array_BFS:
  3.     def __init__(self, tree):
  4.         self.tree = tree
  5.  
  6.     def traverse_levelorder_bfs(self):
  7.         if len(self.tree) == 0:
  8.             return
  9.         q = []
  10.  
  11.         # initialization
  12.         i_root = 0
  13.         q.append(i_root)
  14.  
  15.         while(True):
  16.             if len(q) == 0 :
  17.                 break
  18.  
  19.             i = q.pop(0)
  20.             if i>=len(tree) :
  21.                 continue
  22.             if tree[i] == None :
  23.                 continue
  24.  
  25.             print(tree[i], end=" ")
  26.  
  27.             # get left right index
  28.             i_plus_one = i + 1
  29.             i_left_plus_one = i_plus_one * 2
  30.             i_right_plus_one = i_plus_one * 2 + 1
  31.  
  32.             i_left = i_left_plus_one - 1
  33.             i_right = i_right_plus_one - 1
  34.  
  35.             q.append(i_left)
  36.             q.append(i_right)
  37.  
  38.  
  39. if __name__=='__main__':
  40.  
  41.     # build binary tree
  42.     tree = [
  43.             5,
  44.             2, 6,
  45.             1, 4, None, 7,
  46.             None, None, 3, None, None, None, None, None
  47.     ]
  48.     bt_array_bfs = BT_Array_BFS(tree)
  49.     print()
  50.  
  51.     # traverse (BFS)
  52.     print("level-order: ")
  53.     bt_array_bfs.traverse_levelorder_bfs()
  54.     print()
  55.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement