二叉树

二叉搜索树(Binary Search Tree, BST)是具有以下特性的二叉树： 左子树中的所有节点键值小于父节点的键值 右子树中的所有节点键值大于父节点的键值 左右子树本身也必须是二叉搜索树 这些特性使得二叉搜索树成为一种高效的数据结构，特别适合用于搜索、插入和删除操作。 二叉搜索树的操作复杂度 二叉搜索树各种操作的时间复杂度如下： 操作 平均情况 最坏情况 插入 O(log n) O(n) 查找 O(log n) O(n) 删除 O(log n) O(n) 最小值 O(log n) O(n) 最大值 O(log n) O(n) 前驱 O(log n) O(n) 后继 O(log n) O(n) 值得注意的是，平均情况指的是在平衡树上执行操作所需的时间，而最坏情况则是在非平衡树上执行操作所需的时间。当树不平衡时（例如所有节点都在一侧），BST的性能会大幅下降。 Python实现二叉搜索树 让我们用Python来实现一个二叉搜索树。首先，我们需要定义两个基本类：BinarySearchTree和Node。 基本结构 首先，我们定义一个空的BinarySearchTree类： class BinarySearchTree: def __init__(self): self.root = None self.size = 0 def length(self): return self.size def __len__(self): return self.size 接下来，我们定义一个Node类，并实现一些辅助方法： class Node: def __init__(self, key, val, left=None, right=None, parent=None): self.key = key self.payload = val self.leftChild = left self.rightChild = right self.parent = parent def has_left_child(self): return self.leftChild def has_right_child(self): return self.rightChild def is_left_child(self): return self.parent and self.parent.leftChild == self def is_right_child(self): return self.parent and self.parent.rightChild == self def is_root(self): return not self.parent def is_leaf(self): return not (self.rightChild or self.leftChild) def has_any_children(self): return self.rightChild or self.leftChild def has_both_children(self): return self.rightChild and self.leftChild 插入操作 有了基本结构后，我们可以实现插入操作。插入方法put()会检查树是否已有根节点。如果没有，它会创建一个新节点并将其设为根节点；如果已有根节点，则调用私有的递归辅助函数_put()来按照二叉搜索树的属性搜索树并插入新节点： ...

Binary trees are fundamental data structures in computer science that appear frequently in coding interviews and real-world applications. This guide offers a straightforward explanation of binary trees, their implementation in Python, and common problem-solving patterns. What is a Binary Tree? A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. Key characteristics include: Every node contains a value and references to its children (if any) There is exactly one root node (the topmost node) Nodes with no children are called leaf nodes The structure naturally represents hierarchical relationships Binary trees enable efficient searching, insertion, and deletion operations Python Implementation and Basic Operations Node Structure class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val # Node value self.left = left # Left child reference self.right = right # Right child reference Creating a Binary Tree def create_binary_tree(): # Create a simple binary tree root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) return root Basic Operations (for Binary Search Trees) def insert(root, val): """Insert a value into a binary search tree""" if not root: return TreeNode(val) if val < root.val: root.left = insert(root.left, val) else: root.right = insert(root.right, val) return root def search(root, val): """Search for a value in a binary search tree""" if not root or root.val == val: return root if val < root.val: return search(root.left, val) else: return search(root.right, val) Binary Tree Traversals There are four primary ways to traverse a binary tree, each visiting nodes in a different order: ...