数据结构--二叉树

黑静美原创...大约 6 分钟

二叉树

根节点
子节点
父节点
叶节点：没有子节点的节点
深度：从根到特定节点的“边”的数量

遍历

前序遍历：先访问跟节点，递归地访问遍历左子树，再同样遍历右子树
中序遍历：先递归地遍历左子树，再访问根节点，最后遍历右子树
后序遍历：先左，再右，后根

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = TreeNode(key)
        else:
            self._insert(self.root, key)

    def _insert(self, root, key):
        if key < root.val:
            if root.left is None:
                root.left = TreeNode(key)
            else:
                self._insert(root.left, key)
        else:
            if root.right is None:
                root.right = TreeNode(key)
            else:
                self._insert(root.right, key)

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, root, key):
        if root is None or root.val == key:
            return root
        if key < root.val:
            return self._search(root.left, key)
        return self._search(root.right, key)

    def inorder(self):
        return self._inorder(self.root, [])

    def _inorder(self, root, result):
        if root:
            self._inorder(root.left, result)
            result.append(root.val)
            self._inorder(root.right, result)
        return result

    def preorder(self):
        return self._preorder(self.root, [])

    def _preorder(self, root, result):
        if root:
            result.append(root.val)
            self._preorder(root.left, result)
            self._preorder(root.right, result)
        return result

    def postorder(self):
        return self._postorder(self.root, [])

    def _postorder(self, root, result):
        if root:
            self._postorder(root.left, result)
            self._postorder(root.right, result)
            result.append(root.val)
        return result

# 示例使用
if __name__ == "__main__":
    tree = BinaryTree()
    elements = [20, 10, 30, 5, 15, 25, 35]
    for elem in elements:
        tree._insert(elem)

    print("Inorder traversal:", tree.inorder())
    print("Preorder traversal:", tree.preorder())
    print("Postorder traversal:", tree.postorder())

    key = 15
    node = tree.search(key)
    if node:
        print(f"Found node with key {key}")
    else:
        print(f"Node with key {key} not found")

题目描述

给定一个二叉树，编写一个函数来判断它是否是一个镜像对称的树。一个二叉树如果它的左子树是右子树的镜像反射，则它是对称的。

示例

对于以下这棵树，它是对称的：

对于以下这棵树，它不是对称的：

任务

定义一个二叉树节点类 Node，包含属性 value（节点的值），left 和 right（指向左右子节点的引用）。
实现一个函数 is_symmetric(root)，其中 root 是二叉树的根节点，该函数返回一个布尔值，表示树是否对称。

你可以用下面的框架开始编写你的代码：

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def is_symmetric(root):
    # 在这里实现你的函数
    pass

# 辅助函数，用于比较两个子树是否对称
def is_mirror(left, right):
    # 在这里实现你的函数
    pass

# 测试代码
if __name__ == "__main__":
    # 构建对称的树
    sym_root = Node(1)
    sym_root.left = Node(2)
    sym_root.right = Node(2)
    sym_root.left.left = Node(3)
    sym_root.left.right = Node(4)
    sym_root.right.left = Node(4)
    sym_root.right.right = Node(3)

    # 构建不对称的树
    asym_root = Node(1)
    asym_root.left = Node(2)
    asym_root.right = Node(2)
    asym_root.left.right = Node(3)
    asym_root.right.right = Node(3)

    print("Symmetric tree:", is_symmetric(sym_root))
    print("Asymmetric tree:", is_symmetric(asym_root))

题目描述

二叉树的垂直遍历：给定一个二叉树，返回其节点值的垂直遍历结果。垂直遍历是指从左到右查看二叉树时，将所有在同一垂直线上的节点值按从上到下的顺序聚集起来。如果两个节点在同一行和列，按节点值大小排序。

示例

考虑以下二叉树：

垂直遍历的输出应该是：

[
  [9],
  [3, 8],
  [20, 7],
  [15],
  [5]
]

任务

定义一个二叉树节点类 Node，包括属性 value，left 和 right。
实现一个函数 vertical_order(root)，它接收二叉树的根节点并返回垂直遍历的列表。

你可以使用这个框架开始：

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def vertical_order(root):
    # 在这里实现你的函数
    pass

