【数据结构与算法】树结构(二叉树)_数据结构与算法树结构代码

树结构

• 树结构(Tree)
  • 可以把树结构看做是现实中的树，有很多分叉，只不过数据结构中的树是倒过来的

树的优点

-+ 数组的优点
    - 数组的主要优点是根据下标访问的效率会很高。
    - 如果想根据元素来访问元素的时候，比较好的方式就是先对数组进行排序，生成有序数组，才能提高查找效率
-+ 数组的缺点
    - 需要先对数组进行排序，生成有序数组，才能提高查找效率。
    - 在数组进行插入和删除数据的时候，需要有大量的位移操作（首位或中间位置），效率低

-+ 链表的优点
    - 链表的插入和删除操作效率很高
-+ 链表的缺点
    - 查找的效率很低，需要从头开始依次访问链表中的每一个数据项
    - 即使是插入和删除数据，如果插入、删除的位置是链表中间，还是需要从头、从尾不开始找到对应数据

-+ 哈希表的优点
    - 插入、查询、删除的效率都很高
-+ 哈希表的缺点
    - 空间利用不高。底层利用的是数组。有些位置还是空值
    - 哈希表中的数据是无序的。不能按照固定顺序遍历哈希表中的元素
    - 不能快速找到特殊的值（最大值。最小值等）

—+ 树结构的优点
    - 查找效率特别高
    ·····
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

树的术语

• 树(Tree): n(n >= 0)个节点构成的有限集合，且当n = 0 的时候（没有节点），这个时候即空树
• 一个非空的树(n > 0)它会有一个根节点（Root）
• 其他节点可以分为m(m > 0)个互不相交的有限集t1，t2，tm````,每个集合又是一棵树，称为子树
• 节点的度（degree）：节点的子树个数
• 树的度：树的所有节点中最大的度数
• 叶节点（leaf）：度为0的节点（也称叶子结点）
• 父节点
• 子节点
• 兄弟节点
• 路径和路径长度：从节点n1到nk的路径为一个节点序列n1，n2···，nk，ni是ni-1的父节点，路径中所包含的路径个数为路径长度
• 节点层数（level）：根节点所在节点层次为1，子节点依次类推
• 树的深度（depth）: 树中所有节点中最大的的节点层次是这个树的深度

---

树的表示方式

基础表示和兄弟表示法

任意的三叉树及多叉树都可以通过旋转变换得到二叉树结构

---

二叉树

• 树结构中每个节点的子节点最多有两个，这样的树就叫做二叉树

结构

• 有空树
• 只有一个节点
• 左子节点
• 右子节点
• 完整二叉树

特性

• 二叉树第i层最大的节点数为2^(i-1),i>=1

• 深度为k的二叉树总的节点数最大为2^k - 1

• 对于任意非空二叉树T，m表示叶节点的个数，n表示度为2的非叶节点的个数，满足m = n + 1

• 完美二叉树（满二叉树）

  • 除叶节点外，每个节点的度为2（每个节点都有两个子节点），这样的树被称为满二叉树

• 完全二叉树

  • 除最后一层外，其他各层的节点数都达到最大，且最后一层从左向右的叶节点连续存在，只缺右侧若干节点

  • 完美二叉树是特殊的完全二叉树
    

• 二叉搜索树BST（二叉排序树，二叉查找树）

  • 二叉搜索树是一颗二叉树，可以为空;
  • 如果不为空，二叉树就必须满足以下特性
    • 非空左子树的所有键值小于其根节点的键值
    • 非空右子树所有的键值大于其根节点的键值
    • 左右本身也是二叉搜索树
      

---

二叉搜索树的实现

实现属性和方法

常见的二叉搜索树的属性方法
	
	属性
    header：指向根节点的指针
	
	方法
    insert(key, value)：向树中插入一个新的键和值
    search(key):在树中搜索对应key值的value;
    inOrderTraverse: 通过中序遍历方式遍历所有的节点
    preOrderTraverse: 通过先序遍历方式遍历所有节点
    postOrderTraverse: 通过后序遍历的方式遍历所有节点
    alter(key, value):修改对应key的value值
    remove(key): 移除对应key的值
    min: 返回树中最小的键的值
    max：返回树中最大的键的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

二叉搜索树的遍历

• 先序遍历

从根节点开始，沿着左子树方向遍历，直到节点左子树为null，那么则从右子树节点遍历，若左右均没有子树，则退回上一层次继续遍历

• 中序遍历

先从最左边的节点开始遍历，树节点有左节子树点，则沿左子树遍历，没有则向右子树遍历，左右子树都没有返回上一层次树结构

• 后序遍历

先从最左边的节点开始遍历，树节点有右节子树点，则沿右子树遍历，没有则向左子树遍历，左右子树都没有返回上一层次树结构

---

我们发现这里需要使用递归遍历和while遍历更为方便，因为找不到子树时，需要返回到上一层次或者更上一层次遍历，而递归遍历在某一层次遍历后，可以返回到相应的上一层次结构中，所以使用递归遍历或者while遍历。

---

二叉树的实现

创建创建树节点的class

// 创建实例树结构节点的类
class TreeNode {

