JavaScript数据结构之二叉树的删除算法示例

本文实例讲述了JavaScript数据结构之二叉树的删除算法。分享给大家供大家参考，具体如下：

从二叉查找树上删除节点的操作复杂程度取决于删除哪个节点。如果删除没有子节点的节点就非常简单，如果节点只有一个子节点，不管是左子节点还是右子节点，就变得稍微有点复杂，如果节点包含两个子节点就最复杂。

如果待删除节点是叶子节点，那么只需要将从父节点指向它的链接指向null。

如果待删除节点只包含一个子节点，那么原本指向它的节点就得使其指向它的子节点。

如果待删除节点包含两个子节点，那么我们可以采用两种方式，一种是查找待删除节点左子树上的最大值，一种是查找待删除节点右节点上的最小值。我们采取后者，找到最小值后，将临时节点上的值复制到待删除节点，然后再删除临时节点。

删除操作的代码如下：

function getSmallest(node){//查找最小节点
    while(node.left!=null){
      node=node.left;
    }
    return node;
}
function remove(data){
    root=removeNode(this.root,data);//将根节点转换
}
function removeNode(node,data){
    if(node==null){
      return null;
    }
    if(data==node.data){
      //如果没有子节点
      if(node.right==null&&node.left==null){
        return null;//直接将节点设为空
      }
      //如果没有左子节点
      if(node.left==null){
        return node.right;//直接指向其右节点
      }
      //如果没有右子节点
      if(node.right==null){
        return node.left;
      }
      //如果有两个节点
      if(node.right!=null&&node.left!=null){
        var tempNode=getSmallest(node.right);//找到最小的右节点
        node.data=tempNode.data;
        node.right=removeNode(node.right,tempNode.data);//依次寻找
        return node;
      }
    }else if(data<node.data){
      node.left=removeNode(node.left,data);
      return node;
    }else{
      node.right=removeNode(node.right,data);
      return node;
    }
}

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

赞 (0)