# 测试代码
if __name__ == "__main__":
    root = Node(3)
    root.left = Node(9)
    root.right = Node(20)
    root.right.left = Node(8)
    root.right.right = Node(15)
    root.right.right.left = Node(7)
    root.right.right.right = Node(5)

    print(vertical_order(root))

核空间的维数和像空间的维数的关系

对于一个矩阵 $N$ ，核空间的维数 $\dim(\text{Ker}(N))$ 和像空间的维数 $\dim(\text{Im}(N))$ 具有重要的关系。这种关系是由线性代数的基本定理之一：秩-零化度定理（Rank-Nullity Theorem）所描述的。

秩-零化度定理

秩-零化度定理说明，对于一个 $m \times n$ 的矩阵 $N$ ，其像空间的维数（也就是 $\dim(\text{Im}(N))$ $）和核空间的维数$ \dim(\text{Ker}(N)) $之和等于矩阵的列数$ n$。

\color{red}{ \dim(\text{Ker}(N)) + \dim(\text{Im}(N)) = n }

其中： - $\dim(\text{Ker}(N))$ 是矩阵 $N$ 的核空间的维数（零空间的维数）。 - $\dim(\text{Im}(N))$ 是矩阵 $N$ 的像空间的维数。

具体例子

考虑一个具体的幂零矩阵 $N$ ，假设 $N$ 是 $4 \times 4$ 矩阵：

N = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}

计算核空间的维数

计算得出 $\dim(\text{Ker}(N)) = 1$ 。

矩阵 $A$ 的零空间 $\text{Null}(A)$ 是指满足方程 $A\mathbf{x} = \mathbf{0}$ 的所有向量 $\mathbf{x}$ 的集合。换句话说，零空间是 $A$ 的所有特征值为零对应的特征向量构成的向量空间。

如果我们写出矩阵方程 $A\mathbf{x} = \mathbf{0}$ ，然后求解 $\mathbf{x}$ ，得到的解即为零空间的一组基。通常情况下，我们使用高斯消元法或者矩阵的行列式来求解这个方程组。

假设 $A$ 是一个 $m \times n$ 的矩阵。如果 $A$ 的列数大于行数，即 $n > m$ ，则 $A$ 的零空间可能不止一个向量，因为矩阵有自由变量，可以用来表示无穷多个解。

如果 $A$ 为方阵，即 $n = m$ ：

$A$ 是可逆矩阵。
- - $\text{Null}(A)$ 中只包含零向量，因为只有 $\mathbf{x} = \mathbf{0}$ 才能使得 $A\mathbf{x} = \mathbf{0}$ 成立。
$A$ 是幂零矩阵
其像空间的维数可以通过分析其幂的性质得到。
设 $A$ 是一个 $n \times n$ 的幂零矩阵，其最小的幂次为 $k$ ，使得 $A^k = \mathbf{0}$ ，其中 $\mathbf{0}$ 是适当维度的零矩阵。
考虑 $A^{k-1}$ ，它的性质是将 $A$ 的非零元素向右上方移动一步。进一步考虑 $A^{k-2}$ ，它将 $A^{k-1}$ 的非零元素再次向右上方移动一步。以此类推，直到 $A^1$ ，它会将 $A^2$ 的非零元素向右上方移动一步。
观察这个过程，我们可以发现， $A^1$ 的非零元素将会落在 $A^2$ 的主对角线上方一格， $A^2$ 的非零元素将会落在 $A^3$ 的主对角线上方两格，以此类推。最终，在 $A^{k-1}$ 中，所有的非零元素都将会落在 $A^k$ 的右上角之外，因为 $A^k$ 是零矩阵。
因此， $A^{k-1}$ 的非零元素构成的向量将张成像空间。考虑到 $A^{k-1}$ 的非零元素只有 $n - 1$ 个，因为它只会落在主对角线上方的 $n - 1$ 个位置，所以像空间的维数为 $n - 1$ 。
综上所述，幂零矩阵的像空间的维数为 $n - 1$ 。

B= \begin{pmatrix} 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & -2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -2 \\ \end{pmatrix}

昵称

邮箱

网址

按正序
按倒序
按热度

数据结构--二叉树

预览: