二叉搜索树

发表于 | 分类于

二叉搜索树

《学习JavaScri数据结构与算法》

数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。百度百科：数据结构

  • 为什么要学习数据结构？
    程序=算法+数据结构，计算机程序设计的本质是将业务逻辑转换成数理逻辑，通过逻辑推理以及数理运算解决客观世界存在的困难，而算法和数据解结构就是数理逻辑的推演模式和展现方式。

二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。百度百科：二叉搜索树

一些名词概念

一个节点可以有祖先及诶单和后台，一个节点的祖先（除了根节点）包括父节点、祖父节点、曾祖父节点…

  • 子树：子树由节点和它的后台组成

  • 节点的深度：节点的深度取决于它的祖先节点的数量

  • 树的高度：高度取决于所有节点深度的最大值

树的遍历

  • 前序遍历
    前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

    前序遍历结果：ABDECF

前序遍历可用于复制一棵已有的二叉树，或是打印一个结构化的文档。

  • 中序遍历
    指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式

以从最小到最大的顺序访问所有节点，中序遍历的一种应用就是排序操作。

  • 后序遍历
    指先访问子树，然后访问根的遍历方式。

    其中的一种应用是计算文件系统中一个目录和它的子目录中所有文件所占空间的大小。

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
function BinaryBree(key) {
           //构造节点方法
           var Node = function (key) {
               this.key = key
               this.left = null
               this.right = null
           }

           //二叉树根节点
           var root = null

           //二叉树插入接口实现
           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)
                   }
               }
           }
	}
	
	var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]
       var binaryBree = new BinaryBree()
	
    nodes.forEach(function (key) {
           binaryBree.insert(key)
       })

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//中序遍历接口
          this.inOrderTraverse = function (callback) {
              inOrderTraverseNode(root, callback)
          }

          //中序遍历接口实现方法
          var inOrderTraverseNode = function (node, callback) {
              if (node !== null) {
                  inOrderTraverseNode(node.left, callback)

                  callback(node.key)

                  inOrderTraverseNode(node.right, callback)
              }
          }

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
//前序遍历接口
         this.preOrderTraverse = function (callback) {
             preOrderTraverseNode(root, callback)
         }

         //前序遍历接口实现
         var preOrderTraverseNode = function (node, callback) {
             if (node !== null) {
                 callback(node.key)
                 preOrderTraverseNode(node.left, callback)
                 preOrderTraverseNode(node.right, callback)
             }
         }

后续遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
//后续遍历接口
          this.postOrderTraverse = function (callback) {
              postOrderTraverseNode(root, callback)
          }

          //前序遍历接口实现
          var postOrderTraverseNode = function (node, callback) {
              if (node !== null) {
                  postOrderTraverseNode(node.left, callback)
                  postOrderTraverseNode(node.right, callback)
                  callback(node.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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//查找最小值
         this.min = function () {
             return minNode(root)
         }

         var minNode = function (node) {
             if (node) {
                 //如果当前节点存在左节点，继续执行循环
                 while (node && node.left !== null) {
                     node = node.left
                 }
             }
             return node.key
         }

         //查找最大值
         this.max = function () {
             return maxNode(root)
         }
         var maxNode = function (node) {
             if (node) {
                 //如果当前节点存在右节点，继续执行循环
                 while (node && node.right !== null) {
                     node = node.right
                 }
             }
             return node.key
         }

         //查找指定数值
         this.search = function (key) {
             return searchNode(root, key)
         }

         var searchNode = function (node, key) {
             if (node === null) {
                 return false
             }
             if (node < node.key) {
                 return searchNode(node.left, key)
             } else if (key > node.key) {
                 return searchNode(node.right, key)
             } else {
                 return true
             }
         }

删除

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
//删除指定指定节点接口
          this.remove = function (key) {
              root = removeNode(root, key)
          }
          //查找排序二叉树中最小节点
          var finMinNode = function (node) {
              if (node) {
                  while (node && node.left !== null) {
                      node = node.left
                  }
              }
              return node
          }
          //删除指定指定节点实现
          var removeNode = function (node, key) {
              if (node === null) {
                  return null
              }
              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
                  } else if (node.right === null) {
                      //只有左节点，将当前节点替换成做左节点
                      node = node.left
                      return node
                  }
                  //拥有左右节点的情况
                  var aux = finMinNode(node.right)
                  node.key = aux.key
                  node.right = removeNode(node.right, aux.key)
                  return node
              }
          }

完整项目文件