python算法复习：实现二叉树深度&&广度优先遍历

terry 2年前 (2023-09-27) 阅读数 66 #数据结构与算法

Python算法回顾：二叉树深度&&宽度第一遍数据类型数据结构用于使用树结构来模拟数据收集。它是由n（n>0）个有界节点组成的层次关系的集合。

树属性

每个节点有零个或多个子节点；
没有头节点的节点称为根节点。
每个非根节点有且只有一个根节点；
除根节点外，每个子节点都可以分为若干个不相交的子树。

术语

节点度：一个节点所包含的子树的数量称为节点度；树度：在一棵树中，最大节点的度称为树度；
叶子节点或终端节点：度数为零的节点；
非终端节点或分支节点：度数不为零的节点；
父节点或母节点：如果节点包含子节点，则该节点称为其子节点的主节点。
子节点或子节点：节点所包含的子树的根节点称为该节点的子节点；
兄弟节点：共享同一父节点的节点称为兄弟节点；
节点级别：从根开始定义，根为第一级，根的子节点为第二级，以此类推；
深度：对于每个节点n，n的深度是从根到n的唯一路径长度，根的深度为0；
高度：对于每个节点n，n的深度是从点n开始，到叶子节点的最长路径长，所有叶子的高度为0；
表兄弟节点：主节点同级的节点互为表兄弟；
节点的祖先：从根到节点的分支所有节点；
后代：以特定节点为根的子树中的任何节点都称为该节点的后代。
森林：M（m>=0）棵稀疏树的集合称为森林；

什么是二叉树？

二叉树：每个节点最多包含两个子树的树称为树。它是一棵二叉树； 完全二叉树：假设二叉树的深度为 d (d>1)。除第d层外，其他层的节点数均已达到最大值，并且第d层中的所有节点从左到右连续且紧凑。这样的二叉树称为完全二叉树；

满二叉树：所有叶子节点都在最低层的完全二叉树；

深度优先

深度优先遍历是指二叉树的深度优先遍历，包括：

前序遍历
遍历顺序 -> Left subtre -> Left subtre。子树

顺序遍历
遍历顺序 --> 左子树 -> 根节点 -> 右子树

后序遍历
遍历顺序 -> 左 -> 右子树节点

首先定义 TreeNode：

class TreeNode:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left  # 左子树
        self.right = right  # 右子树
复制代码

实例化TreeNode：

node1 = TreeNode("A",
                 TreeNode("B",
                          TreeNode("D"),
                          TreeNode("E")
                          ),
                 TreeNode("C",
                          TreeNode("F"),
                          TreeNode("G")
                          )
                 )
复制代码

前序遍历

def preTraverse(root):
    if root is None:
        return
    print(root.value)
    preTraverse(root.left)
    preTraverse(root.right)
复制代码

运行结果：Traver♶

D
B
E
A
F
C
G
复制代码

后序遍历

def afterTraverse(root):
    if root is None:
        return
    afterTraverse(root.left)
    afterTraverse(root.right)
    print(root.value)
复制代码

运行结果：

D
E
B
F
G
C
A
复制代码

宽度优先

宽度优先遍历是分层遍历，逐层遍历层。

def levelOrder(root):
    # write your code here
    res = []
    # 如果根节点为空，则返回空列表
    if root is None:
        return res
    # 模拟一个队列储存节点
    q = []
    # 首先将根节点入队
    q.append(root)
    # 列表为空时，循环终止
    while len(q) != 0:
        length = len(q)
        for i in range(length):
            # 将同层节点依次出队
            r = q.pop(0)
            if r.left is not None:
                # 非空左孩子入队
                q.append(r.left)
            if r.right is not None:
                # 非空右孩子入队
                q.append(r.right)
            res.append(r.value)
            print(r.value)
    return res
复制代码

运行结果：