蓝桥杯备赛（Day5）——二叉树

二叉树存储

普通做法，二叉树一个节点包括结点的数值以及指向左右子节点的指针

在class Node中

def __init__(self,s,l=None,r=None):
    self.val=None
    self.l=l
    self.r=r

在竞赛中，我们往往使用静态数组实现二叉树，定义一个大小为N的静态结构体数组，使用其来存储一棵二叉树。

#定义静态数组
tree=['']*10000
#根节点
tree[1]
#结点tree[p]的左子节点
tree[2*p]
#结点tree[p]的右子节点
tree[2*p+1]

使用静态数组时，对应的tree假如不是满二叉树，则应该使用-1或者0填补空缺，这样tree对应的静态数组即可使用于任何一个二叉树。 

三种遍历方式

先序遍历

EBADCGFIH

def preorder(p):
    print(tree[p],end='')
    if tree[2*p]!='':
        postorder(2*p)
    if tree[2*p+1]!='':
        postorder(2*p+1)

按照父、左儿子、右儿子的顺序进行访问