javascript算法之二叉搜索树的示例代码

什么是二叉树

二叉树就是树的每个节点最多只能有两个子节点

什么是二叉搜索树

二叉搜索树在二叉树的基础上,多了一个条件,就是二叉树在插入值时,若插入值比当前节点小,就插入到左节点,否则插入到右节点;若插入过程中,左节点或右节点已经存在,那么继续按如上规则比较,直到遇到一个新的节点。

二叉搜索树的特性

二叉搜索树由于其独特的数据结构,使得其无论在增删,还是查找,时间复杂度都是O(h),h为二叉树的高度。因此二叉树应该尽量的矮,即左右节点尽量平衡。

二叉搜索树的构造

要构造二叉搜索树,首先要构造二叉树的节点类。由二叉树的特点可知,每个节点类都有一个左节点,右节点以及值本身,因此节点类如下:

class Node {
 constructor(key) {
  this.key = key;
  this.left = null;
  this.right = null;
 }
}

接着构造二叉搜索树

class Tree{
 constructor(param = null) {
  if (param) {
   this.root = new Node(param);
  } else {
   this.root = null;
  }
 }
}

这里this.root就是当前对象的树。

二叉搜索树的新增

由二叉搜索树左子树比节点小,右子树别节点大的特点,可以很简单的写出二叉搜索树新增的算法,如下:

insert(key) {
 if (this.root === null) {
  this.root = new Node(key);
 } else {
  this._insertNode(this.root, key);
 }
}
_insertNode(node, key) {
 if (key < node.key) {
  if (node.left === null) {
   node.left = new Node(key);{1}
  } else {
   this._insertNode(node.left, key);{2}
  }
 } else if (key > node.key) {
  if (node.right === null) {
   node.right = new Node(key);{3}
  } else {
   this._insertNode(node.right, key);{4}
  }
 }
}

如上代码先判断新增的key与当前节点的key大小,如果小,就递归遍历左子节点,直到找到一个为null的左子节点;如果比当前节点大同理。如上代码{1}{2}{3}{4}之所以能改变this.root的值,是由于JavaScript函数是按值传递,而当参数是非基本类型时,例如这里的对象,其对象的值为内存,因此每次都会直接改变this.root的内容。

二叉搜索树的遍历

二叉搜索树分为先序、中序、后序三种遍历方式。

inOrderTraverse(callback) {
 this._inOrderTraverse(this.root, callback);
}
_inOrderTraverse(node, callback) {
 if (node) {
  this._inOrderTraverse(node.left, callback);
  callback(node.key);
  this._inOrderTraverse(node.right, callback);
 }
}

如上是中序遍历。

这里需要理解的一点是递归。要知道,函数的执行可以抽象为一种数据结构——栈。针对函数的执行,会维护一个栈,来存储函数的执行。函数在每一次递归时,都会将当前的执行环境入栈并记录执行的位置。以上述代码为例,有如下一个数据

其会从11开始,执行{1}入栈,然后进入7,接着执行{1}入栈,然后到5,执行{1}入栈,再到3,执行{1}入栈,此时发现节点3的左子节点为null,因此开始出栈,此时弹出节点3的执行环境,执行{2},{3},发现3的右侧子节点也为null,{3}的递归执行完毕,接着弹出节点5,执行{2}{3},接着弹出7,执行{2}{3}入栈,执行{3}时,发现节点7有右节点,因此继续执行{1},到节点8,再执行{1},8没有左子节点,{1}执行完毕,执行{2}{3},以此类推。

而前序与中序的不同点在于其先访问节点本身,也就是代码的执行顺序为 2 1 3。

后序同理,执行顺序为1 3 2

不难发现,无论前中后序,永远都是先递归左节点,当左节点遍历完毕时再弹出栈,遍历有节点。他们唯一不同的点在与访问该节点本身的时机。

二叉搜索树的查找

查找很简单,根据左子节点比该节点小,右子节点比该节点大的原则进行循环判断即可。

search(value) {
 if (this.root) {
  if (value === this.root.key) {
   return true;
  } else {
   return this._searchNode(value, this.root);
  }
 }
 throw new Error('this.root 不存在');
}
_searchNode(value, node) {
 if (!node) {
  return false;
 }
 if (value === node.key) {
  return true;
 }
 if (value > node.key) {
  return this._searchNode(value, node.right);
 } else if (value < node.key) {
  return this._searchNode(value, node.left);
 }
}

二叉搜索树的删除

删除较为复杂,需要根据不同情况判断

首先判断该节点是否有左子树,如果没有左子节树,则直接将右子树的根节点替换被删除节点;

如果有,则将右子树的最小节点替换被删除节点;

remove(key) {
 this._removeNode(this.root, key);
}
_removeNode(node, value) {
 if (!node) {
  return null;
 }
 if (value > node.key) {
  node.right = this._removeNode(node.right, value);
 } else if (value < node.key) {
  node.left = this._removeNode(node.left, value);
 } else {
  // 如果没有左子树,那么将右子树根节点作为替换节点
  if (!node.left) {
   return node.right;
   // 如果存在左子树,那么取右子树最小节点作为替换节点
  } else if (node.left) {
   return this._minNode(node.right);
  }
 }
}

