前言
对于每一种数据结构而言，增删改查操作是基本，二叉树在此之上，也有一些特殊的操作，比如节点删除后的更换，不同节点位置的变更，而且对于不同种类的二叉树，比如前面讲过的二叉搜索树和二叉堆，还有后续要讲的红黑树，在节点插入或删除之后，还有一些自平衡的操作，因为二叉堆的操作前文已经介绍过，红黑树较为复杂，今天这篇文章主要介绍二叉树和二叉搜索树的基本操作。
二叉树的数据处理模板
在实际的算法处理问题当中，有一个固化的解题步骤非常关键，能够帮助我们快速解决实际问题，而不用把精力花费在数据结构本身的探索上。这也就是数据结构的框架，更广泛的定义上，也可以成为算法的框架。
不管是增删改查中的哪一点，遍历都是必不可少的，所以我们优先构建一个二叉树的遍历模板。
二叉树的遍历大体分为两种，递归和迭代，递归的操作简洁明了，便于理解和书写，迭代遍历中的Morris遍历在查询的基础上有优化。为了便于使用，今天通过递归形式构建二叉树的遍历模板。
二叉树构建
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
二叉树处理模板
class TreeExecuteModel{
public void execute (TreeNode treeNode){
// 处理当前节点
if(treeNode == null) {
// todo 定义如何处理
}
// todo 不为空时处理当前节点
// 处理左子树
execute(treeNode.left);
// 处理右子树
execute(treeNode.right);
}
}
- 在二叉树的处理模板中，我们按照处理当前节点，处理左子树，处理右子树的办法来进行。
二叉树的查找
要在二叉树中找到某一个节点，就是遍历这课二叉树，找到即可，套入模板的代码如下
二叉树的查找
public TreeNode executeSearch (TreeNode treeNode, int val){
// 处理当前节点
if(treeNode == null) {
return null;
}
// todo 不为空时处理当前节点
if (treeNode.val == val) {
return treeNode;
}
TreeNode res = null;
// 处理左子树
res = executeSearch(treeNode.left,val);
if (res != null) {
return res;
}
// 处理右子树
res = executeSearch(treeNode.right,val);
return res;
}
二叉搜索树的查找
对于二叉搜索树而言，因为天然存在排序关系，所以在寻找的过程中，可以有一些优化的手段
- 如果目标值比当前节点小，往左找
- 如果目标值比当前节点大，往右找
那么，套入模板，更新一下代码。
public TreeNode executeSearch (TreeNode treeNode, int val){
// 处理当前节点
if(treeNode == null) {
return null;
}
// todo 不为空时处理当前节点
if (treeNode.val == val) {
return treeNode;
}
TreeNode res = null;
if (val < treeNode.val) {
// 如果目标值比当前节点值小,处理左子树
res = executeSearch(treeNode.left,val);
} else {
// 如果目标值比当前节点值大,处理右子树
res = executeSearch(treeNode.right,val);
}
return res;
}
二叉树的更改
二叉树的更改其实也可以分为两类，批量更改和单独更改，两者其实处理上差不多，就是return的时机需要处理一下。这里只展示批量更改。批量更改这个点上，二叉搜索树也没有特殊性。
public void executeUpdate(TreeNode treeNode, int val) {
// 处理当前节点
if (treeNode == null) {
return;
}
// 处理当前节点
treeNode.val = treeNode.val + val;
// 处理左子树
executeUpdate(treeNode.left, val);
// 处理右子树
executeUpdate(treeNode.right, val);
}
二叉树的增加
二叉树节点的增加，简单说就是遍历这棵树，找到一个为null的节点，替换就好。
需要注意的是，这里的插入是随便插入还是要往左子树加？还是往右子树加？这里可以根据实际情况再做调整
二叉树的增加节点
public void executeInsert (TreeNode treeNode, int val){
// 处理当前节点
if(treeNode == null) {
treeNode = new TreeNode(val);
return;
}
// 处理当前节点 增加节点不需要对当前节点进行控制
// treeNode.val = treeNode.val + val;
// 我们默认本次情况就往左子树找空余位置
executeInsert(treeNode.left, val);
// 处理右子树，右子树不处理
// executeInsert(treeNode.right,val);
}
二叉搜索树的插入
二叉搜索树的插入要注意插入后的稳定性，还是要保持原来这棵树在插入后仍然是一颗二叉搜索树，所以在插入的时候进行判断即可。
public void executeInsert(TreeNode treeNode, int val) {
// 处理当前节点
if (treeNode == null) {
treeNode = new TreeNode(val);
return;
}
if (treeNode.val == val) {
// 如果二叉搜索树已经有目标值,不需要插入,直接返回.
return;
}
// 我们默认本次情况就往左子树找空余位置
if (val < treeNode.val) {
// 处理左子树
executeInsert(treeNode.left, val);
} else {
// 处理右子树
executeInsert(treeNode.left, val);
}
}
二叉树的删除
二叉树的删除较为复杂一点，因为涉及到节点指针的转移
二叉树的删除
普通二叉树的节点删除，分为三种情况
1 如果是叶子节点直接删除即可
2 如果只有一个子节点，直接替换为子节点即可
3 如果两个节点都有值，我们默认用左节点替换当前节点。
public TreeNode executeDelete(TreeNode treeNode, int val) {
// 处理当前节点
if (treeNode == null) {
return null;
}
// 处理当前节点
if (treeNode.val == val) {
// 当前节点就是要被删除的节点,根据三种不同情况处理
// 1 左右节点都为null;
if (treeNode.left == null && treeNode.right == null) {
// 直接删除
return null;
}
// 2 只有一个子节点情况
if (treeNode.right == null) {
return treeNode.left;
}
if (treeNode.left == null) {
return treeNode.right;
}
// 3 两个子节点都存在的情况,我们默认用左子节点进行替换
int leftVal = treeNode.left.val;
treeNode.val = leftVal;
treeNode.left = executeDelete(treeNode.left, leftVal);
}
// 处理左子树
treeNode.left = executeDelete(treeNode.left, val);
// 处理右子树
treeNode.right = executeDelete(treeNode.right, val);
return treeNode;
}
二叉搜索树的删除
二叉树的节点删除，也分为三种情况
1 如果是叶子节点直接删除即可
2 如果只有一个子节点，直接替换为子节点即可
3 如果两个节点都有值，我们可以找到左子树中的最大节点，将其替换。
public TreeNode executeDelete(TreeNode treeNode, int val) {
// 处理当前节点
if (treeNode == null) {
return null;
}
// 处理当前节点
if (treeNode.val == val) {
// 当前节点就是要被删除的节点,根据三种不同情况处理
// 1 左右节点都为null;
if (treeNode.left == null && treeNode.right == null) {
// 直接删除
return null;
}
// 2 只有一个子节点情况
if (treeNode.right == null) {
return treeNode.left;
}
if (treeNode.left == null) {
return treeNode.right;
}
// 3 两个子节点都存在的情况,我们用左子树的最大节点进行替换
int leftVal = findMaxNode(treeNode.left).val;
treeNode.val = leftVal;
treeNode.left = executeDelete(treeNode.left, leftVal);
} if (val < treeNode.val) {
// 处理左子树
treeNode.left = executeDelete(treeNode.left, val);
} else {
// 处理右子树
treeNode.right = executeDelete(treeNode.right, val);
}
return treeNode;
}
TreeNode findMaxNode(TreeNode treeNode){
TreeNode res = treeNode;
while (treeNode.right!=null) {
res = treeNode.right;
}
return res;
}
以上，就完成了二叉树及二叉搜索树的增删改查基本操作，并且对于二叉搜索树而言，这四种操作都会保持二叉搜索树的平衡。
总结
首先，通过整理一个二叉树的处理框架，奠定了我们的一个核心思想，把当前节点处理完，然后丢给框架去处理左右节点（递归的过程）。此后的增删改查，都是在此基础上的微调，为业务处理带来了非常大的便利性。
网友评论