JavaScript数据结构之二叉树的删除算法示例-创新互联
本文实例讲述了JavaScript数据结构之二叉树的删除算法。分享给大家供大家参考,具体如下:
创新互联于2013年成立,是专业互联网技术服务公司,拥有项目成都网站制作、网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元芜湖做网站,已为上家服务,为芜湖各地企业和个人服务,联系电话:18982081108从二叉查找树上删除节点的操作复杂程度取决于删除哪个节点。如果删除没有子节点的节点就非常简单,如果节点只有一个子节点,不管是左子节点还是右子节点,就变得稍微有点复杂,如果节点包含两个子节点就最复杂。
如果待删除节点是叶子节点,那么只需要将从父节点指向它的链接指向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另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
文章名称:JavaScript数据结构之二叉树的删除算法示例-创新互联
文章起源:http://scyanting.com/article/hegjd.html