广度遍历

从根节点开始，一层一层从左到右遍历

深度遍历

前序遍历

根-左-右（根在前）

中序遍历

左-根-右（根在中间）

后序遍历

左-右-根（根在最后）

深度遍历——递归的方法

class Tree:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
       
def forward_look_all(tree):
    record = []
    def forward_look(tree):
        if tree.left == None and tree.right == None:
            record.append(tree)
        elif tree == None:
            return
        else:
            record.append(tree.data)
            forward_look(tree.left)
            forward_look(tree.right)
    forward_look(tree)
    return record

def middle_look_all(tree):
    record = []
    def middle_look(tree):
        if tree.left == None and tree.right == None:
            record.append(tree)
        elif tree == None:
            return
        else:
            middle_look(tree.left)
            record.append(tree.data)
            middle_look(tree.right)
    middle_look(tree)
    return record

def back_look_all(tree):
    record = []
    def back_look(tree):
        if tree.left == None and tree.right == None:
            record.append(tree)
        elif tree == None:
            return
        else:
            back_look(tree.left)
            back_look(tree.right)
            record.append(tree.data)
    back_look(tree)
    return record
    
tree_test = Tree(1,Tree(2,4,Tree(5,7,8)),Tree(3,None,6))
print(forward_look_all(tree_test))
print(middle_look_all(tree_test))
print(back_look_all(tree_test)) 

深度遍历——堆栈

示意图

def forward_look_stack(tree):
    record = []
    stack = [tree]
    while stack:
        current = stack.pop()
        if type(current) == Tree:
            record.append(current.data)
            if current.right:
                stack.append(current.right)
            if current.left:
                stack.append(current.left)
        else:
            record.append(current)
    return record

广度遍历——队列

示意图

def general_look(tree):
    # 队列
    queue = [tree]
    record = []
    while queue:
        current = queue.pop(0)
        if type(current) == Tree:
            record.append(current.data)
            if current.left:
                queue.append(current.left)
            if current.right:
                queue.append(current.right)
        else:
            record.append(current)
    return record