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

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

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

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

1.树-创建BinarySearchTree类

function BinarySearchTree() {var Node &＃61; function(key){ //{1} 节点包括键、左侧子节点、右侧子节点this.key &＃61; key; //键this.left &＃61; null; //左侧子节点this.right &＃61; null; //右侧子节点};var root &＃61; null; //{2} //根元素
}


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

2.insert

//插入insert
this.insert &＃61; function(key){var newNode &＃61; new Node(key);if(root &＃61;&＃61;&＃61; null){root &＃61; newNode;}else{insertNode(root,newNode);}
}var insertNode &＃61; function(node,newNode){if(newNode.key }


3.树的遍历

//var tree &＃61; new BinarySearchTree(); //中序遍历
this.inOrderTraverse &＃61; function(callback){inOrderTraverseNode(root,callback);
}var inOrderTraverseNode &＃61; function(node,callback){if (node!&＃61;&＃61;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 &＃61; function(){return minNode(root);
}
var minNode &＃61; function(node){if(node){while(node && node.left !&＃61;&＃61; null){node &＃61; node.left;}return node.key;}return null;
}this.search &＃61; function(key){return searchNode(root,key);
}
var searchNode &＃61; function(node,key){if(node &＃61;&＃61;&＃61; null){return false;}if(key node.key){return searchNode(node.right,key);}else{return true;}
}


5.树的移除

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


更多可以参考&＃xff1a;https://www.cnblogs.com/xiaohuochai/p/8184989.html#anchor4

附注一张图&＃xff1a;
在这里插入图片描述