BST

Posted on In

Binary Search Tree

  • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
  • 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
  • 左、右子树也分别为二叉排序树。
  • 没有键值相等的节点。

实现

Node:

1
2
3
4
5
6
7
8
let print = (key) => console.log(key)
class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

Tree：

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
class BinarySearchTree {
  constructor() {
    this.root = null
  }

  insert(key) {
    const node = new Node(key)
    if (this.root == null) {
      this.root = node
    } else {
      insertNode(this.root, node)
    }

    function insertNode(parent, node) {
      if (parent.key > node.key) {
        if (parent.left == null) {
          parent.left = node
        } else {
          insertNode(parent.left, node)
        }
      } else {
        if (parent.right == null) {
          parent.right = node
        } else {
          insertNode(parent.right, node)
        }
      }
    }
  }

  inOrderTraverse() {
    // 中序遍历
    inOrderTraverse(this.root)

    function inOrderTraverse(node) {
      if (node) {
        inOrderTraverse(node.left)
        print(node.key)
        inOrderTraverse(node.right)
      }
    }
  }

  preOrderTraverse() {
    // 先序遍历
    preOrderTraverse(this.root)

    function preOrderTraverse(node) {
      print(node.key)
      preOrderTraverse(node.left)
      preOrderTraverse(node.right)
    }
  }

  postOrderTraverse() {
    // 后序遍历
    postOrderTraverse(this.root)

    function postOrderTraverse(node) {
      postOrderTraverse(node.left)
      postOrderTraverse(node.right)
      print(node.key)
    }
  }

  max() {
    let maxNode = {}

    function getMax(node) {
      if (node && node.right) {
        maxNode = node
        getMax(node.right)
      }
    }
    getMax(this.root)
    return maxNode.key
  }

  min() {
    let minNode = {}

    function getMin(node) {
      if (node && node.left) {
        minNode = node
        getMin(node.left)
      }
    }
    getMin(this.root)
    return minNode.key
  }

  search(key) {
    function findNode(node) {
      if (!node) return false
      if (key > node.key) {
        return findNode(node.right)
      } else if (key < node.key) {
        return findNode(node.left)
      }
      return node
    }
    return findNode(this.root)
  }

  remove(key) {
    if (!this.search(key)) return

    // 调整二叉树
    function adjustNode(current, key) {
      if (key < current.key) {
        current.left = adjustNode(current.left, key)
        return current
      } else if (key > current.key) {
        current.right = adjustNode(current.right, key)
        return current
      } else {
        // 左右都空直接删除
        if (current.left === null && current.right === null) {
          return (current = null)
        } else if (current.right === null) {
          // 处理左边不空
          let temp = current.left
          current = null
          return temp
        } else if (current.left === null) {
          // 处理右边不空
          let temp = current.right
          current = null
          return temp
        }

        // 从需要删除的节点的右边寻找一个最小的节点，放置当前位置
        current.key = minNode(current.right)

        // 调整后处理那个节点
        current.right = adjustNode(current.right, current.key)

        return current
      }
    }
    function minNode(node) {
      if (node.left) return minNode(node.left)
      return node
    }
    adjustNode(this.root, key)
  }
}

** Test **

1
2
3
4
5
6
7
8
9
10
11
12
13
var tree = new BinarySearchTree()
for (let i = 5; i < 15; i++) {
  tree.insert(i)
}
for (let i = 30; i > 15; i--) {
  tree.insert(i)
}

print(tree.search(6))
tree.remove(15)
tree.remove(10)
tree.remove(29)
tree.inOrderTraverse()