LoveCatDog
Home
Archives
Tags
Categories
Link
MessagesBoard
About
List
avatar
文章
25
标签
16
分类
1
Home
Archives
Tags
Categories
Link
MessagesBoard
About
List
目录
  1. 1. 二叉排序树
  2. 2. 二叉树的中序遍历
  3. 3. 二叉树的前序遍历
  4. 4. 二叉树的后序遍历
  5. 5. 查找最小值
  6. 6. 查找最大值
  7. 7. 查找任意某个值
  8. 8. 删除叶子节点
  9. 9. 删除中间节点
  10. 10. 总结
  11. 11. 友情链接分享
javaScript实现二叉树算法
字数总计:5.5k|阅读时长: 21 分钟
|阅读量:|评论数:

最近正在看慕课网的《Javascript实现二叉树算法》课程，现在把学习的东西记录下来。

什么是二叉树？简单来说，二叉树是一种具有层级特性的数据结构，一棵树包含多个节点。节点自身含有一个属性，就是他所代表的数值。
排序二叉树具有以下特征：

  1. 如果他的左子树上不为空，则他的左子树上所有节点的值都小于根节点上的值；
  2. 如果他的右子树上不为空，则他的右子树上所有节点的值都小于根节点上的值；
  3. 他的左、右子树也是二叉排序树；
  4. 没有完全相等的两个节点；

二叉排序树

代码实现

javascript
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
function BinaryTree() {
            var Node = function (key) {
                this.key = key; //key表示的是节点node的值
                this.left = null; //节点的左箭头
                this.right = null; //节点的右箭头
            };
            var root = null; //初始化根节点为null
            /**
             * node：老节点
             * newNode：新节点
             **/
            var insertNode = function (node, newNode) {
                if (newNode.key < node.key) { //如果新节点的值小于老节点的值,那么新节点为老节点的左边，否则在右边
                    if (node.left === null) { //如果老节点没有左孩子的话，新节点为老节点的左孩子
                        node.left = newNode;
                    } else {
                        insertNode(node.left, newNode) //将该节点的左孩子 和新节点对比 进行递归
                    }

                } else {
                    if (node.right === null) { //如果老节点的右孩子为空，则插入新节点，否则不为空的话就继续递归
                        node.right = newNode;
                    } else {
                        insertNode(node.right, newNode)
                    }
                }
            }

            this.insert = function (key) {
                var newNode = new Node(key); //创建节点对象
                if (root === null) { //如果值为空则给它作为根节点
                    root = newNode;
                } else {
                    insertNode(root, newNode); //否则根据节点的特性进行插入
                }
            }
        }


        var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]; //创建一个包含节点的数组
        var binaryTree = new BinaryTree(); //创建一个二叉树对象
        nodes.forEach(function (key) {
            binaryTree.insert(key)
        })

二叉树的中序遍历

从根节点开始，如果存在左子树就开始遍历左子树，然后再遍历右子树，最后输出根节点的值。遍历左、右子树时也是先遍历左子树，然后遍历右子树，最少输出改接点，如此循环。

  • 输入顺序： 左节点—> 当前节点 —> 右节点

代码实现

