二叉树是由一个根节点和根节点的左右指针指向的节点们构成的。
我们在做栈结构，队列结构，单向链表结构的节点删除时，都是通过改变指针的指向来删除节点的，二叉树结构，也可以根据改变指针的指向来删除一个节点，只不过就是比前面的几个结构复杂了一些。
首先二叉树是遵循左小右大的原则的 如果 1 图
1
如果根节点值为9的二叉树 左边的任何一个值都小于9 右边的任何一个值都大于9
我们在已4为父节点的角度去观察 4左边的任何一个值 都小于4 4右边的任何一个值都大于4
如果我们要删除 值为4的这个节点 我们需要把值为9的左指针改变指向 这个时候 指向谁 就成了一个问题了
我们先尝试一下指向值为3的节点这个时候 9指向3 如 2图
2
此时 根节点 指向 值为3的节点 这样不只是把4节点给删除了 7 5 8也跟着被删除了 所以我们把3节点的右指针指向7 7又指向5和8 以为右边的一定比左边的大 所以放在3的右指针上是成立的 如3 图
3
这样就达到了 删除了值为4的节点 并且让二叉树保留原有的逻辑规律；
上述的是父节点指向左子节点 我们再试试指向右子节点 4图
4
把指针指向右边节点 把删除的节点的左边的节点都放到右节点最左边的位置 也就是最小的位置 因为左边的一定比右边的小；、
所以删除节点的父节点的指针指向左右都行 关键是看删除节点的子节点如果变动位置。对根节点也是可行的 比如删除值为9的节点 5图
5
我们把根节点左边的节点 放到 根节点右边节点的最左边即可；
下面开始用js代码来编写一个二叉树删除节点的方法：
二叉树的插入节点和中序遍历都已经在数据结构（5）中写完了 所以这一章就不做示范了
function Node(value){
this.value = value;
this.left = null;
this.right = null;
this.searchNode = function(value){ // t根据节点的值 查找到要删除的节点 并且把删除的节点的父节点找到 如果没有父节点 就是根节点
if(value==this.value){
return this;
}
if(value<this.value){ //value如果小于这个节点的value 就去左边找 前提是 左边有节点
if(this.left!=null){
node = this.left.searchNode(value);//我们用左子节点再去调用这个方法 去查询
if(node!=null){ //查询到之后 顺便也得到 他的父节点
if(!node.parent){ //因为层层循环 防止父节点被重复覆盖 所以要先确认父节点不存在 再赋值
node.parent = this;
}
}
}else{// value小于这个节点 这个节点左边的节点还没有value这个值 就证明此二叉树不存在value这个值
return null;
}
}else{ //valuie大于或等于 this.value就去 左边找
if(this.right!=null){
node = this.right.searchNode(value);
if(node!=null){
if(!node.parent){
node.parent = this;
}
return node;
}else{
return null;
}
}else{
return null;
}
}
}
//如果我们要把根节点的指针指向要删除节点的右子节点 我们就得把左子节点放在右子节点的最左边 所以我们先得找到右子节点的最左边的那个节点
this.mostLeft = function(){
if(left!=null){
this.left.mostLeft();
}else{
return this;
}
}
}
function ForkedTree(){//因为我们存放二叉树的类是基于根节点的而建立的 所以如果我们要删除根节点的话 需要从新编写一个类
this.root=null;//用root来存放节点
this.add=function(value){ //插入节点的方法 前一章节 讲过 不需要多做解释
if(this.root!=null){
this.root.add(value);
}else{
this.root = new Node(value);
}
}
this.iterate=function(arr){ //中序遍历方法
this.root.iterate(arr);
}
this.del=function(value){ //删除节点的方法
if(this.root!=null){//先判断root 是否存在节点 没有就返回 else 返回 null
delNode = this.root.searchNode(value); //将要查询的节点返回出来并找出父节点 没有父节点 就是根节点
if(delNode==null){//如果查询不到 就证明删除的节点 在root里 是不存在的 返回 null
return null;
}
if(delNode.parent){ //判断是不是根节点
if(delNode.right!=null){ //有右子树
rightBottomLeft = delNode.right.mostLeft(); //找右侧最小节点也就是右侧最左边的节点
rightBottomLeft.left = delNode.left;//让右侧最小节点的也就是右侧最做的变得节点的左指针指向 要删除节点的的左指针指向的节点
if(delNode.parent.left==delNode){//判断一下删除的节点的父节点 是右指针指向删除节点的 还是 左指针指向删除节点的
delNode.parent.left = delNode.right; //如果是左 就用左指针指向要删除节点的右指针
}else{//如果不是左 也就是右指针 那就用右指针指向被删除节点的右指针指向的节点
delNode.parent.right = delNode.right;
}
}else{ //无右子树 那就直接指向删除节点 并把指向删除节点的指针指向删除节点左指针的指向
if(delNode.parent.right == delNode){//判断父指针 是哪个指针指向要删除的节点 然后直接指向删除节点的左指针即可
delNode.parent.right = delNode.left;
}
if(delNode.parent.left == delNode){
delNode.parent.left = delNode.left;
}
}
}else{ //是根节点
if(delNode.right!=null){ //先判断 有无 右子树
rightBottomLeft = delNode.right.mostLeft();//找到右指针的最小值
rightBottomLeft.left = delNode.left;//然后右指针的最左边的节点的左指针指向根节点的左指针
this.root = delNode.right;//然后把右指针作为根节点
}else{//如果没有右指针 直接把左指针作为根节点即可
this.root = delNode.left;
}
}
delete delNode;//最后删除要删除的节点
}else{
return null;
}
}
}
网友评论