JS递归及二叉搜索树的移除节点

时间: 2019-07-12阅读: 585标签: 递归

1递归含义:在某时某刻某个条件下调用包含自己的函数


2:注意点:⑴递归过程中一定要加限制条件,要不然会陷入死循环:

死循环eg:

function f(someP){
   f(somP);  
}
f(4); //Uncaught RangeError: Maximum call stack size exceeded

正常调用: 

//计算输入某个正整数,然后一直向下叠加 ,这里仅仅做一个简单示例,不进行输入num的判断
function f(num){
    let x;
    if(num>0){
        x =num + f(num-1); 
        return x;
    }
    return false;
}
    
f(5);

递归有个过程,不是一步到位的,这一点尤其重要,因为在学习js数据结构与算法中的二叉搜索树的移除代码会至关重要,不懂递归过程的话很容易看不懂移除代码  

function getSum(num){
     if(x === 1){
           return 1;
     }
     return num + getSum(num-1)
}

getSum(5);

过程如下:

①:getSum(5)调用函数并传入参数5,执行函数中的num +getSum(num-1) ->5+getSum(5-1)

②:getSum(4)调用函数并传入参数4,执行函数中的num+getSum(num-1) ->4+getSum(4-1)

③:getSum(3)调用函数并传入参数3,执行函数中的num+getSum(num-1) ->3+getSum(3-1)

④:getSum(2)调用函数并传入参数2,执行函数中的num+getSum(num-1) ->2+getSum(2-1)

⑤:getSum(1)调用函数并传入参数1,执行函数中的return 1;

⑥:这时候再一步一步往回走,即1+2+3+4+5;即可以理解为递归调用过程中,是不会立即计算的,要等到限制条件结束后,才会一步一步往上计算。


3:二叉搜索树的移除节点:移除节点程序是二叉搜索树程序方法中最复杂的一个。

eg: 

class Node{    //节点类
  constructor(key){
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
function defaultCompare(a, b) {  //比较函数
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};
class BinarySearchTree{
  constructor(compareFn = defaultCompare){
    this.compareFn = compareFn;
    this.root = null;
  }
  remove(key){                                       
    this.root = this.removeNode(this.root,key);
  }
  removeNode(node,key){
    if(node == null){
      return null;
    }
    if(this.compareFn(key,node.key) === Compare.LESS_THAN){      // (1)
      node.left = this.removeNode(node.left,key);                //(2)
      return  node;                            //(3)
    }else if (this.compareFn(key,node.key) === Compare.BIGGER_THAN){  //(4)
      node.right = this.removeNode(node.right,key);            //(5)
      return  node;                               //(6) 
    }else{                                    //(7)
      if(node.left == null && node.right == null){      //(8)    //第一种情况,移除一个叶节点(只有父节点没有子节点的节点)
        node = null;                              //(9)
        return  node;                             //(10)
      }
      if(node.left == null){               //第二种情况,移除有一个左or右子节点的节点
        node = node.right;                          //(11)
        return  node;                             //(12)
      }else if(node.right == null) {
        node = node.left;                                            //(13)
        return node;                             //(14)
      }
      const aux = this.minNode(node.right);         //(15) //第三种情况,移除有两个子节点的节点 
      node.key = aux.key;                //(16)
      node.right = this.removeNode(node.right,aux.key); //(17)
      return  node;                      //(18)
    }
  }   
}
const tree1 = new BinarySearchTree();
tree1.remove(8);

 假设现在有一个节点顺序为


现在我们需要移除节点8,则代码的顺序应该是:

①:开始时key:8   node: Node{ key: 11, left : Node, right : Node},进入行(1),判断大小后进入行(2),此时key:8   node: Node{ key: 7, left : Node, right : Node}
②:递归调用第一次,进入行(4)判断大小后进入行(5),此时key:8   node: Node{ key: 9, left : Node, right : Node}
③:递归调用第二次,进入行(1)判断大小后进入行(2),此时key:8   node: Node{ key: 8, left : null, right : null}
④:递归调用第三次,进入行(7 ,8, 9),返回一个node,此时key: 8 ,node :null;
⑤:进入行(3),此时结果为: key:8 ,node:Node{key: 9 ,left:null,right:Node};
⑥:进入行(6),此时结果为: key:8 ,node:Node{key: 9 ,left:Node,right:Node};
⑦:进入行(3),此时结果为:key:8 ,node:Node{key: 11,left:Node,right:Node};
⑧:返回到remove()后,跳出程序,节点8已移除。

备注1:上述步骤只实现了第一种情况,如果有需要,读者可以用chrome的调试工具进行断点调试,在Sources中可查看key及node的具体情况,

备注2:这里很明显说明了递归调用的执行顺序

 

站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/4644

关闭

递归思想与实战

递归算法对于一个程序员应该算是最经典的算法之一,而且它越想越乱,很多复杂算法的实现也都用到了递归,例如深度优先搜索,二叉树遍历等。面试中常常会问递归相关的内容(深拷贝,对象格式化,数组拍平,走台阶问题等)

vue依赖注入、递归组件的用法

在组件上面使用 ref 这个属性绑定,属性值自取,然后就可以通过 $refs.属性名 这种方式去获取到指定组件的实例了。其实不仅仅是组件能够使用 ref ,标签元素也能使用。

Js中的递归

递归函数是在一个函数通过名字调用自身的情况下构成的,这种写法在函数有名字,而且名字以后也不会变的情况下是没有问题的。但是函数的执行与函数名factorial紧紧耦合在了一起

递归获取页面元素的真实offsetLeft和offsetTop

由于父元素的定位属性, 导致子元素及其孙元素等的offsetLeft和offsetTop变得和预期不一致(预期上都是到屏幕左边和上边的位置), 由于需要做鼠标拖动旋转和鼠标框选

Vue一个案例引发的递归组件的使用

什么是递归组件?简单来说就是在组件中内使用组件本身,下面我们就来看看如何在项目中使用递归组件去解决我们上面问题。类似与信息分类的展示在我们的项目中是非常常见的形式,我们利用递归组件可以很好的去解决问题

原生js实现树级递归,通过js生成tree树形菜单(递归算法)

JavaScript生成树形菜单需求:首先这是一个数据集—js的类型,我们需要把生成一个tree形式的对象 : id,与pid之间的对应关系,当pid不存在,或pid:0的时候,这一项,应该为树的顶端,那么我们需要去重新建一次索引。

Js递归

传统的递归思想:自已调用自已,但是调用栈里面的执行上下文会越来越多,容易暴栈。采用尾递归可以规避这个问题:每次入栈出栈再入栈

浅谈javascript中的递归和闭包

递归和闭包作为js中很重要的一环,几乎在前端的面试中都会涉及,特别闭包。今天前端组的组长冷不丁的问了我一下,粗略的回答了一下,感觉不太满足,于是重新学习了一下,写下本篇。

AngularJS templates 递归循环

使用 ng-include 进行递归循环;在指令内,可以使用这样的结构;可以使用 ng-init 重命名子级变量名称

Vue 和递归组件

有人说递归很难理解,也有人不这么认为。递归函数简单的定义是:一个自调用函数,这意味着它将在执行的某个时刻调用自己。从理论上讲,递归是一种需要两个属性的行为:

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!