javascript
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
function BinaryTree() {
         var Node = function (key) {
             this.key = key; //key表示的是节点node的值
             this.left = null; //节点的左箭头
             this.right = null; //节点的右箭头
         };
         var root = null; //初始化根节点为null
         /**
          * node：老节点
          * newNode：新节点
          **/
         var insertNode = function (node, newNode) {
             if (newNode.key < node.key) { //如果新节点的值小于老节点的值,那么新节点为老节点的左边，否则在右边
                 if (node.left === null) { //如果老节点没有左孩子的话，新节点为老节点的左孩子
                     node.left = newNode;
                 } else {
                     insertNode(node.left, newNode) //将该节点的左孩子 和新节点对比 进行递归
                 }

             } else {
                 if (node.right === null) { //如果老节点的右孩子为空，则插入新节点，否则不为空的话就继续递归
                     node.right = newNode;
                 } else {
                     insertNode(node.right, newNode)
                 }
             }
         }

         this.insert = function (key) {
             var newNode = new Node(key); //创建节点对象
             if (root === null) { //如果值为空则给它作为根节点
                 root = newNode;
             } else {
                 insertNode(root, newNode); //否则根据节点的特性进行插入
             }
         };

         var inOrderTraverseNode = function (node, callback) {
             //node :二叉树的节点对象  callback：回调对象
             if (node !== null) { //如果当前节点的值为非空的话，
                 inOrderTraverseNode(node.left, callback); //就去访问左孩子
                 callback(node.key); //再访问当前节点，并将当前节点的key值回调出去
                 inOrderTraverseNode(node.right, callback); //最后访问节点的右孩子

             }

         }
         //中序遍历（升序）
         this.inOrderTraverse = function (callback) {
             //callback当输入某个节点的值传入到回调函数中
             inOrderTraverseNode(root, callback)
         }
     }


     var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]; //创建一个包含节点的数组
     var binaryTree = new BinaryTree(); //创建一个二叉树对象
     nodes.forEach(function (key) {
         binaryTree.insert(key)
     })
     var callback = function (key) {
         console.log('中序遍历接口', key)
     }
     binaryTree.inOrderTraverse(callback);

打印出来的结果

二叉树的前序遍历

从根节点开始，先输出当前节点，如果存在左子树就开始遍历左子树，然后再遍历右子树。遍历左、右子树的规则同上。

  • 输入顺序： 当前节点 —> 左节点—>右节点

代码实现

javascript
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
function BinaryTree() {
            var Node = function (key) {
                this.key = key; //key表示的是节点node的值
                this.left = null; //节点的左箭头
                this.right = null; //节点的右箭头
            };
            var root = null; //初始化根节点为null
            /**
             * node：老节点
             * newNode：新节点
             **/
            var insertNode = function (node, newNode) {
                if (newNode.key < node.key) { //如果新节点的值小于老节点的值,那么新节点为老节点的左边，否则在右边
                    if (node.left === null) { //如果老节点没有左孩子的话，新节点为老节点的左孩子
                        node.left = newNode;
                    } else {
                        insertNode(node.left, newNode) //将该节点的左孩子 和新节点对比 进行递归
                    }

                } else {
                    if (node.right === null) { //如果老节点的右孩子为空，则插入新节点，否则不为空的话就继续递归
                        node.right = newNode;
                    } else {
                        insertNode(node.right, newNode)
                    }
                }
            }

            this.insert = function (key) {
                var newNode = new Node(key); //创建节点对象
                if (root === null) { //如果值为空则给它作为根节点
                    root = newNode;
                } else {
                    insertNode(root, newNode); //否则根据节点的特性进行插入
                }
            };

            var preOrderTraverseNode = function (node, callback) {
                //node :二叉树的节点对象  callback：回调对象
                if (node !== null) { //如果当前节点的值为非空的话，
                    //步骤： 当前节点 --> 左节点 --> 右节点
                    callback(node.key); //访问当前节点，并将当前节点的key值回调出去
                    preOrderTraverseNode(node.left, callback); //然后访问节点的左孩子
                    preOrderTraverseNode(node.right, callback); //最后访问节点的右孩子

                }
            }

            //前序遍历（遍历二叉树效率最高）
            this.preOrderTraverse = function (callback) {
                //实现算法步骤：先访问二叉树的根节点，callback处理节点的数值
                preOrderTraverseNode(root, callback)
            }
        }


        var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]; //创建一个包含节点的数组
        var binaryTree = new BinaryTree(); //创建一个二叉树对象
        nodes.forEach(function (key) {
            binaryTree.insert(key)
        })
        var callback = function (key) {
            console.log('前序遍历接口', key)
        }
     
        binaryTree.preOrderTraverse(callback);

打印出来的结果

二叉树的后序遍历

  • 输入顺序： 左节点—>右节点 当前节点 —>
  • 应用场景：运用于文件系统和操作系统的遍历

代码实现：