    constructor(key, value) {
        // 索引值
        this.key = key;
        // value值
        this.value = value;
        // 树节点左指针 --- 指向左子树
        this.leftNext = null;
        // 树节点右指针 --- 指向右子树
        this.rightNext = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

通过此类可以随时new一个树节点对象

创建树的实现（通过类）

// 创建树结构实现类
class MyTree {
    // 私有的头部指针---指向root节点
    #header = null;
}
1
2
3
4
5

通过此类可以随时new一个二叉搜树对象

---

实现方法—二叉树类中

获取根节点

	// 获取根节点
    get getMyTree() {
        return this.#header;
    }
1
2
3
4

返回根节点

二叉搜索树插入节点的方法

 	// 插入节点
    insert(key, value) {
        // 检测类型
        let isNumKey = Object.prototype.toString,
            // 新节点变量
            newTreeNode;

        // 判断输入key值的类型
        if (isNumKey.call(key) !== '[object Number]') {
            throw new Error('key值非数值');
        }

        // 创建新的树节点
        newTreeNode = new TreeNode(key, value);

        // 判断根节点是否有值
        if (this.#header === null) {
            // 有值将根节点指向指向新节点
            this.#header = newTreeNode;
        } else {
            // 没有则进入递归查找子树
            this.#recursiveInsert(this.#header, newTreeNode);
        }
    }

    // 递归插入节点
    #recursiveInsert(currentNode, newNode) {
        // 判断新增节点key是否小于当前节点
        if (currentNode.key > newNode.key) {
            // 小于则进入左分支树

            // 判断左子树是否值为空
            if (currentNode.leftNext === null) {
                // 为空则将新节点添加到这个位置
                currentNode.leftNext = newNode;
            } else {
                // 不为空进入下一次递归插入值
                this.#recursiveInsert(currentNode.leftNext, newNode);
            }

        } else if (currentNode.key < newNode.key) {
            // 大于进入右分支树

            // 判断右子树是否值为空
            if (currentNode.rightNext === null) {
                // 为空则将新节点添加到这个位置
                currentNode.rightNext = newNode;
            } else {
                // 不为空进入下一次递归插入值
                this.#recursiveInsert(currentNode.rightNext, newNode);
            }
        } else {
            throw new Error('key existing！');
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

主要是递归部分，将创建好的树节点在树结构中查找对应符合二叉搜索树结构的位置插入数据，要注意结构中没有数据的情况

测试

// 创建树结构
let tree = new MyTree();

tree.insert(10, '根节点');
tree.insert(1, '子树1');
tree.insert(8, '树3');
tree.insert(14, '树4');
tree.insert(-2, '最小');
tree.insert(20, '树5');
tree.insert(3, '树6');
tree.insert(24, '44');
tree.insert(-10, '树115');
tree.insert(32, '树46');
tree.insert(4, '123');
tree.insert(44, {name: 'andy'});

 console.log(tree.getMyTree);
 //TreeNode {
  key: 10,
  value: '根节点',
  leftNext: TreeNode {
    key: 1,
    value: '子树1',
    leftNext: TreeNode {
      key: -2,
      value: '最小',
      leftNext: [TreeNode],
      rightNext: null
    },
    rightNext: TreeNode {
      key: 8,
      value: '树3',
      leftNext: [TreeNode],
      rightNext: null
    }
  },
  rightNext: TreeNode {
    key: 14,
    value: '树4',
    leftNext: null,
    rightNext: TreeNode {
      key: 20,
      value: '树5',
      leftNext: null,
      rightNext: [TreeNode]
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

查询数据

  // 搜索方法
    search(key) {
        // 检测类型
        let isNumKey = Object.prototype.toString;

        // 判断输入key值的类型
        if (isNumKey.call(key) !== '[object Number]') {
            throw new Error('key值非数值');
        }
        //获取头部指针
        let rootNode = this.#header;
        //传入递归搜索韩函数，接收返回结果
        return this.#recursiveSearch(rootNode, key);
    }

    // 递归搜索树节点
    #recursiveSearch(currentNode, key) {
        // 判断传入节点是否为空
        if (currentNode === null) {
            // 空返回false
            return false;
        } else if (currentNode.key === key) {
            //判断key值是否相等，相等返回对应value
            return currentNode.value;
        } else if (currentNode.key > key) {
            // 搜索key值小于当前树节点key，则将其左子节点传入递归继续查找
            return this.#recursiveSearch(currentNode.leftNext, key);
        } else {
            // 搜索key值大于当前树节点key，则将其右子节点传入递归继续查找
            return this.#recursiveSearch(currentNode.rightNext, key);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

和插入方法思想类似，不过是按照key值来确定

测试

console.log(tree.search(20));
//'树5'
1
2

更改值方法

 // 修改树数据
    alter(key, value) {
        // 检测类型
        let isNumKey = Object.prototype.toString;

        // 判断输入key值的类型
        if (isNumKey.call(key) !== '[object Number]') {
            throw new Error('key值非数值');
        }
        //获取头部指针
        let rootNode = this.#header;
        //传入递归搜索函数，接收返回结果
        return this.#recursiveAlter(rootNode, key, value);
    }

    // 递归搜索修改树节点
    #recursiveAlter(currentNode, key, value) {
        // 判断传入节点是否为空
        if (currentNode === null) {
            // 空返回false
            return -1;
        } else if (currentNode.key === key) {
            //判断key值是否相等，相等返回对应value
            currentNode.value = value;
            return 0;
        } else if (currentNode.key > key) {
            // 搜索key值小于当前树节点key，则将其左子节点传入递归继续查找
            return this.#recursiveAlter(currentNode.leftNext, key, value);
        } else {
            // 搜索key值大于当前树节点key，则将其右子节点传入递归继续查找
            return this.#recursiveAlter(currentNode.rightNext, key, value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

递归找到对应数据修改即可

获得最大最小数据

// 获取最大键的值
    get max() {
        // 根节点空值判断
        if (this.#header === null) return false;
        // 传入递归
        return this.#getMaxMin(this.#header, true);
    }

    // 获取最小键的值
    get min() {
        // 空值判断
        if (this.#header === null) return false;
        return this.#getMaxMin(this.#header, false);
    }

    // 递归查询最大最小键的值
    #getMaxMin(currentNode, isR) {
        // 判断向左(min)还是向右(max)查询
        if (isR) {
            // 判断当前树节点的右子节点是否为空，为空返回对应value
            if (currentNode.rightNext === null) {
                return currentNode.value;
            }
            // 否则继续向右子节点递归
            return this.#getMaxMin(currentNode.rightNext, true);
        } else {
            // 判断当前树节点的左子节点是否为空，为空返回对应value
            if (currentNode.leftNext === null) {
                return currentNode.value;
            }
            // 否则继续向左子节点递归
            return this.#getMaxMin(currentNode.leftNext, false);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

因为二叉搜索树中最大最小值因其特性分布在结构的最右和最左边，因此我们可以递归遍历根节点的最左侧子树，遍历到null时其叶节点即为目标最小节点，同理，右侧节点遍历即右侧子树叶子节点。代码中的isR形参决定遍历方向

测试

console.log('最大key值对应的数据\t' + tree.max);
console.log('最小key值对应的数据\t' + tree.min);
//
最大key值对应的数据	[object Object]
最小key值对应的数据	树115
1
2
3
4
5

先序遍历—根左右

// 先序遍历---（根左右）
    preOrderTraverse(callback) {
        // 调用递归
        this.#recursivePreOrderTraverse(this.#header, callback);
    }

    // 先序遍历的递归---callback == 回调函数，用于接收value
    #recursivePreOrderTraverse(currentNode, callback) {
        // 当前节点不为空
        if (currentNode !== null) {
            // 将value返回
            callback(currentNode.value);

            // 利用了函数调用栈

            // 继续查询左子树 --- 注意：当当前节点左子树遇到null时，会出现弹栈，然后查询当前节点右子树，
            // 若又遇到null，在弹栈，弹栈，执行栈当前函数结束，返回上一个执行块，然后继续查询
            this.#recursivePreOrderTraverse(currentNode.leftNext, callback);

            // 查询右子树
            this.#recursivePreOrderTraverse(currentNode.rightNext, callback);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

先序遍历树结构，将结果通过回调函数拿到，这个方法注意当当前节点左子树遇到null时，会出现弹栈，然后查询当前节点右子树，
若又遇到null，在弹栈，弹栈，执行栈当前函数结束，返回上一个执行块，然后继续查询

测试

let arr = []
tree.preOrderTraverse((value) => {
    arr.push(value);
})
console.log(arr);
[ '根节点', '子树1',  '最小', '树115', '修改', '树6', '123', '树4', '树5', '44', '树46', { name: 'andy' }]
1
2
3
4
5
6

中序遍历-左根右

// 中序遍历---（左根右）
    inOrderTraverse(callback) {
        // 调用递归
        this.#recursiveInOrderTraverse(this.#header, callback);
    }

    // 递归中序遍历
    #recursiveInOrderTraverse(currentNode, callback) {
        // 判断当前树节点是否为空
        if (currentNode !== null) {
            // 和先序遍历类似，需结合递归执行栈理解（压栈，出栈）

            // 遍历左子树节点
            this.#recursiveInOrderTraverse(currentNode.leftNext, callback);
            // 找到最左子节点后开始获取value
            callback(currentNode.value);
            // 遍历右子树节点
            this.#recursiveInOrderTraverse(currentNode.rightNext, callback);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

和先序类似，但是因为遍历机制的不同导致返回value的时机有所不同

测试

let arrIn = []
tree.inOrderTraverse((value) => {
    arrIn.push(value);
})
console.log(arrIn);
['树115', '最小', '子树1','树6', '123', '修改', '根节点', '树4', '树5', '44', '树46', { name: 'andy' }]
1
2
3
4
5
6

后序遍历—左右根

// 后序遍历
    postOrderTraverse(callback) {
        this.#recursivePostOrderTraverse(this.#header, callback);
    }

    // 后序遍历递归
    #recursivePostOrderTraverse(currentNode, callback) {
        // 判断当前树节点是否为空
        if (currentNode !== null) {
            // 和先序遍历类似，需结合递归执行栈理解（压栈，出栈）

            // 遍历左子树节点
            this.#recursivePostOrderTraverse(currentNode.leftNext, callback);

            // 遍历右子树节点
            this.#recursivePostOrderTraverse(currentNode.rightNext, callback);

            // 找到最左子节点后开始获取value
            callback(currentNode.value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

不同的遍历方式对应不同的代码结构

测试

let arrPo = []
tree.postOrderTraverse((value) => {
    arrPo.push(value);
})
console.log(arrPo);
[ '树115','最小','123','树6','修改','子树1',{ name: 'andy' }, '树46','44','树5','树4','根节点']
1
2
3
4
5
6

---

删除节点

这里要分三种情况

删除的节点没有子节点（叶子结点）

这种情况其实很简单，因为删除的只有可能是叶子结点后者是只有一个根节点的树，直接删除即可

删除的节点只有一个子节点

稍微复杂了一些，在删除节点时，我们需要使当前节点的父节点的对应方向指针指向删除节点的唯一子节点，还要注意根节点的情况

删除的节点有两个节点

最复杂的情况
// + 如果我们要删除的节点有两个子节点时，甚至子节点还有子节点，这种情况下我们需要从下面的子节点中找到一个节点来替换当前的节点
//
// +但是找到的这个节点有什么特征呢? 应该是当前节点下面所有节点中最接近当前节点的.
// - 要么比当前节点小一点点，要么比当前节点大-点点.
// 总结你最接近当前节点,你就可以用来替换当前的位置.
//
// + 这个节点怎么找呢?
// 比当前节点小一点点的节点 -定是当前节点左子树的最大值.
// 比当前节点大一点点的节点 -定是当前节点右子树的最小值.

前驱&后继
在二叉搜索树中， 这两个特别的节点有两个特别的名字
比当前节点小一点点的节点称为当前节点的前驱.
比当前节点大-点点的节点称为当前节点的后继.
也就是为了能够删除有两个子节点的当前节点,要么找到它的前驱，要么找到它的后继
所以接下来，我们先找到这样的节点(前驱或者后继都可以我这里以找后继为例)

删除含有两个子树的数据时，可以获得前驱节点或者后继节点中的一个，将其代替删除节点，不会违背二叉搜索树的特性。
注意:前驱节点不会有右子树节点，后继节点不会有左子树节点

删除图解

---

---

后继节点的使用方式和这类似，待会就使用后继节点解决连个子树节点的删除方法

代码 — 公有部分

// 删除指定树节点
    remove(key) {
        // 检测类型
        let isNumKey = Object.prototype.toString;

        // 删除节点的上一个节点
        let preNode = null,
            // 删除的是否是父节点的左节点
            isL = null;

        // 判断输入key值的类型
        if (isNumKey.call(key) !== '[object Number]') {
            throw new Error('key值非数值');
        }
        //获取头部指针
        let rootNode = this.#header;
        //传入递归搜索函数，接收返回结果
        return this.#recursiveRemove(rootNode, key, preNode, isL);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

递归部分

第一种情况

// 递归的删除方法
    #recursiveRemove(currentNode, key, preNode, isL) {
        // 判断传入节点是否为空
        if (currentNode === null) {
            // 空返回false
            return -1;
        } else if (currentNode.key === key) {
            // 找到删除的节点

            // 判断删除情况
            if (currentNode.leftNext === null && currentNode.rightNext === null) {
                // 删除叶子节点---判断叶子结点是父节点的左右那边的节点，更改对应指向即可

                // 删除根节点---且只有一个根节点
                if (currentNode === this.#header) {
                    this.#header = null;
                }
                // 非根节点
                if (isL) {//判断删除节点使父节点的哪一个指向---方便更改指向
                    preNode.leftNext = null;
                } else {
                    preNode.rightNext = null;
                }
            } else if (currentNode.leftNext !== null && currentNode.rightNext !== null) {
                // 删除元素有双子节点

            } else {
                // 删除元素有单子节点
            }
            return 0;
        } else if (currentNode.key > key) {
            isL = true;
            // 搜索key值小于当前树节点key，则将其左子节点传入递归继续查找
            return this.#recursiveRemove(currentNode.leftNext, key, currentNode, isL);
        } else {
            isL = false;
            // 搜索key值大于当前树节点key，则将其右子节点传入递归继续查找
            return this.#recursiveRemove(currentNode.rightNext, key, currentNode, isL);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

第二种情况

// 递归的删除方法
    #recursiveRemove(currentNode, key, preNode, isL) {
        // 判断传入节点是否为空
        if (currentNode === null) {
            // 空返回false
            return -1;
        } else if (currentNode.key === key) {
            // 找到删除的节点

            // 判断删除情况
            if (currentNode.leftNext === null && currentNode.rightNext === null) {
                
            } else if (currentNode.leftNext !== null && currentNode.rightNext !== null) {
               
            } else {
                // 删除元素有单子节点

                // 删除只有一条子树的根元素,(通过三目运算符判断删除元素的子节点的方向)
                if (currentNode === this.#header) {
                    this.#header = currentNode.leftNext === null ?
                        currentNode.rightNext : currentNode.leftNext;
                }

                // 判断删除节点是否是父节点的左子节点
                if (isL) {
                    // 是，则让父节点的左子节点指向删除节点的子节点(通过三目运算符判断删除元素的子节点的方向)
                    preNode.leftNext = currentNode.leftNext === null ?
                        currentNode.rightNext : currentNode.leftNext;
                } else {
                    // 不是，则让父节点的右子节点指向删除节点的子节点(通过三目运算符判断删除元素的子节点的方向)
                    preNode.rightNext = currentNode.leftNext === null ?
                        currentNode.rightNext : currentNode.leftNext;
                }
            }
            return 0;
        } else if (currentNode.key > key) {
            isL = true;
            // 搜索key值小于当前树节点key，则将其左子节点传入递归继续查找
            return this.#recursiveRemove(currentNode.leftNext, key, currentNode, isL);
        } else {
            isL = false;
            // 搜索key值大于当前树节点key，则将其右子节点传入递归继续查找
            return this.#recursiveRemove(currentNode.rightNext, key, currentNode, isL);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

第三种情况
获取到后继节点

    //获得后继节点---即从要删除的节点的右边开始查找最小的值
    #getSucceed(delNode) {
        // 后继节点
        let succeedNode = delNode,
            // 后继节点的上一级节点
            successPre = delNode,
            // 临时节点----向后遍历找到后继节点
            current = delNode.rightNext;

        while (current !== null) {
            // 获得后继节点的上一级节点---目的是将后继节点的上一级节点的left指向null或者后继节点的子树
            successPre = succeedNode;
            // 获得后继节点
            succeedNode = current;
            // 让临时节点始终沿着左子树遍历---直到遍历到null
            current = current.leftNext;
        }

        // 判断后继节点的父节点是不是删除节点的右节点
        if (succeedNode !== delNode.rightNext) {
            // 让当前后继节点的父节点的左子树指向指向后继节点的右指向
            //（当后继节点没有右节点时也会将null给后继节点父节点的左指向）
            // 后继节点不会有左子树指向
            successPre.leftNext = succeedNode.rightNext;
            // 当前后继节点的右指向替代原先删除元素的右指向
            succeedNode.rightNext = delNode.rightNext;
        }

        // 返回后继节点
        return succeedNode;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

注意，获得后继节点时，要利用后继节点的父节点，删除节点的右节点等

方法

  #recursiveRemove(currentNode, key, preNode, isL) {
        // 判断传入节点是否为空
        if (currentNode === null) {
            // 空返回false
            return -1;
        } else if (currentNode.key === key) {
            // 找到删除的节点

            // 判断删除情况
            if (currentNode.leftNext === null && currentNode.rightNext === null) {
                // 删除叶子节点---判断叶子结点是父节点的左右那边的节点，更改对应指向即可
            } else if (currentNode.leftNext !== null && currentNode.rightNext !== null) {
                // 删除元素有双子节点

                // 调用查找后继节点的方法
                let successNode = this.#getSucceed(currentNode);

                // 删除根节点---有两个根节点
                if (currentNode === this.#header) {
                    // 头部指向指向后继节点
                    this.#header = successNode;
                } else if (isL) {
                    // 当删除节点的父节点左子树指向删除节点
                    // 将父节点的左指向指向替换后的后继节点
                    preNode.leftNext = successNode;
                } else {
                    // 当删除节点的父节点右子树指向删除节点
                    // 将父节点的右指向指向替换后的后继节点
                    preNode.rightNext = successNode;
                }

                // 后继节点替代删除节点的左子树
                successNode.leftNext = currentNode.leftNext;
            } else {
                // 删除元素有单子节点
            }
            return 0;
        } else if (currentNode.key > key) {
            isL = true;
            // 搜索key值小于当前树节点key，则将其左子节点传入递归继续查找
            return this.#recursiveRemove(currentNode.leftNext, key, currentNode, isL);
        } else {
            isL = false;
            // 搜索key值大于当前树节点key，则将其右子节点传入递归继续查找
            return this.#recursiveRemove(currentNode.rightNext, key, currentNode, isL);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

注意指向问题

---

完整代码

/*实现二叉搜索树*/

/*
常见的二叉搜索树的属性方法
    属性
        header：指向根节点的指针
    方法
        insert(key, value)：向树中插入一个新的键和值
        search(key):在树中搜索对应key值的value;
        inOrderTraverse: 通过中序遍历方式遍历所有的节点
        preOrderTraverse: 通过先序遍历方式遍历所有节点
        postOrderTraverse: 通过后序遍历的方式遍历所有节点
        alter(key, value):修改对应key的value值
        remove(key): 移除对应key的值
        min: 返回树中最小的键的值
        max：返回树中最大的键的值
*/

// 创建实例树结构节点的类
class TreeNode {

    constructor(key, value) {
        // 索引值
        this.key = key;
        // value值
        this.value = value;
        // 树节点左指针
        this.leftNext = null;
        // 树节点右指针
        this.rightNext = null;
    }
}

// 创建树结构实现类
class MyTree {
    // 私有的头部指针---指向root节点
    #header = null;

    // 方法
    // 获取根节点
    get getMyTree() {
        return this.#header;
    }

    // 插入节点
    insert(key, value) {
        // 检测类型
        let isNumKey = Object.prototype.toString,
            // 新节点变量
            newTreeNode;

        // 判断输入key值的类型
        if (isNumKey.call(key) !== '[object Number]') {
            throw new Error('key值非数值');
        }

        // 创建新的树节点
        newTreeNode = new TreeNode(key, value);

        // 判断根节点是否有值
        if (this.#header === null) {
            // 有值将根节点指向指向新节点
            this.#header = newTreeNode;
        } else {
            // 没有则进入递归查找子树
            this.#recursiveInsert(this.#header, newTreeNode);
        }
    }

    // 递归插入节点
    #recursiveInsert(currentNode, newNode) {
        // 判断新增节点key是否小于当前节点
        if (currentNode.key > newNode.key) {
            // 小于则进入左分支树

            // 判断左子树是否值为空
            if (currentNode.leftNext === null) {
                // 为空则将新节点添加到这个位置
                currentNode.leftNext = newNode;
            } else {
                // 不为空进入下一次递归插入值
                this.#recursiveInsert(currentNode.leftNext, newNode);
            }

        } else if (currentNode.key < newNode.key) {
            // 大于进入右分支树

            // 判断右子树是否值为空
            if (currentNode.rightNext === null) {
                // 为空则将新节点添加到这个位置
                currentNode.rightNext = newNode;
            } else {
                // 不为空进入下一次递归插入值
                this.#recursiveInsert(currentNode.rightNext, newNode);
            }
        } else {
            throw new Error('key existing！');
        }
    }

    // 搜索方法
    search(key) {
        // 检测类型
        let isNumKey = Object.prototype.toString;

        // 判断输入key值的类型
        if (isNumKey.call(key) !== '[object Number]') {
            throw new Error('key值非数值');
        }
        //获取头部指针
        let rootNode = this.#header;
        //传入递归搜索韩函数，接收返回结果
        return this.#recursiveSearch(rootNode, key);
    }

    // 递归搜索树节点
    #recursiveSearch(currentNode, key) {
        // 判断传入节点是否为空
        if (currentNode === null) {
            // 空返回false
            return false;
        } else if (currentNode.key === key) {
            //判断key值是否相等，相等返回对应value
            return currentNode.value;
        } else if (currentNode.key > key) {
            // 搜索key值小于当前树节点key，则将其左子节点传入递归继续查找
            return this.#recursiveSearch(currentNode.leftNext, key);
        } else {
            // 搜索key值大于当前树节点key，则将其右子节点传入递归继续查找
            return this.#recursiveSearch(currentNode.rightNext, key);
        }
    }

    // 获取最大键的值
    get max() {
        // 根节点空值判断
        if (this.#header === null) return false;
        // 传入递归
        return this.#getMaxMin(this.#header, true);
    }

    // 获取最小键的值
    get min() {
        // 空值判断
        if (this.#header === null) return false;
        return this.#getMaxMin(this.#header, false);
    }

    // 递归查询最大最小键的值
    #getMaxMin(currentNode, isR) {
        // 判断向左(min)还是向右(max)查询
        if (isR) {
            // 判断当前树节点的右子节点是否为空，为空返回对应value
            if (currentNode.rightNext === null) {
                return currentNode.value;
            }
            // 否则继续向右子节点递归
            return this.#getMaxMin(currentNode.rightNext, true);
        } else {
            // 判断当前树节点的左子节点是否为空，为空返回对应value
            if (currentNode.leftNext === null) {
                return currentNode.value;
            }
            // 否则继续向左子节点递归
            return this.#getMaxMin(currentNode.leftNext, false);
        }
    }

    // 先序遍历---（根左右）
    preOrderTraverse(callback) {
        // 调用递归
        this.#recursivePreOrderTraverse(this.#header, callback);
    }

    // 先序遍历的递归---callback == 回调函数，用于接收value
    #recursivePreOrderTraverse(currentNode, callback) {
        // 当前节点不为空
        if (currentNode !== null) {
            // 将value返回
            callback(currentNode.value);

            // 利用了函数调用栈

            // 继续查询左子树 --- 注意：当当前节点左子树遇到null时，会出现弹栈，然后查询当前节点右子树，
            // 若又遇到null，在弹栈，弹栈，执行栈当前函数结束，返回上一个执行块，然后继续查询
            this.#recursivePreOrderTraverse(currentNode.leftNext, callback);

            // 查询右子树
            this.#recursivePreOrderTraverse(currentNode.rightNext, callback);
        }
    }

    // 中序遍历---（左根右）
    inOrderTraverse(callback) {
        // 调用递归
        this.#recursiveInOrderTraverse(this.#header, callback);
    }

    // 递归中序遍历
    #recursiveInOrderTraverse(currentNode, callback) {
        // 判断当前树节点是否为空
        if (currentNode !== null) {
            // 和先序遍历类似，需结合递归执行栈理解（压栈，出栈）

            // 遍历左子树节点
            this.#recursiveInOrderTraverse(currentNode.leftNext, callback);
            // 找到最左子节点后开始获取value
            callback(currentNode.value);
            // 遍历右子树节点
            this.#recursiveInOrderTraverse(currentNode.rightNext, callback);
        }
    }

    // 后序遍历
    postOrderTraverse(callback) {
        this.#recursivePostOrderTraverse(this.#header, callback);
    }

    // 后序遍历递归
    #recursivePostOrderTraverse(currentNode, callback) {
        // 判断当前树节点是否为空
        if (currentNode !== null) {
            // 和先序遍历类似，需结合递归执行栈理解（压栈，出栈）

            // 遍历左子树节点
            this.#recursivePostOrderTraverse(currentNode.leftNext, callback);

            // 遍历右子树节点
            this.#recursivePostOrderTraverse(currentNode.rightNext, callback);

            // 找到最左子节点后开始获取value
            callback(currentNode.value);
        }
    }

    // 修改树数据
    alter(key, value) {
        // 检测类型
        let isNumKey = Object.prototype.toString;

        // 判断输入key值的类型
        if (isNumKey.call(key) !== '[object Number]') {
            throw new Error('key值非数值');
        }
        //获取头部指针
        let rootNode = this.#header;
        //传入递归搜索函数，接收返回结果
        return this.#recursiveAlter(rootNode, key, value);
    }

    // 递归搜索修改树节点
    #recursiveAlter(currentNode, key, value) {
        // 判断传入节点是否为空
        if (currentNode === null) {
            // 空返回false
            return -1;
        } else if (currentNode.key === key) {
            //判断key值是否相等，相等返回对应value
            currentNode.value = value;
            return 0;
        } else if (currentNode.key > key) {
            // 搜索key值小于当前树节点key，则将其左子节点传入递归继续查找
            return this.#recursiveAlter(currentNode.leftNext, key, value);
        } else {
            // 搜索key值大于当前树节点key，则将其右子节点传入递归继续查找
            return this.#recursiveAlter(currentNode.rightNext, key, value);
        }
    }

    // 先找到要删除的节点，没有找到，不需要删除
    //  找到子节点
    //  - 删除叶子节点
    //  - 删除只有一个子节点的节点
    //  - 删除有两个子节点的节点

    // 删除指定树节点
    remove(key) {
        // 检测类型
        let isNumKey = Object.prototype.toString;

        // 删除节点的上一个节点
        let preNode = null,
            // 删除的是否是父节点的左节点
            isL = null;

        // 判断输入key值的类型
        if (isNumKey.call(key) !== '[object Number]') {
            throw new Error('key值非数值');
        }
        //获取头部指针
        let rootNode = this.#header;
        //传入递归搜索函数，接收返回结果
        return this.#recursiveRemove(rootNode, key, preNode, isL);
    }

    // 递归的删除方法
    #recursiveRemove(currentNode, key, preNode, isL) {
        // 判断传入节点是否为空
        if (currentNode === null) {
            // 空返回false
            return -1;
        } else if (currentNode.key === key) {
            // 找到删除的节点

            // 判断删除情况
            if (currentNode.leftNext === null && currentNode.rightNext === null) {
                // 删除叶子节点---判断叶子结点是父节点的左右那边的节点，更改对应指向即可

                // 删除根节点---且只有一个根节点
                if (currentNode === this.#header) {
                    this.#header = null;
                }
                // 非根节点
                if (isL) {
                    preNode.leftNext = null;
                } else {
                    preNode.rightNext = null;
                }
            } else if (currentNode.leftNext !== null && currentNode.rightNext !== null) {
                // 删除元素有双子节点

                // 调用查找后继节点的方法
                let successNode = this.#getSucceed(currentNode);

                // 删除根节点---有两个根节点
                if (currentNode === this.#header) {
                    // 头部指向指向后继节点
                    this.#header = successNode;
                } else if (isL) {
                    // 当删除节点的父节点左子树指向删除节点
                    // 将父节点的左指向指向替换后的后继节点
                    preNode.leftNext = successNode;
                } else {
                    // 当删除节点的父节点右子树指向删除节点
                    // 将父节点的右指向指向替换后的后继节点
                    preNode.rightNext = successNode;
                }

                // 后继节点替代删除节点的左子树
                successNode.leftNext = currentNode.leftNext;
            } else {
                // 删除元素有单子节点

                // 删除只有一条子树的根元素,(通过三目运算符判断删除元素的子节点的方向)
                if (currentNode === this.#header) {
                    this.#header = currentNode.leftNext === null ?
                        currentNode.rightNext : currentNode.leftNext;
                }

                // 判断删除节点是否是父节点的左子节点
                if (isL) {
                    // 是，则让父节点的左子节点指向删除节点的子节点(通过三目运算符判断删除元素的子节点的方向)
                    preNode.leftNext = currentNode.leftNext === null ?
                        currentNode.rightNext : currentNode.leftNext;
                } else {
                    // 不是，则让父节点的右子节点指向删除节点的子节点(通过三目运算符判断删除元素的子节点的方向)
                    preNode.rightNext = currentNode.leftNext === null ?
                        currentNode.rightNext : currentNode.leftNext;
                }
            }
            return 0;
        } else if (currentNode.key > key) {
            isL = true;
            // 搜索key值小于当前树节点key，则将其左子节点传入递归继续查找
            return this.#recursiveRemove(currentNode.leftNext, key, currentNode, isL);
        } else {
            isL = false;
            // 搜索key值大于当前树节点key，则将其右子节点传入递归继续查找
            return this.#recursiveRemove(currentNode.rightNext, key, currentNode, isL);
        }
    }


    // + 如果我们要删除的节点有两个子节点时，甚至子节点还有子节点，这种情况下我们需要从下面的子节点中找到一个节点来替换当前的节点
    // +但是找到的这个节点有什么特征呢? 应该是当前节点下面所有节点中最接近当前节点的.
    // - 要么比当前节点小一点点，要么比当前节点大-点点.
    // 总结你最接近当前节点,你就可以用来替换当前的位置.
    // + 这个节点怎么找呢?
    //  比当前节点小一点点的节点 -定是当前节点左子树的最大值.
    //  比当前节点大一点点的节点 -定是当前节点右子树的最小值.
    // + 前驱&后继
    //  在二叉搜索树中， 这两个特别的节点有两个特别的名字
    //  比当前节点小一点点的节点称为当前节点的前驱.
    //  比当前节点大-点点的节点称为当前节点的后继.
    // 也就是为了能够删除有两个子节点的当前节点,要么找到它的前驱，要么找到它的后继
    // 所以接下来，我们先找到这样的节点(前驱或者后继都可以我这里以找后继为例)


    //获得后继节点---即从要删除的节点的右边开始查找最小的值
    #getSucceed(delNode) {
        // 后继节点
        let succeedNode = delNode,
            // 后继节点的上一级节点
            successPre = delNode,
            // 临时节点----向后遍历找到后继节点
            current = delNode.rightNext;

        while (current !== null) {
            // 获得后继节点的上一级节点---目的是将后继节点的上一级节点的left指向null或者后继节点的子树
            successPre = succeedNode;
            // 获得后继节点
            succeedNode = current;
            // 让临时节点始终沿着左子树遍历---直到遍历到null
            current = current.leftNext;
        }

        // 判断后继节点的父节点是不是删除节点的右节点
        if (succeedNode !== delNode.rightNext) {
            // 让当前后继节点的父节点的左子树指向指向后继节点的右指向（当后继节点没有右节点时也会将null给后继节点父节点的左指向）
            // 后继节点不会有左子树指向
            successPre.leftNext = succeedNode.rightNext;
            // 当前后继节点的右指向替代原先删除元素的右指向
            succeedNode.rightNext = delNode.rightNext;
        }

        // 返回后继节点
        return succeedNode;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420

测试

// 创建树结构
let tree = new MyTree();

tree.insert(10, '根节点');
tree.insert(1, '子树1');
tree.insert(8, '树3');
tree.insert(14, '树4');
tree.insert(-2, '最小');
tree.insert(20, '树5');
tree.insert(3, '树6');
tree.insert(24, '44');
tree.insert(-10, '树115');
tree.insert(32, '树46');
tree.insert(4, '123');
tree.insert(44, {name: 'andy'});

// console.log(tree.getMyTree);
tree.alter(8, '修改');

console.log('查询------------------');
console.log(tree.search(20));

console.log('最值------------------');
console.log('最大key值对应的数据\t' + tree.max);
console.log('最小key值对应的数据\t' + tree.min);


console.log('先序------------------');
let arr = []
tree.preOrderTraverse((value) => {
    arr.push(value);
})
console.log(arr);

console.log('中序------------------');
let arrIn = []
tree.inOrderTraverse((value) => {
    arrIn.push(value);
})
console.log(arrIn);

console.log('后序------------------');
let arrPo = []
tree.postOrderTraverse((value) => {
    arrPo.push(value);
})
console.log(arrPo);
console.log(tree.search(1));
console.log(tree.getMyTree);
// console.log('删除-------------------');
tree.remove(1);
console.log(tree.getMyTree);

//
查询------------------
树5
最值------------------
最大key值对应的数据	[object Object]
最小key值对应的数据	树115
先序------------------
[
  '根节点', '子树1',
  '最小',   '树115',
  '修改',   '树6',
  '123',    '树4',
  '树5',    '44',
  '树46',   { name: 'andy' }
]
中序------------------
[
  '树115',  '最小',
  '子树1',  '树6',
  '123',    '修改',
  '根节点', '树4',
  '树5',    '44',
  '树46',   { name: 'andy' }
]
后序------------------
[
  '树115',          '最小',
  '123',            '树6',
  '修改',           '子树1',
  { name: 'andy' }, '树46',
  '44',             '树5',
  '树4',            '根节点'
]
子树1
TreeNode {
  key: 10,
  value: '根节点',
  leftNext: TreeNode {
    key: 1,
    value: '子树1',
    leftNext: TreeNode {
      key: -2,
      value: '最小',
      leftNext: [TreeNode],
      rightNext: null
    },
    rightNext: TreeNode {
      key: 8,
      value: '修改',
      leftNext: [TreeNode],
      rightNext: null
    }
  },
  rightNext: TreeNode {
    key: 14,
    value: '树4',
    leftNext: null,
    rightNext: TreeNode {
      key: 20,
      value: '树5',
      leftNext: null,
      rightNext: [TreeNode]
    }
  }
}
TreeNode {
  key: 10,
  value: '根节点',
  leftNext: TreeNode {
    key: 3,
    value: '树6',
    leftNext: TreeNode {
      key: -2,
      value: '最小',
      leftNext: [TreeNode],
      rightNext: null
    },
    rightNext: TreeNode {
      key: 8,
      value: '修改',
      leftNext: [TreeNode],
      rightNext: null
    }
  },
  rightNext: TreeNode {
    key: 14,
    value: '树4',
    leftNext: null,
    rightNext: TreeNode {
      key: 20,
      value: '树5',
      leftNext: null,
      rightNext: [TreeNode]
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150