第一节：二叉树用list实现   

from queue import Queue
# 用list列表的方式实现二叉树
def createNode(data, left=None, right=None):
    # 创建当前节点
    return [data, left, right]

def is_null(btree):
    # 判断当前树是否是空的
    return btree is None

def get_Root(btree):
    # 一般节点获取当前自己的值
    return btree[0]

def get_left(btree):
    # 一般节点获取其左孩子
    return btree[1]

def get_right(btree):
    # 一般节点获取其右孩子
    return btree[2]
def set_root(btree, data):
    # 设置当前节点
    btree[0] = data

def set_left(btree, data):
    # 设置当前节点的左孩子
    btree[1] = data

def set_rigth(btree, data):
    # 设置当前节点的右孩子
    btree[2] = data

def cen_bianli(btree):
    # 层序遍历
    que = Queue()  # 获取一个无限长的队列
    que.put(btree)
    while que is not None:
        data = que.get()
        print(data[0])
        if data[1]:    # 有左孩子,将左孩子入队列
            que.put(data[1])
        if data[2]:    # 有右孩子,将右孩子入队列
            que.put(data[2])


if __name__ == '__main__':
    # 创建了第一个节点数值为2, 并且左孩子为4， 右孩子为8
    t1 = createNode(2, createNode(4), createNode(8))
    # 我们紧接着给4创建左孩子, 并且数值为8
    set_left(get_left(t1), createNode(3))  # 获取它的左孩子, 并给左孩子的左孩子赋值
    set_rigth(get_left(get_left(t1)), createNode(6))  # 给根节点的左孩子的左孩子设置右孩子
    set_left(get_left(get_left(t1)), createNode(7))  # 给根节点的左孩子的左孩子设置右孩子
    print(t1)  # 查看创建的树
    print("二叉树层次遍历的结果:")
    cen_bianli(t1)

第二节： 二叉树用面向对象的方式创建以及一些遍历算法

from queue import Queue  # 后面会用到的队列,这是python自带的模块

# 我们不需要导入栈, 因为列表的append和pop就能完全模拟栈的操作

class BinNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

pro = []    # 等会存先序遍历的结果
def pro_bianli(node):
    # 先序遍历递归实现
    if node != None:
        pro.append(node.data)
        pro_bianli(node.left)
        pro_bianli(node.right)

pro_list = []
def no_recur_pro(node):
    # 先序遍历的非递归实现
    if node != None:
        Stack = [node]
        while Stack:
            temp = Stack.pop()
            pro_list.append(temp.data)
            if temp.right != None:
                Stack.append(temp.right)
            if temp.left != None:
                Stack.append(temp.left)

mid = []    # 等会存中序遍历的结果
def mid_bianli(node):
    # 中序遍历的递归实现
    if node != None:
        mid_bianli(node.left)
        mid.append(node.data)
        mid_bianli(node.right)

mid_list = []
def no_recur_mid(node):
    # 中序遍历的非递归实现
    stack = []

    while node or stack:
        while node != None:
            stack.append(node)
            node = node.left
        if stack != None:
            node = stack.pop()
            mid_list.append(node.data)
            node = node.right

end = []    # 等会存后序遍历的结果
def end_bianli(node):
    # 后序遍历递归实现
    if node != None:
        end_bianli(node.left)
        end_bianli(node.right)
        end.append(node.data)

end_list = []
def no_recur_end(node):
    # 后序遍历的非递归实现   # 借鉴先序遍历
    # 后序遍历是逆后序遍历的取反,逆后序遍历跟先序遍历刚好相反   先序遍历是先根，再左，再右。 逆后序是先根，再右，再左
    if node != None:
        Stack = [node]
        while Stack:
            temp = Stack.pop()
            end_list.append(temp.data)
            if temp.left != None:
                Stack.append(temp.left)
            if temp.right != None:
                Stack.append(temp.right)
    # 在后面的输出我们逆转就行了

cen = []
def cen_bianli(node):

    que = Queue()  # 申请一个无限长的队列
    que.put(node)
    while que.empty() == False:   # 队列为空等于False  也就是队列不空
        dat = que.get(block=False)   # 默认的是阻塞式获取，没有就一直等下去
        cen.append(dat.data)
        if dat.left != None:
            que.put(dat.left)
        if dat.right != None:
            que.put(dat.right)

def count_node(node):
    # 统计节点的个数
    if node is None:
        return 0
    else:
        # 自己按照递归的步骤捋一遍
        left_ = count_node(node.left)    # 可千万别把这个理解成左边节点数目
        right_ = count_node(node.right)   # 可千玩别把这个理解成右边节点数据
        return 1 + left_ + right_

def calc_node(node):
    # 计算节点上数据之和
    if node is None:
        return 0
    else:
        return node.data + calc_node(node.left) + calc_node(node.right)

def get_height(node):
    # 求二叉树的高度
    if node == None:
        return 0
    else:
        left_height = get_height(node.left)
        right_height = get_height(node.right)
        return 1 + max(left_height, right_height)

count = 0
def count_leave(node):
    # 统计叶子节点的个数
    global count
    if node:
        if not node.left and not node.right:
            count += 1
        count_leave(node.left)
        count_leave(node.right)


if __name__ == '__main__':

    # 一口气创建了一棵二叉树
    node = BinNode(4,
                   left=BinNode(5, left=BinNode(3, left=None, right=BinNode(8)), right=BinNode(2)),
                   right=BinNode(9, left=BinNode(7), right=BinNode(0)))
    pro_bianli(node)  # 先序遍历的递归实现
    print("先序遍历递归实现的结果:", pro)

    no_recur_pro(node)  # 先序遍历的非递归实现
    print("先序遍历非递归实现结果:", pro_list)

    mid_bianli(node)  # 中序遍历的递归实现
    print("中序遍历递归实现的结果:", mid)

    no_recur_mid(node)   # 中序遍历的非递归实现
    print("中序遍历非递归实现结果:", mid_list)

    end_bianli(node)  # 后序遍历的递归实现
    print("后序遍历递归实现的结果:", end)

    no_recur_end(node)  # 后序遍历的非递归实现
    print("后序遍历非递归实现结果:", end_list[::-1])

    cen_bianli(node)  # 层序遍历
    print("层序遍历的结果:", cen)

    number = count_node(node)
    print("总的节点个数:", number)

    sum = calc_node(node)
    print("树上面所有节点的和为:", sum)

    height = get_height(node)
    print("树的高度为:", height)

    count_leave(node)   # 统计叶子节点的个数
    print("叶子节点的个数:", count)