作者:as123466_866 | 来源:互联网 | 2020-08-03 11:04
本篇文章给大家带来的内容是关于Javascript二叉树(二叉搜索树)的详细介绍,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
可能有一部分人没有读过我上一篇写的二叉堆,所以这里把二叉树的基本概念复制过来了,如果读过的人可以忽略前面针对二叉树基本概念的介绍,另外如果对链表数据结构不清楚的最好先看一下本人之前写的js数据结构-链表
二叉树
二叉树(Binary Tree)是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点,分支节点,叶子节点组成。而每个分支节点也常常被称作为一棵子树。
用代码初始化一个二叉搜索树的结点:
一个指向父亲节点的指针 parent
一个指向左节点的指针 left
一个指向右节点的指针 right
一个数据元素,里面可以是一个key和value
class BinaryTreeNode {
constructor(key, value){
this.parent = null;
this.left = null;
this.right = null;
this.key = key;
this.value = value;
}
}
接着我们再用代码去初始化一个二叉搜索树
class BinarySearchTree {
constructor() {
this.root = null;
}
}
创建节点
static createNode(key, value) {
return new BinarySearchTree(key, value);
}
插入操作
看下面这张图,13是我们要插入的节点,它插入的具体步骤:
跟根节点12做比较,比12大,所以我们确定了,这个节点是往右子树插入的
而根节点的右边已经有节点,那么跟这个节点18做比较,结果小于18所以往18的左节点找位置
而18的左节点也已经有节点了,所以继续跟这个节点做比较,结果小于16
刚好16的左节点是空的(left=null),所以13这个节点就插入到了16的左节点
通过上面的描述,我们来看看代码是怎么写的
定义两个指针,分别是p和tail,最初都指向root,p是用来指向要插入的位置的父节点的指针,而tail是用来查找插入位置的,所以最后它会指向null,用上图举个例子,p最后指向了6这个节点,而tail最后指向了null(tail为null则说明已经找到了要插入的位置)
循环,tail根据我们上面分析的一步一步往下找位置插入,如果比当前节点小就往左找,大则往右找,一直到tail找到一个空位置也就是null
如果当前的root为null,则说明当前结构中并没有节点,所以插入的第一个节点直接为跟节点,即this.root = node
将插入后的节点的parent指针指向父节点
insert(node){
let p = this.root;
let tail = this.root;
// 循环遍历,去找到对应的位置
while(tail) {
p = tail;
// 要插入的节点key比当前节点小
if (node.key 查找
查找就很简单了,其实和插入差多,都是去别叫左右节点的大小,然后往下找
search(key) {
let p = this.root;
if(!p) {
return;
}
while(p && p.key !== key){
if(p.key遍历
中序遍历(inorder):先遍历左节点,再遍历自己,最后遍历右节点,输出的刚好是有序的列表
前序遍历(preorder):先自己,再遍历左节点,最后遍历右节点
后序遍历(postorder):先左节点,再右节点,最后自己
最常用的一般是中序遍历,因为中序遍历可以得到一个已经排好序的列表,这也是为什么会用二叉搜索树排序的原因
根据上面对中序遍历的解释,那么代码就变的很简单,就是一个递归的过程,递归停止的条件就是节点为null
transverse() {
return this._transverse(this.root);
}
*_transverse(node){
if(!node){
return;
}
yield* this._transverse(node.left);
yield node;
yield* this._transverse(node.right)
}
看上面这张图,我们简化的来看一下,先访问左节点4,再自己12,然后右节点18,这样输出的就刚好是一个12,4,8
补充:这个地方用了generater,所以返回的一个迭代器。可以通过下面这种方式得到一个有序的数组,这里的前提就当是已经有插入的节点了
const tree = new BinaryTree();
//...中间省略插入过程
// 这样就返回了一个有序的数组
var arr = [...tree.transverse()].map(item=>item.key);
完整代码
class BinaryTreeNode {
constructor(key, value) {
// 指向父节点
this.p = null;
// 左节点
this.left = null;
// 右节点
this.right = null;
// 键
this.key = key;
// 值
this.value = value;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
static createNode(key, value) {
return new BinaryTreeNode(key, value);
}
search(key) {
let p = this.root;
if (!p) {
return;
}
while (p && p.key !== key) {
if (p.key 总结
二叉查找树就讲完了哈,其实这个和链表很像的,还是操作那么几个指针,既然叫查找树了,它主要还是用来左一些搜索,还有就是排序了,另外补充一下,二叉查找树里找最大值和最小值也很方便是不是,如果你大致读懂了的话。
以上就是Javascript二叉树(二叉搜索树)的详细介绍的详细内容,更多请关注 第一PHP社区 其它相关文章!