JavaScript二叉树（二叉搜索树）的详细介绍

可能有一部分人没有读过我上一篇写的二叉堆，所以这里把二叉树的基本概念复制过来了，如果读过的人可以忽略前面针对二叉树基本概念的介绍，另外如果对链表数据结构不清楚的最好先看一下本人之前写的js数据结构-链表

二叉树

二叉树(Binary Tree)是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。

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

二叉树的三个性质

1. 在二叉树的第i层上，至多有2^i-1个节点

2. i=1时，只有一个根节点，2^(i-1) = 2^0 = 1

3. 深度为k的二叉树至多有2^k-1个节点

4. i=2时，2^k-1 = 2^2 - 1 = 3个节点

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

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

二叉树分类

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

二叉搜索树

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

我们来举个例子来深入理解以下

一组数据：12,4,18,1,8,16,20
由下图可以看出，左边的图满足了二叉树的性质，它的每个左子节点都小于父节点，右子节点大于其父节点，同时左子树的节点都小于根节点，右子树的节点都大于根节点

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

二叉树搜索树的链式存储结构

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

用代码初始化一个二叉搜索树的结点：

 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是我们要插入的节点，它插入的具体步骤：

1. 跟根节点12做比较，比12大，所以我们确定了，这个节点是往右子树插入的

2. 而根节点的右边已经有节点，那么跟这个节点18做比较，结果小于18所以往18的左节点找位置

3. 而18的左节点也已经有节点了，所以继续跟这个节点做比较，结果小于16

4. 刚好16的左节点是空的(left=null)，所以13这个节点就插入到了16的左节点

通过上面的描述，我们来看看代码是怎么写的

 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;

 }

查找

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

 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;
 }

遍历

最常用的一般是中序遍历，因为中序遍历可以得到一个已经排好序的列表，这也是为什么会用二叉搜索树排序的原因

根据上面对中序遍历的解释，那么代码就变的很简单，就是一个递归的过程，递归停止的条件就是节点为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 < 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);
 }
}

总结

二叉查找树就讲完了哈，其实这个和链表很像的，还是操作那么几个指针，既然叫查找树了，它主要还是用来左一些搜索，还有就是排序了，另外补充一下，二叉查找树里找最大值和最小值也很方便是不是，如果你大致读懂了的话。

纷纭教育还为您提供以下相关内容希望对您有帮助：

平衡二叉树：任何节点的两个子树的高度差不超过1，保证了树的平衡性，提高了搜索效率。基于节点值的二叉树类型二叉搜索树：对于树中的每个节点，其左子树中的所有节点值都小于该节点的值，右子树中的所有节点值都大于该节点的值。AVL树：一种自平衡的二叉搜索树，通过旋转操作来保持树的平衡，确保搜索、插入和删除操作的时间复杂度为O(

二叉搜索树除了满足二叉树的性质，还满足自身的一个特性 所有左子树的节点都比根节点的值小，所有右子树节点的值都比根结点值大 而这个定义是递归定义的，左子树的左子树所有点比左子树根小，左子树的右子树比左子树的根大，对于每一棵子树都是这样 这样在查询一个数的时候，可以每次根据根的信息决定...

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，其核心特性是通过节点键值（key）的排序关系实现高效查找、插入和删除操作。以下是其关键特性的详细说明：核心定义与结构节点结构：每个节点包含键值（key）、卫星数据（存储的实际信息）及三个指针属性：left：指向左子节点 right：指向右...

平衡二叉树（Balanced Binary Tree）是为了解决二叉搜索树可能出现的退化成链表的问题而提出的。它的定义是：一棵空树，或者左右子树的高度之差不大于1，并且子树也必须是一棵平衡二叉树。平衡二叉树在插入和删除节点时，需要通过旋转操作来保持树的平衡性。这使得平衡二叉树的查找、插入和删除操作的时间复...

二叉搜索树是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：示例：观察二叉搜索树结构可知，查询每个节点需要的比较次数为节点深度加一。如深度为 0，节点值为 “6” 的根节点，只需要一次比较即可；深度为 1，节点值为 “3” 的节点，只需要两次比较。即二叉树节点个数确定的情况下，...

且最后一层的节点从左到右依次排列；二叉搜索树中，任意节点的左子树节点值都小于该节点值，右子树节点值都大于该节点值。在实际应用中，二叉搜索树常用于高效的查找和插入操作；堆（基于完全二叉树）可用于实现优先级队列；平衡的二叉搜索树（如红黑树）可用于实现 map 和 set 等数据结构。

二叉排序树也叫二叉搜索树、二叉查找树。二叉排序树树是一颗它的左子树上的节点都小于根节点，右子树上的节点都大于根节点的二叉树，且其左右子树也是二叉排序树。实例 当要向二叉排序树中插入元素的时候，从根节点开始查找，先将根节点作为当前节点，如果要插入的值比当前节点的值小，则判断当前节点的...

要判断两棵二叉树是否相同（结构和节点值都相同），可以使用深度优先搜索（DFS）算法。以下是改进后的代码实现，并附上详细说明：class Node { constructor(data) { this.left = null; this.right = null; this.data = data; }}// 改进后的判断函数const isIdentical = (tree1, ...

1、B树 即二叉搜索树：①所有非叶子结点至多拥有两个儿子（Left和Right）；②所有结点存储一个关键字；③非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树。2、B-树 是一种多路搜索树（并不是二叉的），B-树索引是基于二叉树结构的。B-树索引结构有3个基本组成部分：根节点...

二叉树的特点：二叉树的性质：1、二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，简称BST 2、二叉搜索树可以大大提高搜索数据的效率 3、二叉搜索树存储的元素必须具备可比较性 可以利用递归来实