javascript
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
function BinaryTree() {
           var Node = function (key) {
               this.key = key; //key表示的是节点node的值
               this.left = null; //节点的左箭头
               this.right = null; //节点的右箭头
           };
           var root = null; //初始化根节点为null
           /**
            * node：老节点
            * newNode：新节点
            **/
           var insertNode = function (node, newNode) {
               if (newNode.key < node.key) { //如果新节点的值小于老节点的值,那么新节点为老节点的左边，否则在右边
                   if (node.left === null) { //如果老节点没有左孩子的话，新节点为老节点的左孩子
                       node.left = newNode;
                   } else {
                       insertNode(node.left, newNode) //将该节点的左孩子 和新节点对比 进行递归
                   }

               } else {
                   if (node.right === null) { //如果老节点的右孩子为空，则插入新节点，否则不为空的话就继续递归
                       node.right = newNode;
                   } else {
                       insertNode(node.right, newNode)
                   }
               }
           }

           this.insert = function (key) {
               var newNode = new Node(key); //创建节点对象
               if (root === null) { //如果值为空则给它作为根节点
                   root = newNode;
               } else {
                   insertNode(root, newNode); //否则根据节点的特性进行插入
               }
           };




           var nextOrderTraverseNode = function (node, callback) {
               //node :二叉树的节点对象  callback：回调对象
               if (node !== null) { //如果当前节点的值为非空的话，
                   //步骤： 左节点 --> 右节点 --> 当前节点
                   preOrderTraverseNode(node.left, callback); //访问节点的左孩子
                   preOrderTraverseNode(node.right, callback); //然后访问节点的右孩子
                   callback(node.key); //最后当前节点，并将当前节点的key值回调出去

               }
           }

           //后序遍历（主要应用于：文件系统和操作系统）
           this.nextOrderTraverse = function (callback) {
               nextOrderTraverseNode(root, callback)
           }
       }


       var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]; //创建一个包含节点的数组
       var binaryTree = new BinaryTree(); //创建一个二叉树对象
       nodes.forEach(function (key) {
           binaryTree.insert(key)
       })
       var callback = function (key) {
           console.log('后续遍历接口', key)
       }

       binaryTree.nextOrderTraverse(callback); //后序遍历

打印出来的结果

查找最小值

javascript
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
function BinaryTree() {
          var Node = function (key) {
              this.key = key; //key表示的是节点node的值
              this.left = null; //节点的左箭头
              this.right = null; //节点的右箭头
          };
          var root = null; //初始化根节点为null
          /**
           * node：老节点
           * newNode：新节点
           **/
          var insertNode = function (node, newNode) {
              if (newNode.key < node.key) { //如果新节点的值小于老节点的值,那么新节点为老节点的左边，否则在右边
                  if (node.left === null) { //如果老节点没有左孩子的话，新节点为老节点的左孩子
                      node.left = newNode;
                  } else {
                      insertNode(node.left, newNode) //将该节点的左孩子 和新节点对比 进行递归
                  }

              } else {
                  if (node.right === null) { //如果老节点的右孩子为空，则插入新节点，否则不为空的话就继续递归
                      node.right = newNode;
                  } else {
                      insertNode(node.right, newNode)
                  }
              }
          }

          this.insert = function (key) {
              var newNode = new Node(key); //创建节点对象
              if (root === null) { //如果值为空则给它作为根节点
                  root = newNode;
              } else {
                  insertNode(root, newNode); //否则根据节点的特性进行插入
              }
          };


          //查找最小二叉树的值
          var minNode = function (node) {
              if (node) {
                  while (node && node.left !== null) {

                      node = node.left
                  }
                  return node.key //返回最小值
              }
              return null
          }

          this.min = function () {
              return minNode(root)
          }

      }


      var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]; //创建一个包含节点的数组
      var binaryTree = new BinaryTree(); //创建一个二叉树对象
      nodes.forEach(function (key) {
          binaryTree.insert(key)
      })
      
      console.log('查找最小的二叉树', binaryTree.min())

打印出来的结果

查找最大值