相关推荐

  • JavaScript数据结构和算法之二叉树详解

    JavaScript数据结构和算法之二叉树详解

    二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母.左孩子和右孩子的指针.每一个节点都是通过指针相互连接的.相连指针的关系都是父子关系. 二叉树节点的定义 二叉树节点定义如下: 复制代码 代码如下: struct

  • JavaScript实现树的遍历算法示例【广度优先与深度优先】

    JavaScript实现树的遍历算法示例【广度优先与深度优先】

    本文实例讲述了JavaScript实现树的遍历算法.分享给大家供大家参考,具体如下: <script type="text/javascript"> var t = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]; //下面这段深度优先搜索方法出自Aimingoo的[JavaScript语言精髓与编程实践] var deepView = function(aTree,iNode) { (iNode in aTree)

  • JavaScript数据结构之二叉树的计数算法示例

    本文实例讲述了JavaScript数据结构之二叉树的计数算法.分享给大家供大家参考,具体如下: 二叉查找树的一个用途就是记录一组数据集中数据出现的次数.比如记录成绩的分布,给定一组考试成绩,如果未出现则加入树,如果已经出现则数量加一. 所以要修改Node对象,添加记录成绩出现次数加一,代码如下: function Node(data,left,right){ this.data=data; this.left=left; this.right=right; this.show=show; thi

  • JS中的二叉树遍历详解

    二叉树是由根节点,左子树,右子树组成,左子树和友子树分别是一个二叉树. 这篇文章主要在JS中实现二叉树的遍历. 一个二叉树的例子 var tree = { value: 1, left: { value: 2, left: { value: 4 } }, right: { value: 3, left: { value: 5, left: { value: 7 }, right: { value: 8 } }, right: { value: 6 } } } 广度优先遍历 广度优先遍历是从二叉树

  • JavaScript数据结构之二叉树的遍历算法示例

    本文实例讲述了JavaScript数据结构之二叉树的遍历算法.分享给大家供大家参考,具体如下: 三种遍历的代码: function inOrder(node){//中序遍历 if(node!=null){ inOrder(node.left); document.write(node.show()+" "); inOrder(node.right); } } function preOrder(node){//先序遍历 if(node!=null){ document.write(no

  • javascript实现二叉树遍历的代码

    javascript实现二叉树遍历的代码

    前言: 紧接着上篇 二叉树的javascript实现 ,来说一下二叉树的遍历. 本次一本正经的胡说八道,以以下这个二叉树为例子进行遍历: 接着是要引入二叉树实现的代码: function Node(data, left, right) { this.data = data; this.left = left; this.right = right; this.show = show; } function show() { return this.data; } function BST() {

  • javascript先序遍历DOM树的方法

    DOM树由文档中的所有节点(元素节点.文本节点.注释节点等)所构成的一个树结构,DOM树的解析和构建是浏览器要实现的关键功能.既然DOM树是一个树结构,那么我们就可以使用遍历树结构的相关方法来对DOM树进行遍历,同时DOM2中的"Traversal"模块又提供了两种新的类型,从而可以很方便地实现DOM树的先序遍历. 注:本文中的5种方法都是对DOM的先序遍历方法(深度优先遍历),并且只关注Element类型. 1. 使用DOM1中的基础接口,递归遍历DOM树 DOM1中为基础类型Nod

  • JS二叉树的简单实现方法示例

    本文实例讲述了JS二叉树的简单实现方法.分享给大家供大家参考,具体如下: 今天学习了一下 二叉树的实现,在此记录一下 简单的二叉树实现,并且实现升序和降序排序输出 function Node(data , left,right){ this.data = data; this.left = left; this.right = right; this.show = show; function show(){ return this.data; } }; function Bst(){ this

  • JS实现的二叉树算法完整实例

    本文实例讲述了JS实现的二叉树算法.分享给大家供大家参考,具体如下: <!DOCTYPE HTML> <head> <title>20130328BinaryTree</title> <metahttp-equiv="Content-Type" content="text/html; charset=utf-8" /> </head> <html> <body> <

  • JavaScript实现二叉树的先序、中序及后序遍历方法详解

    本文实例讲述了JavaScript实现二叉树的先序.中序及后序遍历方法.分享给大家供大家参考,具体如下: 之前学数据结构的时候,学了二叉树的先序.中序.后序遍历的方法,并用C语言实现了,下文是用js实现二叉树的3种遍历,并以动画的形式展现出遍历的过程. 整个遍历过程还是采用递归的思想,原理很粗暴也很简单 先序遍历的函数: function preOrder(node){ if(!(node==null)){ divList.push(node); preOrder(node.firstEleme

  • javascript实现二叉树的代码

    javascript实现二叉树的代码

    前言: 二叉树的特点(例图只是二叉树的一种情况,不要尝试用例图推理以下结论) 除了最下面一层,每个节点都是父节点,每个节点都有且最多有两个子节点: 除了嘴上面一层,每个节点是子节点,每个节点都会有一个父节点: 最上面一层的节点(即例图中的节点50)为根节点: 最下面一层的节点称为叶子节点,他们没有子节点: 左子节点的值 < 父节点的值 <= 右节点的值 1 节点的javascript实现 // 节点对象 function Node(data, left, right) { this.data

  • JavaScript数据结构之二叉树的查找算法示例

    本文实例讲述了JavaScript数据结构之二叉树的查找算法.分享给大家供大家参考,具体如下: 前面文章介绍了二叉树的遍历,现在谈谈在二叉树中进行查找.对二叉查找树来说,一般有以下三类查找:最大值,最小值和给定值. 查找最小值就是遍历左子树,直到找到最后一个结点,这是因为在二叉查找树中较小的值总是在左子节点上的. 代码如下: function getMin(){//查找最小值 var current=this.root;//指向根节点 while(current.left!=null){ cur

随机推荐