二叉查找树python二叉查找树源码

二叉查找树（Binary Search Tree，BST），也称为二叉排序树，是一种特殊的二叉树数据结构。它的每个节点都包含一个键（key）、一个关联的值、一个指向左子节点的指针和一个指向右子节点的指针。在二叉查找树中，对于任意节点，其左子树中的所有节点的键都小于该节点的键，而右子树中的所有节点的键都大于该节点的键。这种特性使得二叉查找树非常适合进行查找、插入和删除操作。 在给定的Python代码中，定义了两个类：`Node` 和 `BST`。`Node` 类用于创建二叉树的节点，包含三个属性：`data` 存储节点的键，`lchild` 指向左子节点的引用，`rchild` 指向右子节点的引用。 `BST` 类是二叉查找树的核心，它包含了四个主要方法： 1. **搜索（search）**：这个方法用于查找给定数据在树中的位置。它使用递归的方式，从根节点开始比较数据，如果找到匹配的节点则返回其引用，如果数据小于当前节点的数据则在左子树中继续搜索，反之则在右子树中搜索。如果整个树中都没有找到数据，则返回 `False`。 2. **插入（insert）**：插入操作基于搜索结果进行。首先调用 `search` 方法找到插入位置，如果搜索返回的标志 `flag` 为 `False`，表示没有找到匹配的节点，此时创建一个新的 `Node` 并将其插入到适当的位置。如果数据大于父节点的数据，则插入到父节点的右子树，否则插入到左子树。 3. **删除（delete）**：删除操作相对复杂，需要处理三种情况：待删除节点没有子节点、只有一个子节点或有两个子节点。通过 `search` 方法找到要删除的节点。如果找到了，但节点没有子节点，可以直接删除；如果只有一个子节点，将该子节点提升到被删除节点的位置；如果节点有两个子节点，需要找到其右子树中最小的节点（即左子树的最大节点），将这个节点的值复制到待删除节点，然后删除该最小节点。 4. **先序遍历（preOrderTraverse）**：这是对二叉树进行的一种遍历方式，按照“根-左-右”的顺序访问节点。在给定的代码中，`preOrderTraverse` 方法实现了递归的先序遍历，当节点不为空时，打印节点的值，然后分别对左子节点和右子节点进行先序遍历。 二叉查找树的优点在于它的查找、插入和删除操作的时间复杂度在理想情况下可以达到 O(log n)，但在最坏的情况下（如树退化成链表）这些操作的时间复杂度会退化到 O(n)。为了保持二叉查找树的高效性，通常需要保持树的平衡，例如使用AVL树或红黑树等自平衡二叉查找树。