数据结构与算法：二叉树的增删改查

在上一篇的内容中，我们了解了二叉树的结构以及几种常见的二叉树类型。

本篇我们继续探索二叉树的增删改查

上期回顾

数据结构与算法：二叉树（Binary Tree）

01

遍历二叉树

常见的二叉树遍历方式有三种：前序遍历、中序遍历和后序遍历。

这里的前、中、后是相对于根节点来说的。

前序遍历：指从根节点开始，优先遍历左侧子树，然后遍历右侧子树。

中序遍历：指从左子树开始遍历，然后经过根节点，最后遍历右子树。

后序遍历：指从左子树开始遍历，然后遍历右子树，最后经过根节点。

用一个图片来对比一下：

02

二叉查找树（Binary Search Tree）

从名字上不能看出，这种二叉树就是为了实现快速搜索而设计的，同时支持快速插入、删除。

那么它是如何实现的呢？

以上是两个二叉查找树的例子，从结构上看其实没什么特殊的地方。重点之处在于其对节点中元素大小的排列：

对于任一节点，其左子树中任一节点的值都必须小于当前节点的值，其右子树中任一节点的值都必须大于当前节点的值。

在了解二叉查找树的特点之后，我们用一个例子来体验一下二叉查找树的搜索效率：

假设我们需要找到数字65，判断思路很简单：从根节点开始，当前数字若小于节点中数字则向左寻找，反之若大于节点中数字则向右寻找。

03

插入

看完了查找逻辑我们再来演示一下插入的逻辑，其实和查找类似：

04

删除

删除逻辑则较为复杂，不同于搜索和插入的从上至下，删除则需要从下至上去判断节点之间的大小关系，而且删除也分为以下几种情况：

1、需要删除的目标节点无子节点，直接删除即可

2、需要删除的目标节点只有一个子节点，直接将子节点指向父节点即可

3、需要删除的目标节点有两个子节点，则将右测数值大的节点上移，维持查找二叉树的数字排列规则。

4、需要删除的目标节点有多级子节点，我们需要从目标节点的右侧所有子节点中寻找到最小的，然后将其替换至目标节点位置。

其实不管怎么操作，最终的目的都是要保证操作之后的查找二叉树满足查找二叉树的排列规则对于任一节点，其左子树中任一节点的值都必须小于当前节点的值，其右子树中任一节点的值都必须大于当前节点的值。

到这里关于二叉树的基本内容就结束了，我们通过两篇文章了解了二叉树的结构以及几种不同类型的二叉树、对二叉树的增删改查操作，希望对大家有所帮助。