【数据结构】二叉搜索树(BST)
定义1、一棵二叉树:
2、一颗二叉搜索树是满足下面条件的二叉树:
3、二叉搜索树的定义要求它的值必须能比较大小。为了强调这种区别,特称二叉搜索树的值为键,把节点存储的其他数据信息称为值。 数据组织二叉搜索树的节点: 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.root = null;
//方法
this.insert = insert; //插入函数
this.inOrder = inOrder; //中序遍历函数
}
function insert(data) {
var n = new Node(data,null,null);
if (this.root == null) {
this.root = n;
} else {
var current = this.root;
var parent;
while (true) {
parent = current;
if (data < current.data) {
current = current.left;
if (current == null) {
parent.left = n;
break;
}
} else {
current = current.right;
if (current == null) {
parent.right = n;
break;
}
}
}
}
}
遍历1、有三种遍历 BST 的方式: 中序遍历、 前序遍历和后序遍历。
算法描述函数: //中序遍历
function inOrder(node){
if(node != null){
inOrder(node.left);
console.log(node.show());
inOrder(node.right);
}
}
//前序遍历
function perOrder(node){
if(node != null){
console.log(node.show());
perOrder(node.left);
perOrder(node.right);
}
}
//后续遍历
function postOrder(node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
console.log(node.show());
}
}
4、通过中序遍历得到一个排序方法: var array = [23,45,16,37,3,99,22];
var nums = new BST();
for(var i in array){
nums.insert(array[i]);
}
console.log("Inorder traversal: ");
inOrder(nums.root);
// Inorder traversal: 3 16 22 23 37 45 99
搜索BST 通常有下列三种类型的查找:
lookup算法描述:
算法描述函数: 算法时间复杂度: 实现: /* * findup:在BST中查找一个元素 * 如果找到给定值, 该方法返回保存该值的节点; 如果没找到, 该方法返回 null。 */
function findup(data){ //递归实现
var current = this.root;
while(current!=null){
console.log(current)
if(current.data == data){
return current;
} else if(data<current.data){
current = current.left;
} else if(data > current.data){
current = current.right;
}
}
return null;
}
function findup(data){ //迭代实现
var current = this.root;
while(current!=null && current.data!=data){
if(data < current.data ){
current = current.left;
} else {
current = current.right;
}
}
return current;
}
最小元素和最大元素算法描述: /* * getMin():取得BST最小值 */
function getMin() {
var current = this.root;
while (current.left != null) {
current = current.left;
}
return current.data;
}
/* - getMax():取得BST最小值 */
function getMax() {
var current = this.root;
while (current.right!= null) {
current = current.right;
}
return current.data;
}
前驱和后继后继(Succ):给定元素
实现: /* * Succ:后继函数 * param: x——给定元素 * return:返回给顶元素在BST中的后继 */
function Succ(x){
if(x.right!=null){
//getMin(node) 获取以node节点为根节点的BST的最小值
return this.getMin(x.right);
} else{
//Node节点有一个parent属性来保存父节点
var parent = x.parent;
while(parent!=null&&x ==parent.right){
x = parent;
parent = parent.parent;
}
return parent;
}
}
/* * Pred:前驱函数 * param: x——给定元素 * return:返回给顶元素在BST中的前驱 */
function Pred(x){
if(x.left!=null){
//getMax(node) 获取以node节点为根节点的BST的最大值
return this.getMax(x.left);
} else{
var parent = x.parent;
while(parent!=null&&x ==parent.left){
x = parent;
parent = parent.parent;
}
return parent;
}
}
删除算法描述:
因为右子树中的最小值节点不可能有两个非空的孩子,因此将上面第二种情况简化为第一种情况,因而可以直接将最小值节点“切掉”。 算法描述函数: 实现: /* * removeData:删除数据 * param: * node——要删除数据的节点 * data——要删除的数据 * return: * 已删除data数据的树根节点 */
function removeData(node,data){
if(node == null){ //空树
return null;
}
if (data == node.data) {
if (node.left == null && node.right == null) { //没有子节点的节点
return null;
}
if (node.left == null) { //没有左子树的节点
return node.right;
}
if (node.right == null) { //没有右子树的节点
return node.left;
}
//有左右子树的节点
var tempNode = getMin(node.right);
node.data = tempNode.data;
node.right = removeData(node.right,tempNode.data);
return node;
}else if(data < node.data){
node.left = removeData(node.left,data);
return node;
}else{
node.right = removeData(node.right,data);
return node;
}
}
/* * remove() 方法:简单地接受待删除数据 */
function remove(data){
this.root = removeData(this.root,data);
}
//test
var nums = new BST();
var arr = [4,8,1,2,10,9,14]; for(var i in arr){ nums.insert(arr[i]); } nums.remove(4); console.log(nums.root); (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |