您的位置: 首页  >  文章  >  二叉查找树（插入、查询、删除）

二叉查找树（插入、查询、删除）

分类: 文章 • 2024-07-31 10:35:46

插入

不改变树原来的结构，小的插到左边，大的插到右边。

二叉查找树（插入、查询、删除）

二叉查找树（插入、查询、删除）
以此类推：
二叉查找树（插入、查询、删除）

查询

和插入一样，小的往左找，大的往右找

二叉查找树（插入、查询、删除）

删除

  • 叶子节点（不存在后继结点）：直接删除
  • 存在后继节点：使用中序遍历的后继结点取代要删除的节点
    • 后继节点存在右子树：将此右子树移到该后继节点的位置。
    • 后继结点不可能存在左子树，若存在则不是后继结点

红色代表要删除的节点；绿色代表后继节点；蓝色代表后继结点的右子树
二叉查找树（插入、查询、删除）
50的后继节点是70，但是70存在右子树。
二叉查找树（插入、查询、删除）

其他例子

删除叶子节点（不存在后继结点）

二叉查找树（插入、查询、删除）
二叉查找树（插入、查询、删除）

存在后继节点

1 后继节点无右子树

二叉查找树（插入、查询、删除）
二叉查找树（插入、查询、删除）
二叉查找树（插入、查询、删除）
二叉查找树（插入、查询、删除）

2 后继结点有右子树

二叉查找树（插入、查询、删除）

二叉查找树（插入、查询、删除）

相关推荐