javascript
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
function BinaryTree() {
           var Node = function (key) {
               this.key = key; //key表示的是节点node的值
               this.left = null; //节点的左箭头
               this.right = null; //节点的右箭头
           };
           var root = null; //初始化根节点为null
           /**
            * node：老节点
            * newNode：新节点
            **/
           var insertNode = function (node, newNode) {
               if (newNode.key < node.key) { //如果新节点的值小于老节点的值,那么新节点为老节点的左边，否则在右边
                   if (node.left === null) { //如果老节点没有左孩子的话，新节点为老节点的左孩子
                       node.left = newNode;
                   } else {
                       insertNode(node.left, newNode) //将该节点的左孩子 和新节点对比 进行递归
                   }

               } else {
                   if (node.right === null) { //如果老节点的右孩子为空，则插入新节点，否则不为空的话就继续递归
                       node.right = newNode;
                   } else {
                       insertNode(node.right, newNode)
                   }
               }
           }

           this.insert = function (key) {
               var newNode = new Node(key); //创建节点对象
               if (root === null) { //如果值为空则给它作为根节点
                   root = newNode;
               } else {
                   insertNode(root, newNode); //否则根据节点的特性进行插入
               }
           };


           //查找最大二叉树的值
           var maxNode = function (node) {
               if (node) {
                   while (node && node.right !== null) {

                       node = node.right
                   }
                   return node.key //返回最大值
               }
               return null
           }

           this.max = function () {
               return maxNode(root)
           }

       }


       var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]; //创建一个包含节点的数组
       var binaryTree = new BinaryTree(); //创建一个二叉树对象
       nodes.forEach(function (key) {
           binaryTree.insert(key)
       })
       console.log('查找最大的二叉树', binaryTree.max())

打印出来的结果

查找任意某个值

javascript
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
function BinaryTree() {
           var Node = function (key) {
               this.key = key; //key表示的是节点node的值
               this.left = null; //节点的左箭头
               this.right = null; //节点的右箭头
           };
           var root = null; //初始化根节点为null
           /**
            * node：老节点
            * newNode：新节点
            **/
           var insertNode = function (node, newNode) {
               if (newNode.key < node.key) { //如果新节点的值小于老节点的值,那么新节点为老节点的左边，否则在右边
                   if (node.left === null) { //如果老节点没有左孩子的话，新节点为老节点的左孩子
                       node.left = newNode;
                   } else {
                       insertNode(node.left, newNode) //将该节点的左孩子 和新节点对比 进行递归
                   }

               } else {
                   if (node.right === null) { //如果老节点的右孩子为空，则插入新节点，否则不为空的话就继续递归
                       node.right = newNode;
                   } else {
                       insertNode(node.right, newNode)
                   }
               }
           }

           this.insert = function (key) {
               var newNode = new Node(key); //创建节点对象
               if (root === null) { //如果值为空则给它作为根节点
                   root = newNode;
               } else {
                   insertNode(root, newNode); //否则根据节点的特性进行插入
               }
           };


           //查找二叉树中任意的值是否存在
           var seacrhNode = function (newNode, node) {
               if (node === null) { //先判断当前节点是否存在
                   return false
               }

               if (newNode === node.key) {
                   return newNode //当前节点的值与查询的值相等的话就返回出去
               } else if (newNode < node.key) {
                   return seacrhNode(newNode, node.left)
               } else if (newNode > node.key) {
                   return seacrhNode(newNode, node.right)
               } else {
                   return true
               }
           }
           this.search = function (newNode) {
               // newNode  ：要查询的值
               //root ：根节点
               return seacrhNode(newNode, root)
           }

       }


       var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]; //创建一个包含节点的数组
       var binaryTree = new BinaryTree(); //创建一个二叉树对象
       nodes.forEach(function (key) {
           binaryTree.insert(key)
       })
       const value = 7 //输入要查找的任意某个值
       console.log('查找二叉树中任意指定值', binaryTree.search(value) ? 'key ' + value + ' is found' : " key " + value +
           " is noFound")

打印出来的结果

删除叶子节点

