数据结构(6)二叉树-2 删除节点

二叉树是由一个根节点和根节点的左右指针指向的节点们构成的。

大家在做栈结构,队列结构,单向链表结构的节点删除时,都是通过改变指针的指向来删除节点的,二叉树结构,也可以根据改变指针的指向来删除一个节点,只不过就是比前面的几个结构复杂了一些。

首先二叉树是遵循左小右大的原则的 如果 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;

????????????????????????????}

????????????}

}

推荐阅读更多精彩内容