总结

总的来说,通过这次简单的二叉搜索树的学习,让我重新认识了递归,以前对于递归的理解只是一些简单的理论概念,这次深入实践让我对递归的理解又加深了许多。

这让我想到了数学的学习,数学的理论公式是很容易记住掌握的,如果说对一个知识点的掌握满分是十分,那么直到真正去实践它之前,只看公式的掌握只能是2分,因为公式很简单,就几句话几个原则,但是遇到的问题是千变万化的,只有真正将理论付诸实践,经过各种实践的打磨蹂躏,才能真正理解它其中的奥秘。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2017-09-10

Javascript实现从小到大的数组转换成二叉搜索树

废话不多说了,直接给大家贴代码了,具体代码如下所示: var Array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; var Tree = createTree(Array); console.log(Tree); // 构造一个节点 function Node(nodeData, leftData, rightData) { this.nodeData = nodeData; this.leftData = leftData; this.rightData = rig

javascript数据结构之二叉搜索树实现方法

本文实例讲述了javascript二叉搜索树实现方法.分享给大家供大家参考,具体如下: 二叉搜索树:顾名思义,树上每个节点最多只有二根分叉:而且左分叉节点的值 < 右分叉节点的值 . 特点:插入节点.找最大/最小节点.节点值排序 非常方便 二叉搜索树-javascript实现 <script type="text/javascript"> // <![CDATA[ //打印输出 function println(msg) { document.write(msg

C#创建二叉搜索树的方法

本文实例讲述了C#创建二叉搜索树的方法.分享给大家供大家参考.具体如下: public static BinaryTreeNode BuildBinarySearchTree(int[] sortedArray) { if (sortedArray.Length == 0) return null; int _mid = sortedArray.Length / 2; BinaryTreeNode _root = new BinaryTreeNode(sortedArray[_mid]); in

C语言判定一棵二叉树是否为二叉搜索树的方法分析

本文实例讲述了C语言判定一棵二叉树是否为二叉搜索树的方法.分享给大家供大家参考,具体如下: 问题 给定一棵二叉树,判定该二叉树是否是二叉搜索树(Binary Search Tree)? 解法1:暴力搜索 首先说明一下二叉树和二叉搜索树的区别.二叉树指这样的树结构,它的每个结点的孩子数目最多为2个:二叉搜索树是一种二叉树,但是它有附加的一些约束条件,这些约束条件必须对每个结点都成立: 结点node的左子树所有结点的值都小于node的值. 结点node的右子树所有结点的值都大于node的值. 结点n

Python二叉搜索树与双向链表转换实现方法

本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

Java二叉搜索树基础原理与实现方法详解

本文实例讲述了Java二叉搜索树基础原理与实现方法.分享给大家供大家参考,具体如下: 前言:本文通过先通过了解一些二叉树基础知识,然后在转向学习二分搜索树. 1 树 1.1 树的定义 树(Tree)是n(n>=0)个节点的有限集.n=0时称为空树.在任意一颗非空树中: (1)有且仅有一个特定的称为根(Root)的节点: (2)当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1.T2........Tn,其中每一个集合本身又是一棵树,并且称为根的子树. 此外,树的定义还需要强调以

Java删除二叉搜索树的任意元素的方法详解

本文实例讲述了Java删除二叉搜索树的任意元素的方法.分享给大家供大家参考,具体如下: 一.删除思路分析 在删除二叉搜索树的任意元素时,会有三种情况: 1.1 删除只有左孩子的节点 节点删除之后,将左孩子所在的二叉树取代其位置:连在原来节点父亲元素右节点的位置,比如在图中需要删除58这个节点. 删除58这个节点后,如下图所示: 1.2 删除只有右孩子的节点: 节点删除之后,将右孩子所在的二叉树取代其位置:连在原来节点的位置,比如在下图中需要删除58这个节点. 删除58这个节点后,如下图所示: 这

Java删除二叉搜索树最大元素和最小元素的方法详解

本文实例讲述了Java删除二叉搜索树最大元素和最小元素的方法.分享给大家供大家参考,具体如下: 在前面一篇<Java二叉搜索树遍历操作>中完成了树的遍历,这一节中将对如何从二叉搜索树中删除最大元素和最小元素做介绍: 我们要想删除二分搜索树的最小值和最大值,就需要先找到二分搜索树的最小值和最大值,其实也还是很容易的,因为根据二叉搜索树的特点,它的左子树一定比当前节点要小,所以二叉搜索树的最小值一定是左子树一直往下走,一直走到底.同样在二叉搜索树中,右子树节点值,一定比当前节点要大,所以右子树一直

C++ 二叉搜索树(BST)的实现方法

废话不多说了,直接给大家贴代码了,具体代码如下所示: class BST { public: struct Node { int key;//节点的key int value;//节点的value Node* left; Node *right; int N;//节点的叶子节点数目 Node(int _key, int _value, int _N) { key = _key; value = _value; N = _N; } }; BST(); ~BST(); void put(int ke