二叉树的概念和用途

# 二叉树的概念和用途

树是一种非线性的数据结构，分层存储。
树被用来存储具有层级关系的数据，还被用来存储有序列表。
二叉树进行查找特别快，为二叉树添加或删除元素也特别快。

# 二叉树的一些关键点

树由一组以边连接的节点组成。
一棵树最上面的节点称为根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点被称为子节点。一个节点可以有 0 个、1 个或多个子节点。没有任何子节点的节点称为叶子节点。
二叉树是一种特殊的树，子节点数不超过两个。
从一个节点走到另一个节点的这一组边称为路径。
以某种特定顺序访问树中的所有节点称为树的遍历。
树分为几个层次，根节点是第 0 层，它的子节点第 1 层，以此类推。我们定义树的层数就是树的深度。
每个节点都有一个与之相关的值，该值有时被称为键。
一个父节点的两个子节点分别称为左节点和右节点。

# 二叉搜索树

二叉搜索树又称有序二叉树、排序二叉树，它具有以下性质：

左子树上所有节点的值均小于它的根节点的值；
右子树上所有节点的值均大于它的根节点的值；
左右子树也是二叉搜索树。

# 满二叉树和完全二叉树

一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。

对一个有 n 个节点的二叉树，按层级顺序编号，则所有节点的编号为从 1 到 n。如果这个树所有节点和同样深度的满二叉树的编号为从 1 到 n 的节点位置相同，则这个二叉树为完全二叉树。

在上图中，二叉树编号从 1 到 12 的 12 个节点，和前面满二叉树编号从 1 到 12 的节点位置完全对应。因此这个树是完全二叉树。

完全二叉树的条件没有满二叉树那么苛刻：满二叉树要求所有分支都是满的；而完全二叉树只需保证最后一个节点之前的节点都齐全即可。

# 二叉树的存储方式

📌 1. 链式存储结构

链式存储是二叉树最直观的存储方式。

二叉树中一个节点最多可以指向左右两个孩子节点，所以二叉树的每一个节点包含 3 部分。

存储数据的 data 变量
指向左孩子的 left 指针
指向右孩子的 right 指针

📌 2. 数组

使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来。

为什么这样设计呢？因为这样可以更方便地在数组中定位二叉树的孩子节点和父节点。

假设一个父节点的下标是 parent，那么它的左孩子节点下标就是 2 × parent + 1；右孩子节点下标就是 2 × parent + 2。

反过来，假设一个左孩子节点的下标是 leftChild，那么它的父节点下标就是 (leftChild-1)/ 2。

假如节点 4 在数组中的下标是 3，节点 4 是节点 2 的左孩子，节点 2 的下标可以直接通过计算得出。

节点 2 的下标 = (3-1)/2 = 1

显然，对于一个稀疏的二叉树来说，用数组表示法是非常浪费空间的。

什么样的二叉树最适合用数组表示呢?

二叉堆，一种特殊的完全二叉树，就是用数组来存储的。

# 二叉树的代码实现

// 节点
function Node(data) {
  this.data = data;
  this.left = null;
  this.right = null;
}

// 二叉搜索树
function Bst() {
  this.root = null;
  this.insert = insert;
  this.preOrder = preOrder;
  this.inOrder = inOrder;
  this.lastOrder = lastOrder;
  this.iteratePreOrder = iteratePreOrder;
  this.iterateInOrder = iterateInOrder;
  this.iterateLastOrder = iterateLastOrder;
  this.getMin = getMin;
  this.getMax = getMax;
  this.find = find;
  this.remove = remove;
}

// 向树中插入数据
function insert(data) {
  var node = new Node(data);
  if (this.root === null) {
    this.root = node;
  } else {
    var current = this.root;
    var parent;
    while (true) {
      parent = current;
      if (data < current.data) {
        current = current.left;
        if (current === null) {
          parent.left = node;
          break;
        }
      } else {
        current = current.right;
        if (current === null) {
          parent.right = node;
          break;
        }
      }
    }
  }
}

