本文共 1988 字，大约阅读时间需要 6 分钟。

二叉树

树是一种数据结构 比如:目录结构

• 如果n=0，那这是一棵空树;
• 如果n>0,那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。

二叉树的基本概念可以看我前面的博客:

二叉树的链式存储: 将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。

'''TOPIC: 二叉树的概念(节点的建立)author: Bluetime: 2020-08-16QQ: 2458682080'''class BiTreeNode:    def __init__(self, data):        self.data = data        self.lchild = None   # 左孩子        self.rchild = None   # 右孩子a = BiTreeNode("A")b = BiTreeNode("B")c = BiTreeNode("C")d = BiTreeNode("D")e = BiTreeNode("E")f = BiTreeNode("F")g = BiTreeNode("G")e.lchild = ae.rchild = ga.rchild = cc.lchild = bc.rchild = dg.rchild = froot = e

二叉树的遍历:

'''TOPIC: 二叉树的遍历author: Bluetime: 2020-08-16QQ: 2458682080'''from collections import dequeclass BiTreeNode:    def __init__(self, data):        self.data = data        self.lchild = None   # 左孩子        self.rchild = None   # 右孩子a = BiTreeNode("A")b = BiTreeNode("B")c = BiTreeNode("C")d = BiTreeNode("D")e = BiTreeNode("E")f = BiTreeNode("F")g = BiTreeNode("G")e.lchild = ae.rchild = ga.rchild = cc.lchild = bc.rchild = dg.rchild = froot = e# print(root.lchild.rchild.data)# 前序遍历(先递归左子树，再递归右子树)def pre_order(root):    if root:        print(root.data, end=",")        pre_order(root.lchild)        pre_order(root.rchild)pre_order(root)print('\n')# 中序遍历(先递归左子树，再访问自己，再递归右子树)def in_order(root):    if root:        in_order(root.lchild)        print(root.data, end=",")        in_order(root.rchild)in_order(root)print('\n')# 后续遍历(先递归左，后递归有，最后打印自己)def post_order(root):    if root:        post_order(root.lchild)        post_order(root.rchild)        print(root.data, end=",")post_order(root)print('\n')# 层次遍历def level_order(root):    queue = deque()    queue.append(root)    while len(queue) > 0:  # 只要队不空        node = queue.popleft()  # 要进队，先出队一个        print(node.data, end=",")        if node.lchild:   # 出队的这个有没有左孩子，有的话，进队            queue.append(node.lchild)        if node.rchild:   # 出队的这个有没有右孩子，有的话，进队            queue.append(node.rchild)level_order(root)

转载地址：http://pbiwi.baihongyu.com/