# 二元搜尋數的array建立法

## 基本概念：
父節點 = floor(index / 2)
左子節點 = index * 2
右子節點 = index * 2 + 1

## 第一種方法

 Python3 implementation of tree using array
# numbering starting from 0 to n-1.
tree = [None] * 10
 
 
def root(key):
    if tree[0] != None:
        print("Tree already had root")
    else:
        tree[0] = key
 
 
def set_left(key, parent):
    if tree[parent] == None:
        print("Can't set child at", (parent * 2) + 1, ", no parent found")
    else:
        tree[(parent * 2) + 1] = key
 
 
def set_right(key, parent):
    if tree[parent] == None:
        print("Can't set child at", (parent * 2) + 2, ", no parent found")
    else:
        tree[(parent * 2) + 2] = key
 
 
def print_tree():
    for i in range(10):
        if tree[i] != None:
            print(tree[i], end="")
        else:
            print("-", end="")
    print()
 
 
# Driver Code
root('A')
set_right('C', 0)
set_left('D', 1)
set_right('E', 1)
set_right('F', 2)
print_tree()

## 第二種方法：

btree=[None]*1024
btree[1]='A'
btree[2]='B'
btree[3]='C'
btree[4]='D'
btree[5]='E'
btree[7]='F'
def preorder(p):
  if btree[p]:
    print(btree[p], ' ', end='');
    preorder(2*p);
    preorder(2*p+1);
def inorder(p):
  if btree[p]:
    inorder(2*p);
    print(btree[p], ' ', end='');
    inorder(2*p+1);
def postorder(p):
  if btree[p]:
    postorder(2*p);
    postorder(2*p+1);
    print(btree[p], ' ', end='');
preorder(1)
print()
inorder(1)
print()
postorder(1)
print()