/* 插入操作也可以这么写 */
// 向树中插入数据
function insert(data) {
  var newNode = new Node(data); // 新节点
  if (this.root === null) {
    this.root = newNode;
  } else {
    insertNode(this.root, newNode);
  }
}
// 插入节点方法
function insertNode(node, newNode) {
  if (newNode.data > node.data) {
    // 往右走
    if (node.right === null) {
      node.right = newNode;
    } else {
      insertNode(node.right, newNode); // 递归
    }
  } else if (newNode.data < node.data) {
    // 往左走
    if (node.left === null) {
      node.left = newNode;
    } else {
      insertNode(node.left, newNode); // 递归
    }
  }
}

// 前序遍历：根->左->右
function preOrder(node, res) {
  if (node) {
    res.push(node.data);
    preOrder(node.left, res);
    preOrder(node.right, res);
  }
  return res;
}

// 中序遍历：左->根->右
function inOrder(node, res) {
  if (node) {
    inOrder(node.left, res);
    res.push(node.data);
    inOrder(node.right, res);
  }
  return res;
}

// 后序遍历：左->右->根
function lastOrder(node, res) {
  if (node) {
    lastOrder(node.left, res);
    lastOrder(node.right, res);
    res.push(node.data);
  }
  return res;
}

// 前序遍历的迭代实现
function iteratePreOrder(node, res) {
  const stack = [];
  while (node || stack.length) {
    // 迭代访问节点的左孩子，并入栈
    while (node) {
      res.push(node.data);
      stack.push(node);
      node = node.left;
    }
    // 如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
    if (stack.length) {
      node = stack.pop();
      node = node.right;
    }
  }
  return res;
}

// 中序遍历的迭代实现
function iterateInOrder(node, res) {
  const stack = [];
  while (node || stack.length) {
    // 迭代访问节点的左孩子，并入栈
    while (node) {
      stack.push(node);
      node = node.left;
    }
    // 如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
    if (stack.length) {
      node = stack.pop();
      res.push(node.data);
      node = node.right;
    }
  }
  return res;
}

// 后序遍历的迭代实现
function iterateLastOrder(node, res) {
  const stack = [];
  let prev = null;
  while (node || stack.length) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    if (node.right === null || node.right === prev) {
      res.push(node.data);
      prev = node;
      node = null;
    } else {
      stack.push(node);
      node = node.right;
    }
  }
  return res;
}

// 获取树中的最小节点
function getMin(node) {
  var current = this.root || node;
  while (current.left) {
    current = current.left;
  }
  return current;
}

// 获取树中的最大节点
function getMax(node) {
  var current = this.root || node;
  while (current.right) {
    current = current.right;
  }
  return current;
}

// 查找某个数据
function find(data) {
  var current = this.root;
  while (current) {
    if (data === current.data) {
      return current;
    } else if (data < current.data) {
      current = current.left;
    } else {
      current = current.right;
    }
  }
  return null;
}

// 删除某个数据
function remove(data) {
  removeNode(this.root, data);
}

// 删除节点方法
function removeNode(node, data) {
  if (node === null) {
    return null;
  }
  if (data === node.data) {
    // 叶子节点
    if (node.left === null && node.right === null) {
      return null;
    }
    // 只有右节点
    if (node.left === null) {
      return node.right;
    }
    // 只有左节点
    if (node.right === null) {
      return node.left;
    }
    // 左右节点都有，记住删除后要替换成右子树的最小节点
    var tempNode = getMin(node.right); // 找到右子树的最小节点
    node.data = tempNode.data;
    node.right = removeNode(node.right, tempNode.data);
    return node;
  } else if (data < node.data) {
    node.left = removeNode(node.left, data);
    return node;
  } else {
    node.right = removeNode(node.right, data);
    return node;
  }
}

var bst = new Bst();
bst.insert(23);
bst.insert(45);
bst.insert(16);
bst.insert(37);
bst.insert(3);
bst.insert(99);
bst.insert(22);
console.log("前序遍历：", bst.preOrder(bst.root, []));
console.log("中序遍历：", bst.inOrder(bst.root, []));
console.log("后序遍历：", bst.lastOrder(bst.root, []));
console.log("最小节点：", bst.getMin());
console.log("最大节点：", bst.getMax());
bst.remove(16);
console.log("中序遍历：", bst.inOrder(bst.root, []));

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

首页

二叉树的概念和用途