JavaScript数据结构与算法（10）树

谁借莪１个温暖的怀抱￠ 2022-01-27 12:45 206阅读 0赞

前面介绍过一种非顺序数据结构是散列表，本文将详细介绍另一种非顺序数据结构——树，它对于存储需要快速查找的数据非常有用

二叉树、满二叉树、完全二叉树、堆、二叉搜索树BST/二叉查找树/二叉排序树

二叉搜索树是我们这章要研究的数据结构

**1.树-创建BinarySearchTree类**

然后，我们需要实现一些方法。下面是将要在树类中实现的方法：  
insert(key)：向树中插入一个新的键。  
search(key)：在树中查找一个键，如果节点存在，则返回true；如果不存在，则返回 false。  
inOrderTraverse：通过中序遍历方式遍历所有节点。  
preOrderTraverse：通过先序遍历方式遍历所有节点。  
postOrderTraverse：通过后序遍历方式遍历所有节点。  
min：返回树中最小的值/键。  
max：返回树中最大的值/键。  
remove(key)：从树中移除某个键。

**2.insert**

//插入insert
    this.insert = function(key){
    	var newNode = new Node(key);
    	if(root === null){
    		root = newNode;
    	}else{
    		insertNode(root,newNode);
    	}
    }
    
    var insertNode = function(node,newNode){
    	if(newNode.key < node.key){
    
    		if(node.left === null){
    			node.left = newNode;
    		}else{
    			insertNode(node.left,newNode);
    		}
    
    	}else{
    		if(node.right === null){
    			node.right = newNode;
    		}else{
    			insertNode(node.right,newNode);
    		}
    	}
    }

**3.树的遍历**

//var tree = new BinarySearchTree(); 
    
    //中序遍历
    this.inOrderTraverse = function(callback){
    	inOrderTraverseNode(root,callback);
    }
    
    var inOrderTraverseNode = function(node,callback){
    	if (node!==null) {
    		inOrderTraverseNode(node.left,callback);
    		callback(node.key);
    		inOrderTraverseNode(node.right,callback);
    	}
    }
    	//回调函数callback
    function printNode(value){
    	console.log(value);
    }
    	//tree调用中序遍历
    tree.inOrderTraverse(printNode);

**4.树的搜索**

//树的搜索(最小值、最大值、特定值)
    this.min = function(){
    	return minNode(root);
    }
    var minNode = function(node){
    	if(node){
    		while(node && node.left !== null){
    			node = node.left;
    		}
    
    		return node.key;
    	}
    	return null;
    }
    
    this.search = function(key){
    	return searchNode(root,key);
    }
    var searchNode = function(node,key){
    	if(node === null){
    		return false;
    	}
    	if(key < node.key){
    		return searchNode(node.left,key);
    	}else if(key > node.key){
    		return searchNode(node.right,key);
    	}else{
    		return true;
    	}
    }

**5.树的移除**

//移除一个节点
    this.remove = function(key){
    	root = removeNode(root,key);
    }
    var removeNode = function(node,key){
    
    	if(node === null){
    		return null;
    	}
    
    	if (key<node.key) {
    		node.left = removeNode(node.left,key);
    		return node;
    	}else if(key>node.key){
    		node.right = removeNode(node.right,key);
    		return node;
    	}else{
    		//键等于node.key 
    	    //第一种情况——一个叶节点     
    	    if (node.left === null && node.right === null){ //{9}      
    	      node = null; //{10}       
    	      return node; //{11}     
    	    } 
    	    //第二种情况——一个只有一个子节点的节点     
    	    if (node.left === null){ //{12}       
    	      node = node.right; //{13}
    	      return node; //{14} 
    	    } else if (node.right === null){ //{15}       
    	      node = node.left; //{16}       
    	      return node; //{17}     
    	    } 
    	    //第三种情况——一个有两个子节点的节点     
    	    var aux = findMinNode(node.right); //{18}     
    	    node.key = aux.key; //{19}     
    	    node.right = removeNode(node.right, aux.key); //{20}     
    	    return node; //{21} 
    	}
    
    }

更多可以参考：https://www.cnblogs.com/xiaohuochai/p/8184989.html\#anchor4

附注一张图：  
在这里插入图片描述