乐趣区

js数据结构-二叉树(二叉搜索树)

前言
可能有一部分人没有读过我上一篇写的二叉堆,所以这里把二叉树的基本概念复制过来了,如果读过的人可以忽略前面针对二叉树基本概念的介绍,另外如果对链表数据结构不清楚的最好先看一下本人之前写的 js 数据结构 - 链表
二叉树
二叉树 (Binary Tree) 是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点,分支节点,叶子节点组成。而每个分支节点也常常被称作为一棵子树。

根节点:二叉树最顶层的节点
分支节点:除了根节点以外且拥有叶子节点
叶子节点:除了自身,没有其他子节点

常用术语在二叉树中,我们常常还会用父节点和子节点来描述,比如图中 2 为 6 和 3 的父节点,反之 6 和 3 是 2 子节点
二叉树的三个性质

在二叉树的第 i 层上,至多有 2^i- 1 个节点
i= 1 时,只有一个根节点,2^(i-1) = 2^0 = 1

深度为 k 的二叉树至多有 2^k- 1 个节点
i= 2 时,2^k-1 = 2^2 – 1 = 3 个节点

对任何一棵二叉树 T,如果总结点数为 n0,度为 2(子树数目为 2)的节点数为 n2, 则 n0=n2+1

树和二叉树的三个主要差别

树的节点个数至少为 1,而二叉树的节点个数可以为 0
树中节点的最大度数 (节点数量) 没有限制, 而二叉树的节点的最大度数为 2
树的节点没有左右之分,而二叉树的节点有左右之分

二叉树分类
二叉树分为完全二叉树 (complete binary tree) 和满二叉树(full binary tree)

满二叉树:一棵深度为 k 且有 2^k – 1 个节点的二叉树称为满二叉树
完全二叉树:完全二叉树是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)

二叉搜索树
二叉搜索树满足以下的几个性质:

若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
任意节点的左、右子树也需要满足左边小右边大的性质

我们来举个例子来深入理解以下
一组数据:12,4,18,1,8,16,20 由下图可以看出,左边的图满足了二叉树的性质,它的每个左子节点都小于父节点,右子节点大于其父节点,同时左子树的节点都小于根节点,右子树的节点都大于根节点

二叉搜索树主要的几个操作:

查找(search)
插入(insert)
遍历(transverse)

二叉树搜索树的链式存储结构
通过下图,可以知道二叉搜索树的节点通常包含 4 个域,数据元素,分别指向其左,右节点的指针和一个指向父节点的指针所构成,一般把这种存储结构称为三叉链表。
用代码初始化一个二叉搜索树的结点:

一个指向父亲节点的指针 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;
}
}
接着我们再用代码去初始化一个二叉搜索树
在二叉搜索树中我们会维护一个 root 指针,这个就相当于链表中的 head 指针,在没有任何节点插入的时候它指向空,在有节点插入以后它指向根节点。
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 < tail.key){
tail.left = tail.left;
}
// 要插入的节点 key 比当前节点大
else {
tail.right = tail.right;
}
}

// 没有根节点,则直接作为根节点插入
if(!p) {
this.root = node;
return;
}

// p 是最后一个节点,也就是我们要插入的位置的父节点
// 比父节点大则往右边插入
if(p.key < node.key){
p.right = node;
}
// 比父节点小则往左边插入
else {
p.left = node;
}

// 指向父节点
node.parent = p;

}
查找
查找就很简单了,其实和插入差多,都是去别叫左右节点的大小,然后往下找

如果 root = null, 则二叉树中没有任何节点,直接 return,或者报个错什么的。
循环查找

search(key) {
let p = this.root;
if(!p) {
return;
}

while(p && p.key !== key){
if(p.key<key){
p = p.right;
}else{
p = p.left;
}
}

return p;
}
遍历

中序遍历(inorder):先遍历左节点,再遍历自己,最后遍历右节点,输出的刚好是有序的列表
前序遍历(preorder):先自己,再遍历左节点,最后遍历右节点
后序遍历(postorder):先左节点,再右节点,最后自己

最常用的一般是中序遍历,因为中序遍历可以得到一个已经排好序的列表,这也是为什么会用二叉搜索树排序的原因
根据上面对中序遍历的解释,那么代码就变的很简单,就是一个递归的过程,递归停止的条件就是节点为 null

先遍历左节点 –>yield* this._transverse(node.left)
遍历自己 –> yield* node
遍历左节点 –> yield* this._transverse(node.right)

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 < key) {
p = p.right;
} else {
p = p.left;
}
}

return p;
}

insert(node) {
// 尾指针的父节点指针
let p = this.root;

// 尾指针
let tail = this.root;

while (tail) {
p = tail;
if (node.key < tail.key) {
tail = tail.left;
} else {
tail = tail.right;
}
}

if (!p) {
this.root = node;
return;
}

// 插入
if (p.key < node.key) {
p.right = node;
} else {
p.left = node;
}

node.p = p;
}

transverse() {
return this.__transverse(this.root);
}

*__transverse(node) {
if (!node) {
return;
}
yield* this.__transverse(node.left);
yield node;
yield* this.__transverse(node.right);
}
}
总结
二叉查找树就讲完了哈,其实这个和链表很像的,还是操作那么几个指针,既然叫查找树了,它主要还是用来左一些搜索,还有就是排序了,另外补充一下,二叉查找树里找最大值和最小值也很方便是不是,如果你大致读懂了的话。这篇文章我写的感觉有点乱诶,因为总感觉哪里介绍的不到位,让一些基础差的人会看不懂,如果有不懂或者文章哪里写错了,欢迎评论留言哈
后续
后续写什么呢,这个问题我也在想,排序算法,react 第三方的一些模拟实现?,做个小程序组件库?还是别的,容我再想几个小时,因为可以,有建议的朋友们也可以留言说一下哈。最后最后,最重要的请给个赞,请粉一个呢,谢谢啦

退出移动版