数据结构--二叉树

二叉树

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

遍历

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

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")

题目描述

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

示例

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

        1
       / \
      2   2
     / \ / \
    3  4 4  3

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

        1
       / \
      2   2
       \   \
       3    3

任务

1. 定义一个二叉树节点类 Node，包含属性 value（节点的值），left 和 right（指向左右子节点的引用）。
2. 实现一个函数 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))

题目描述

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

示例

考虑以下二叉树：

      3
     / \
    9  20
      /  \
     8   15
        /  \
       7   5

垂直遍历的输出应该是：

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

任务

1. 定义一个二叉树节点类 Node，包括属性 value，left 和 right。
2. 实现一个函数 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))