前端：二叉树算法在JavaScript中的实现_0

下面我们来讨论一下js数据结构中的树。这里的树类似于现实生活中的树。它有树干和树枝。在程序中，树是一种数据结构，对于存储需要快速查找的数据用处不大。它是分层数据的抽象模型。树结构由一系列具有父子关系的节点组成。每个节点都有一个父节点和零个或多个子节点。下面是一个树结构：）与树相关的概念：1.子树：由节点及其后代组成，如上图所示。2.深度：节点的深度取决于其祖先节点的数量。例如节点5有2个祖先节点，其深度为2。3.高度：树的高度取决于所有节点深度的最大值。二叉树和二叉搜索树简介二叉树中的一个节点最多只能有2个子节点，一个是左子节点，一个是右子节点。这样定义的好处是有利于我们编写更高效的插入、查找、删除节点的算法。二叉搜索树是二叉树的一种，但它只允许你在左子节点中存储小于父节点的值，而在右节点中存储大于父节点的值。下面我们就按照这个思路来实现一个二叉搜索树。1.创建BinarySearchTree类这里我们将使用构造函数创建一个类：functionBinarySearchTree(){//创建节点的类letNode=function(key){this.key=key;this.left=null;this.right=null;}//根节点letroot=null;}我们将使用类似于链表的指针来表示节点之间的关系。如果你不知道链表，请阅读我的后记《如何实现单向链表和双向链表》。2.Insertakey//Insertakeythis.insert=function(key){letnewNode=newNode(key);root===null?(root=newNode):(insertNode(root,newNode))}到树中插入新节点主要有以下三部分：1.创建新节点的Node类实例-->2.判断插入操作是否为根节点，如果是根节点则指向根node-->3.添加节点除根节点以外的其他位置。insertNode具体实现如下：functioninsertNode(node,newNode){if(newNode.keynode.key){returnsearchNode(node.right,key)}else{returntrue}}3删除anodethis.remove=function(key){root=removeNode(root,key);}//求最小节点functionfindMinNode(node){if(node){while(node&&node.left!==null){node=node.left;}returnnode}returnnull}//移除节点辅助方法函数removeNode(node,key){if(node===null){returnnull}if(keynode.key){node.right=removeNode(node.right,key);returnnode}else{//一个页面节点if(node.left===null&&node.right===null){node=null;returnnode}//只有一个子节点的节点if(node.left===null){node=node.right;returnnode}elseif(node.right===null){node=node.left;returnnode}//有是两个节点letaux=findMinNode(node.right);node.key=aux.key;node.right=removeNode(node.right,aux.key);returnnode}}删除节点时需要考虑的情况很多。这里我们将使用类似于min的实现来编写一个函数来查找最小节点。当待删除节点有两个子节点时，我们需要将当前待删除节点替换为子节点中最大节点的值，然后使用这个至此实现了一颗二叉查找树，但是有仍然是一个问题。如果树很深，会有一定的性能问题。为了解决这个问题，我们可以使用AVL树，一种自平衡的二叉树，也就是说任意一个节点的左右子树的高度差最多为1。