javascript
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
function BinaryTree() {
           var Node = function (key) {
               this.key = key; //key表示的是节点node的值
               this.left = null; //节点的左箭头
               this.right = null; //节点的右箭头
           };
           var root = null; //初始化根节点为null
           /**
            * node：老节点
            * newNode：新节点
            **/
           var insertNode = function (node, newNode) {
               if (newNode.key < node.key) { //如果新节点的值小于老节点的值,那么新节点为老节点的左边，否则在右边
                   if (node.left === null) { //如果老节点没有左孩子的话，新节点为老节点的左孩子
                       node.left = newNode;
                   } else {
                       insertNode(node.left, newNode) //将该节点的左孩子 和新节点对比 进行递归
                   }

               } else {
                   if (node.right === null) { //如果老节点的右孩子为空，则插入新节点，否则不为空的话就继续递归
                       node.right = newNode;
                   } else {
                       insertNode(node.right, newNode)
                   }
               }
           }

           this.insert = function (key) {
               var newNode = new Node(key); //创建节点对象
               if (root === null) { //如果值为空则给它作为根节点
                   root = newNode;
               } else {
                   insertNode(root, newNode); //否则根据节点的特性进行插入
               }
           };

           //删除叶子节点
           var removeNode = function (node, key) {
               if (node === null) {
                   return false
               }

               if (key < node.key) {
                   node.left = removeNode(node.left, key)
                   return node
               } else if (key > node.key) {
                   node.right = removeNode(node.right, key)
                   return node
               } else {
                   if (node.left === null && node.right === null) { //叶子节点的话直接删除
                       node = null
                       return node
                   }
               }
           }

           //删除二叉树中的叶子节
           this.remove = function (key) {
               removeNode(root, key)
           }
       }

       var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]; //创建一个包含节点的数组
       var binaryTree = new BinaryTree(); //创建一个二叉树对象
       nodes.forEach(function (key) {
           binaryTree.insert(key)
       })
       binaryTree.remove(1); //删除叶子节点

删除中间节点

javascript
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
function BinaryTree() {
           var Node = function (key) {
               this.key = key; //key表示的是节点node的值
               this.left = null; //节点的左箭头
               this.right = null; //节点的右箭头
           };
           var root = null; //初始化根节点为null
           /**
            * node：老节点
            * newNode：新节点
            **/
           var insertNode = function (node, newNode) {
               if (newNode.key < node.key) { //如果新节点的值小于老节点的值,那么新节点为老节点的左边，否则在右边
                   if (node.left === null) { //如果老节点没有左孩子的话，新节点为老节点的左孩子
                       node.left = newNode;
                   } else {
                       insertNode(node.left, newNode) //将该节点的左孩子 和新节点对比 进行递归
                   }

               } else {
                   if (node.right === null) { //如果老节点的右孩子为空，则插入新节点，否则不为空的话就继续递归
                       node.right = newNode;
                   } else {
                       insertNode(node.right, newNode)
                   }
               }
           }

           this.insert = function (key) {
               var newNode = new Node(key); //创建节点对象
               if (root === null) { //如果值为空则给它作为根节点
                   root = newNode;
               } else {
                   insertNode(root, newNode); //否则根据节点的特性进行插入
               }
           };


           //删除叶子节点
           var removeNode = function (node, key) {
               if (node === null) {
                   return false
               }

               if (key < node.key) {
                   node.left = removeNode(node.left, key)
                   return node
               } else if (key > node.key) {
                   node.right = removeNode(node.right, key)
                   return node
               } else {
                   /**删除叶子节点**/
                   if (node.left === null && node.right === null) { //叶子节点的话直接删除
                       node = null
                       return node
                   }
                   /**删除中间节点（左节点为空）**/
                   if (node.left === null) { //如果左孩子为空，当前节点只有右孩子，当前节点变为右孩子值
                       node = node.right
                       return node;
                   }
                   /**删除中间节点（右节点为空）**/
                   if (node.right === null) { //如果右孩子为空，当前节点只有左孩子，当前节点变为左孩子值
                       node = node.left
                       return node;
                   }

                   /**删除中间节点（左右节点都存在值）**/

                   var aux = findMinNode(node.rigth); //找到当前节点的右节点的最小节点值
                   node.key = aux.key; // 当前的节点变成为（要删除节点的右节点的最小节点值）
                   node.right = removeNode(node.right, aux.key); //删除（删除节点的右节点的最小节点值）
               }
           }



           //删除二叉树中的叶子节
           this.remove = function (key) {
               removeNode(root, key)
           }

       }
       var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]; //创建一个包含节点的数组
       var binaryTree = new BinaryTree(); //创建一个二叉树对象
       nodes.forEach(function (key) {
           binaryTree.insert(key)
       })
       var callback = function (key) {
           console.log('中序遍历接口', key)
       }
       binaryTree.remove(3); //删除中间节点

