二叉树

原理

无根节点, 则生成二叉树根节点
当前节点值小于父节点值, 则迁移到左子树中, 如果左子树为空, 则占用为节点位, 否则继续遍历寻找占位
当前节点值大于父节点值, 则迁移到右子树中, 如果右子树为空, 则占用为节点位, 否则继续遍历寻找占位

如图所示二叉树:

graph TD A-->B A-->C B-->D B-->E C-->F

前序遍历

遍历规则

访问根节点
前序遍历左子树
前序遍历右子树

前序遍历最高效的复制出整个二叉树

输出结果: ABDECF

中序遍历

遍历规则

中序遍历左子树
访问根节点
中序遍历右子树

中序遍历可使用于数组排序

输出结果: DBEAFC

后序遍历

遍历规则

后序遍历左子树
后序遍历右子树
访问根节点

后序遍历可使用于系统查找文件

输出结果: DEBCFA

寻找最小值

以根节点为起点, 一直以二叉树最左边节点寻找

输出结果: ABD (D 为最小值)

寻找最大值

以根节点为起点, 一直以二叉树最右边节点寻找

输出结果: ACF (F 为最大值)

寻找节点

以根节点为起点, 当前要检索的值小于当前节点值, 则进入左子树, 反之进入右子树

删除节点

先寻找要删除节点的位置,
如果节点没有左右节点 (如删除 F 节点), 则将该节点直接删除并返回
如果节点有左节点, 无右节点, (如删除 C 节点, 假设 F 为左节点), 则左节点替代要被删除的节点, 结果如下图

graph TD A-->B A-->F B-->D B-->E

如果节点有左节点, 无右节点, (如删除 C 节点, 假设 F 为左节点), 则左节点替代要被删除的节点
如果节点左右节点都存在, (如删除 B 节点), 先寻找出右子树下最小节点, 将最小节点替代要被删除的节点, 并将右子树的最小节点删除, 结果如下图

graph TD A-->E A-->C E-->D C-->F

代码演示

class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}
class BinaryTree {
  // 构造函数 new 时候调用
  constructor() {
    this.root = null
  }
  // 插入子节点
  insertNode(node, newNode) {
    if (node.key > newNode.key) {
      node.left === null
        ? (node.left = newNode)
        : this.insertNode(node.left, newNode)
    } else {
      node.right === null
        ? (node.right = newNode)
        : this.insertNode(node.right, newNode)
    }
  }
  // 插入节点
  insert(key) {
    let newNode = new Node(key)
    if (this.root === null) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }
  inOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.inOrderTraverseNode(node.left, callback)
      callback(node.key)
      this.inOrderTraverseNode(node.right, callback)
    }
  }
  // 中序遍历
  inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback)
  }
  preOrderTraverseNode(node, callback) {
    if (node !== null) {
      callback(node.key)
      this.preOrderTraverseNode(node.left, callback)
      this.preOrderTraverseNode(node.right, callback)
    }
  }
  // 前序遍历
  preOrderTraverse(callback) {
    this.preOrderTraverseNode(callback)
  }
  postOrderTraverseNode(node, callback) {
    if (node !== null) {
      callback(node.key)
      this.postOrderTraverseNode(node.left, callback)
      this.postOrderTraverseNode(node.right, callback)
    }
  }
  // 后序遍历
  postOrderTraverse(callback) {
    this.postOrderTraverseNode(callback)
  }
  minNode(node) {
    if (node) {
      while (node && node.left != null) {
        node = node.left
      }
      return node.key
    }
    return null
  }
  // 查找最小值
  min() {
    return this.minNode(this.root)
  }
  maxNode(node) {
    if (node) {
      while (node && node.right != null) {
        node = node.right
      }
      return node.key
    }
    return null
  }
  // 查找最大值
  max() {
    return this.maxNode(this.root)
  }
  serachNode(node, key) {
    if (node === null) {
      return false
    }
    if (key < node.key) {
      return this.serachNode(node.left, key)
    } else if (key > node.key) {
      return this.serachNode(node.right, key)
    } else {
      return true
    }
  }
  // 查找节点
  serach(key) {
    return this.serachNode(this.root, key)
  }
  findMinNode(node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left
      }
      return node
    }
    return null
  }
  removeNode(node, key) {
    if (node === null) {
      return null
    }
    if (key < node.key) {
      node.left = this.removeNode(node.left, key)
      return node
    } else if (key > node.key) {
      node.right = this.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
      }
      let aux = this.findMinNode(node.right)
      node.key = aux.key
      node.right = this.removeNode(node.right, aux.key)
      return node
    }
  }
  // 删除节点
  remove(key) {
    return this.remove(this.root, key)
  }
}

let tree = [2, 1, 5, 3, 6, 8, 4, 10, 7]
let binaryTree = new BinaryTree()

tree.forEach(key => {
  binaryTree.insert(key)
})

function callback(key) {
  console.log(key)
}

// binaryTree.inOrderTraverse(callback)

console.log('min node value:', binaryTree.min())
console.log('max node value:', binaryTree.max())
console.log(binaryTree.serach(11))

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

# 二叉树

# 原理

# 代码演示

二叉树

原理

代码演示