二叉树
二叉树(Binary tree)是每个节点最多只有两个分支的树结构，通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
二叉树的第 $i$ 层最多拥有 $2^i$ 个节点，深度为 $k$ 的二叉树最多拥有 $2^{k+1}-1$ 个节点(根节点所在深度为 $0$)。
对于一个非空的二叉树，若树叶的总数为 $n_0$，拥有两个子节点的节点数为 $n_1$，则 $n_0=n_1+1$。
二叉树与普通树的区别
- 普通树的节点个数至少为 1，而二叉树的节点个数可以为 0。
- 普通树节点的最大分支度没有限制，而二叉树节点的最大分支度为 2。
- 普通树的节点无左、右次序之分，而二叉树的节点有左、右次序之分。
二叉树的种类
满二叉树(完美二叉树)
如果一棵二叉树除最下面一层外，每一层的每一个节点都有两个子节点，这样的树就是满二叉树。
1
/ \
2 3
/\ /\
4 5 6 7
完全二叉树
在一棵二叉树中，若除了最后一层之外其他层都是满的，并且最后一层要么是满的，要么在右侧缺少连续若干节点，这样的树就是完全二叉树。
深度为 $k$ 的完全二叉树，至少有 $2^{k-1}$ 个节点，至多有 $2^k-1$ 个节点。
1
/ \
2 3
/\
4 5
二叉查找树
二叉查找树(Binary Search Tree)也称为有序二叉树或排序二叉树，是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值。
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。
- 任意节点的左、右子树也分别为二叉查找树。
- 通过中序遍历，将得到的是一个有序的数列。
5
/ \
4 6
/\ /
3 9 5
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为 $O(log n)$。如果待排序列表本身有序，则二叉查找树等同于线性表，最坏情况为 $O(n)$。
平衡二叉查找树(AVL 树)
平衡二叉查找树(Balanced Binary Search Tree)是一种结构平衡的二叉查找树，是二叉查找树最优的情况。树中任一节点对应的两棵子树的最大高度差为 1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 $O(log n)$。
下图左边是二叉查找树，右边是 AVL 树：
5 5
/ \ / \
4 6 4 6
/\ / /\
3 9 5 3 9
二叉树的遍历
我们假设有这样一个树：
1
/ \
2 3
/\ /\
4 5 6 7
/ \
9 8
将其抽象为 JS 对象 binaryTreeObj：
const binaryTreeObj = {
data: 1,
left: {
data: 2,
left: {
data: 4,
left: {
data: 9,
},
},
right: {
data: 5,
},
},
right: {
data: 3,
left: {
data: 6,
right: {
data: 8,
},
},
right: {
data: 7,
},
},
}
先序遍历
先序遍历的顺序为：根节点 👉 左节点 👉 右节点，因此上面的树先序遍历结果为 1, 2, 4, 9, 5, 3, 6, 8, 7。
算法实现：
function preOrder(tree) {
const res = []
function loop(node) {
if (node) {
res.push(node.data)
loop(node.left)
loop(node.right)
}
}
loop(tree)
return res
}
中序遍历
中序遍历的顺序为：左节点 👉 根节点 👉 右节点，因此上面的树中序遍历结果为 9, 4, 2, 5, 1, 6, 8, 3, 7。
算法实现：
function inOrder(tree) {
const res = []
function loop(node) {
if (node) {
loop(node.left)
res.push(node.data)
loop(node.right)
}
}
loop(tree)
return res
}
后序遍历
后序遍历的顺序为：左节点 👉 右节点 👉 根节点，因此上面的树后序遍历结果为 9, 4, 5, 2, 8, 6, 7, 3, 1。
算法实现：
function postOrder(tree) {
const res = []
function loop(node) {
if (node) {
loop(node.left)
loop(node.right)
res.push(node.data)
}
}
loop(tree)
return res
}
层序遍历(广度优先遍历)
层序遍历顾名思义是从根节点往下一层一层的遍历，所以层序遍历的结果为 1, 2, 3, 4, 5, 6, 7, 9, 8。
// 循环
function levelOrder(tree) {
const res = []
const queue = [binaryTreeObj]
while (queue.length) {
const node = queue.shift()
res.push(node.data)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
return res
}
// 递归
function levelOrder(tree) {
const res = []
const queue = []
function loop(node) {
if (node) {
res.push(node.data)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
loop(queue.shift())
}
}
loop(tree)
return res
}
如何比较两个二叉树是否相同
对于两个二叉树，仅比较先序、中序或者后序都不能判断出两个树是否完全相同，如下两个树的先序遍历相同但结构不同：
1 1
/ \ / \
2 3 2 3
/\ /\ / /
4 5 6 7 4 6
/ \ /\ /\
8 9 8 5 9 7
两棵树对应的抽象 JS 对象：
const tree1 = {
data: 1,
left: {
data: 2,
left: {
data: 4,
left: {
data: 8,
},
},
right: {
data: 5,
},
},
right: {
data: 3,
left: {
data: 6,
right: {
data: 9,
},
},
right: {
data: 7,
},
},
}
const tree2 = {
data: 1,
left: {
data: 2,
left: {
data: 4,
left: {
data: 8,
},
right: {
data: 5,
},
},
},
right: {
data: 3,
left: {
data: 6,
left: {
data: 9,
},
right: {
data: 7,
},
},
},
}
1. 层序遍历比较
采用层序遍历，判断节点值是否相同，再判断分支是否也是相同的：
function levelOrderComp(tree1, tree2) {
const tree1Queue = [tree1]
const tree2Queue = [tree2]
let res = true
while (tree1Queue.length && tree2Queue.length) {
const node1 = tree1Queue.shift()
const node2 = tree2Queue.shift()
if (node1.data !== node2.data) {
// 两个节点值不同，说明不相等
res = false
break
}
if (!!node1.left !== !!node2.left) {
// 两个节点一个有左节点一个没有，说明不相等
res = false
break
} else if (node1.left && node2.left) {
// 两个节点都有左节点
tree1Queue.push(node1.left)
tree2Queue.push(node2.left)
}
if (!!node1.right !== !!node2.right) {
// 两个节点一个有右节点一个没有，说明不相等
res = false
break
} else if (node1.right && node2.right) {
// 两个节点都有右节点
tree1Queue.push(node1.right)
tree2Queue.push(node2.right)
}
}
return res
}
2. 先序(后序)+中序遍历比较
由于前面已经写过这几种排序的写法，这里就不写了，单讲讲为什么这样可以确定同一个二叉树。
因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设 1 个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设 $r$ 个元素）是右子树，若为空，则右子树为空。根据前序遍历中"根-左子树-右子树"的顺序，则由从第二元素开始的 1 个结点序列和中序序列根左边的 1 个结点序列构造左子树，由前序序列最后 $r$ 个元素序列与中序序列根右边的 $r$ 个元素序列构造右子树。
由中序序列和先序序列能唯一确定一棵二叉树，但是由先序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。
反例：任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。
已经说明由二叉树的前序序列和中序序列可以确定一棵二叉树，现在来证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
当 $n=1$ 时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。
设当 $n=m-1$ 时结论成立，现证明当 $n=m$ 时结论成立。
设中序序列为 $S1,S2,…,Sm$，后序序列是 $P1,P2,…,Pm$。因后序序列最后一个元素 $Pm$ 是根，则在中序序列中可找到与 $Pm$ 相等的结点（设二叉树中各结点互不相同）$Si(1≤i≤m)$，因中序序列是由中序遍历而得，所以 $Si$ 是根结点，$S1,S2,…,Si-1$ 是左子树的中序序列，而 $Si+1,Si+2,…,Sm$ 是右子树的中序序列。
若 $i=1$，则 $S1$ 是根，这时二叉树的左子树为空，右子树的结点数是 $m-1$，则 ${S2,S3,…,Sm}$ 和 ${P1,P2,…,Pm-1}$ 可以唯一确定右子树，从而也确定了二叉树。
若 $i=m$，则 $Sm$ 是根，这时二叉树的右子树为空，左子树的结点数是 $m-1$，则 ${S1,S2,…,Sm-1}$ 和 ${P1,P2,…,Pm-1}$ 唯一确定左子树，从而也确定了二叉树。
最后，当 $1<i<m$ 时，$Si$ 把中序序列分成 ${S1,S2,…,Si-1}$ 和 ${Si+1,Si+2,…,Sm}$。由于后序遍历是"左子树-右子树-根结点"，所以 ${P1,P2,…,Pi-1}$ 和 ${Pi,Pi+1,…Pm-1}$ 是二叉树的左子树和右子树的后序遍历序列。因而由 ${S1,S2,…,Si-1}$ 和 ${P1,P2,…,Pi-1}$ 可唯一确定二叉树的左子树，由 ${Si+1,Si+2,…,Sm}$ 和 ${Pi,Pi+1,…,Pm-1}$ 可唯一确定二叉树的右子树。
哈夫曼树(最优二叉树)
给定 $n$ 个权值作为 $n$ 的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
下图是一个哈夫曼树：
18
/ \
7 11
/\ /\
3 4 5 6
/\
1 2
构造上面这个哈夫曼树我们只需要 5 个叶子节点： 1, 2, 4, 5, 6 即可构造。
构造步骤：
- 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树。
- 取出根节点权值最小的两颗二叉树。
- 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和。
- 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理。