二叉树(binary tree)

定义

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

• 二叉树是一种特殊的树数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。

  下面是二叉树数据结构的一种通用定义

  class Tree:
  
      def __init__(self, value=None, left=None, right=None):
          self.value = value
          self.left = left  # 左子树
          self.right = right  # 右子树
  

  在这个定义中，TreeNode 表示二叉树的一个节点。每个节点有三个属性：

  • val: 存储节点的值。
  • left: 指向左子节点的指针。
  • right: 指向右子节点的指针。

  当 left 和 right 都为 None 时，这个节点被称为叶子节点。.png>)

二叉树基本操作

数遍历说明

• 1. 前序遍历： DBACEGF（根节点排最先，然后同级先左后右）
• 2. 中序遍历： ABCDEFG (先左后根最后右）
• 3. 后序遍历： ACBFGED （先左后右最后根）

生成树结构

class Tree:

    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left  # 左子树
        self.right = right  # 右子树


# 生成树
T = Tree("D", Tree("B", Tree("A"), Tree("C")), Tree("E", right=Tree("G", Tree("F"))))
"""
            D
            /\
           B  E
           /\  \
          A  C  G
                /
               F
"""

前序遍历

def pre_traverse(tree):
    """
    前序遍历 根 左 右（根节点排最先，然后同级先左后右）
    :param tree: 二叉树
    :return:
    """
    if tree is None:
        return
    print(tree.value)
    pre_traverse(tree.left)
    pre_traverse(tree.right)


print("前序遍历")
pre_traverse(T)

前序遍历步骤推演

前序排列原理：
#####此时执行preTraverse(root.left) 函数
'''
1、第一步 root=Node(D) print D，D入栈[D]
2、第二步 root=Node(D).left=Node(B) print B, B入栈[D,B]
3、第三步 root=Node(B).left=Node(A) print A, A入栈[D,B,A]
4、第四步 root=Node(A).left=None,没有进入递归，顺序执行preTraverse(root.right)
5、第五步 Node(A).right==None，也没有进入递归，此时preTraverse(A) 函数才会正真返回，A出栈[D,B]
6、第六步 A的上级调用函数为：preTraverse(B.left),所以接着会顺序执行preTraverse(B.right),B的左右节点访问后B出栈[D]
7、第七步 Node(B).right==Node(C) print C,C入栈[D,C]
8、第八步 Node(C).left==None, Node(C).right==None,访问完C的左右节点后函数返回C出栈，返回上级调用[D]
9、第九步 此时返回上级调用执行preTraverse(D.right)=Node(E) print E,D出栈，E入栈[E] 
'''

'''此时输出结果：DBACE'''

中序遍历

def mid_traverse(tree):
    """
    中序遍历 左根右（先左 后根 最后右）
    :param tree:
    :return:
    """
    if tree is None:
        return
    mid_traverse(tree.left)
    print(tree.value)
    mid_traverse(tree.right)


print("中序遍历")
mid_traverse(T)

后序遍历

def after_traverse(tree):
    """
    后序遍历 左右根（先左 后右 最后根）
    :param tree:
    :return:
    """
    if tree is None:
        return
    after_traverse(tree.left)
    after_traverse(tree.right)
    print(tree.value)


print("后序遍历")
after_traverse(T)

分层打印二叉树

def layered_print(tree):
    """
    分层打印二叉树
    :param tree:
    :return:
    """
    if not tree:
        return
    cur_layer = [tree]
    while cur_layer:
        layer_value = []
        next_layer = []
        for t in cur_layer:
            layer_value.append(t.value)
            if t.left:
                next_layer.append(t.left)
            if t.right:
                next_layer.append(t.right)
        print(layer_value)
        cur_layer = next_layer


print("分层打印")
layered_print(T)