总结

javascript
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
function BinaryTree() {
            var Node = function (key) {
                this.key = key; //key表示的是节点node的值
                this.left = null; //节点的左箭头
                this.right = null; //节点的右箭头
            };
            var root = null; //初始化根节点为null
            /**
             * node：老节点
             * newNode：新节点
             **/
            var insertNode = function (node, newNode) {
                if (newNode.key < node.key) { //如果新节点的值小于老节点的值,那么新节点为老节点的左边，否则在右边
                    if (node.left === null) { //如果老节点没有左孩子的话，新节点为老节点的左孩子
                        node.left = newNode;
                    } else {
                        insertNode(node.left, newNode) //将该节点的左孩子 和新节点对比 进行递归
                    }

                } else {
                    if (node.right === null) { //如果老节点的右孩子为空，则插入新节点，否则不为空的话就继续递归
                        node.right = newNode;
                    } else {
                        insertNode(node.right, newNode)
                    }
                }
            }

            this.insert = function (key) {
                var newNode = new Node(key); //创建节点对象
                if (root === null) { //如果值为空则给它作为根节点
                    root = newNode;
                } else {
                    insertNode(root, newNode); //否则根据节点的特性进行插入
                }
            };

            var inOrderTraverseNode = function (node, callback) {
                //node :二叉树的节点对象  callback：回调对象
                if (node !== null) { //如果当前节点的值为非空的话，
                    //步骤：左节点-->  当前节点  --> 右节点
                    inOrderTraverseNode(node.left, callback); //就去访问左孩子
                    callback(node.key); //再访问当前节点，并将当前节点的key值回调出去
                    inOrderTraverseNode(node.right, callback); //最后访问节点的右孩子

                }

            }
            var preOrderTraverseNode = function (node, callback) {
                //node :二叉树的节点对象  callback：回调对象
                if (node !== null) { //如果当前节点的值为非空的话，
                    //步骤： 当前节点 --> 左节点 --> 右节点
                    callback(node.key); //访问当前节点，并将当前节点的key值回调出去
                    preOrderTraverseNode(node.left, callback); //然后访问节点的左孩子
                    preOrderTraverseNode(node.right, callback); //最后访问节点的右孩子

                }
            }


            var nextOrderTraverseNode = function (node, callback) {
                //node :二叉树的节点对象  callback：回调对象
                if (node !== null) { //如果当前节点的值为非空的话，
                    //步骤： 左节点 --> 右节点 --> 当前节点
                    preOrderTraverseNode(node.left, callback); //访问节点的左孩子
                    preOrderTraverseNode(node.right, callback); //然后访问节点的右孩子
                    callback(node.key); //最后当前节点，并将当前节点的key值回调出去

                }
            }
            //中序遍历（升序）
            this.inOrderTraverse = function (callback) {
                //callback当输入某个节点的值传入到回调函数中
                inOrderTraverseNode(root, callback)
            }


            //前序遍历（遍历二叉树效率最高）
            this.preOrderTraverse = function (callback) {
                //实现算法步骤：先访问二叉树的根节点，callback处理节点的数值
                preOrderTraverseNode(root, callback)
            }
            //后序遍历（主要应用于：文件系统和操作系统）
            this.nextOrderTraverse = function (callback) {
                nextOrderTraverseNode(root, callback)
            }
            //查找最小二叉树的值
            var minNode = function (node) {
                if (node) {
                    while (node && node.left !== null) {

                        node = node.left
                    }
                    return node.key //返回最小值
                }
                return null
            }

            this.min = function () {
                return minNode(root)
            }

            //查找最大二叉树的值
            var maxNode = function (node) {
                if (node) {
                    while (node && node.right !== null) {

                        node = node.right
                    }
                    return node.key //返回最大值
                }
                return null
            }

            this.max = function () {
                return maxNode(root)
            }

            //查找二叉树中任意的值是否存在
            var seacrhNode = function (newNode, node) {
                if (node === null) { //先判断当前节点是否存在
                    return false
                }

                if (newNode === node.key) {
                    return newNode //当前节点的值与查询的值相等的话就返回出去
                } else if (newNode < node.key) {
                    return seacrhNode(newNode, node.left)
                } else if (newNode > node.key) {
                    return seacrhNode(newNode, node.right)
                } else {
                    return true
                }
            }
            //查找某个节点的最小节点值
            var findMinNode = function (node) {
                if (node) {
                    while (node && node.left !== null) {
                        node = node.left
                    }
                    return node
                }
            }
            //删除叶子节点
            var removeNode = function (node, key) {
                if (node === null) {
                    return false
                }

                if (key < node.key) {
                    node.left = removeNode(node.left, key)
                    return node
                } else if (key > node.key) {
                    node.right = removeNode(node.right, key)
                    return node
                } else {
                    /**删除叶子节点**/
                    if (node.left === null && node.right === null) { //叶子节点的话直接删除
                        node = null
                        return node
                    }
                    /**删除中间节点（左节点为空）**/
                    if (node.left === null) { //如果左孩子为空，当前节点只有右孩子，当前节点变为右孩子值
                        node = node.right
                        return node;
                    }
                    /**删除中间节点（右节点为空）**/
                    if (node.right === null) { //如果右孩子为空，当前节点只有左孩子，当前节点变为左孩子值
                        node = node.left
                        return node;
                    }

                    /**删除中间节点（左右节点都存在值）**/

                    var aux = findMinNode(node.rigth); //找到当前节点的右节点的最小节点值
                    node.key = aux.key; // 当前的节点变成为（要删除节点的右节点的最小节点值）
                    node.right = removeNode(node.right, aux.key); //删除（删除节点的右节点的最小节点值）
                }
            }


            //查找二叉树中任意值
            this.search = function (newNode) {
                // newNode  ：要查询的值
                //root ：根节点
                return seacrhNode(newNode, root)
            }
            //删除二叉树中的叶子节
            this.remove = function (key) {
                removeNode(root, key)
            }

        }


        var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]; //创建一个包含节点的数组
        var binaryTree = new BinaryTree(); //创建一个二叉树对象
        nodes.forEach(function (key) {
            binaryTree.insert(key)
        })
        var callback = function (key) {
            console.log('中序遍历接口', key)
        }

        // console.log('查找最小的二叉树', binaryTree.min())
        // console.log('查找最大的二叉树', binaryTree.max())
        // const value = 7
        // console.log('查找二叉树中任意指定值', binaryTree.search(value) ? 'key ' + value + ' is found' : " key " + value +
        //     " is noFound")


        // binaryTree.inOrderTraverse(callback);//中序遍历
        // binaryTree.preOrderTraverseNode(callback);//前序遍历
        // binaryTree.nextOrderTraverseNode(callback); //后序遍历
        // binaryTree.remove(1); //
        binaryTree.remove(3); //删除中间节点

友情链接分享

什么是红黑树

红黑树就是一种平衡的二叉查找树，说他平衡的意思是他不会变成“瘸子”，左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外，还具体下列的特性：

  1. 节点是红色或者黑色

  2. 根节点是黑色

  3. 每个叶子的节点都是黑色的空节点（NULL）

  4. 每个红色节点的两个子节点都是黑色的。

  5. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

文章作者: 会吃鱼的猫
文章链接: https://lovecatdog.github.io/2020/04/23/javaScript%E5%AE%9E%E7%8E%B0%E4%BA%8C%E5%8F%89%E6%A0%91%E7%AE%97%E6%B3%95/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LoveCatDog！
javascript
打赏
  • 微信
    微信
  • 支付宝
    支付宝
相关推荐
2020-04-23
ES6-map、filter、find、findIndex讲解
2020-04-23
js手写日历
2020-04-23
javascript 中五种实现B继承A的方法
评论
简体中文