树
树是一种分层数据的抽象模型。例如：DOM树、树形控件等。
Javascript 中没有树，但是可以用 Object 和 Array 构建树。
树的常用操作：深度/广度优先遍历、先中后序遍历。
树的深度/广度优先遍历
深度优先遍历
定义：从根节点，尽可能深的搜索树的分支。
遍历算法：访问根节点，对根节点的 children 挨个进行深度优先遍历。
遍历代码：
const dfs = (root) => {
console.log(root);
root.children.forEach(dfs);
}
遍历顺序图：
深度优先遍历.png
广度优先遍历
定义：先访问里根节点最近的节点。
遍历算法：
- 新建队列，把根节点入队
- 把队头出队，并访问。
- 把对头 children 挨个入队。
- 重复2.3.直到队列为空。
遍历代码：
const bfs = (root) => {
const queue = [root];
while (queue.length > 0) {
const n = queue.shift();
console.log(n);
queue.children.forEach(i => queue.push(i));
}
}
遍历顺序图：
广度优先遍历.png
二叉树
树中每个节点最多只能有两个子节点。
在 Javascript 中通常用对象来模拟二叉树。
二叉树代码示例：
const binaryTree = {
val:1,
left: {
val: 2,
left: Object,
right: Object
},
right: {
val: 3,
left: Object,
right: Object
}
}
二叉树先序遍历
遍历算法（中->左->右）：
- 访问根节点。
- 对根节点的左子树进行先序遍历。
- 对根节点的右子树进行先序遍历。
二叉树先序遍历.png
递归法实现先序遍历：
const preorder = (bt) => {
if (!bt) { return; }
console.log(bt.val);
preorder(bt.left);
preorder(bt.right);
}
栈实现先序遍历：
const preorder = (bt) => {
if (!bt) { return; }
const stack = [bt];
while(stack.length > 0) {
const n = stack.pop();
console.log(n);
if (bt.right) stack.push(bt.right);
if (bt.left) stack.push(bt.left);
}
}
二叉树中序遍历
遍历算法（左->中->右）：
- 对根节点左子树进行中序遍历。
- 访问根节点。
- 对根节点的右子树进行中序遍历。
二叉树中序遍历.png
递归法实现中序遍历：
const inorder = (bt) => {
if (!bt) { return; }
inorder(bt.left);
console.log(be.val);
inorder(bt.right);
}
栈实现中序遍历：
const inorder = (bt) => {
if (!bt) { return; }
const stack = [];
const p = bt;
while(stack.length>0 || p) {
while(p) {
stack.push(p);
p = p.left;
}
const n = stack.pop();
console.log(n);
p = n.right;
}
}
二叉树后序遍历
遍历算法（左->右->中）：
- 对根节点左子树进行中序遍历。
- 对根节点的右子树进行中序遍历。
- 访问根节点。
二叉树后序遍历.png
递归法实现后序遍历：
const postorder = (bt) => {
if (!bt) { return; }
postorder(bt.left);
postorder(bt.right);
console.log(be.val); // 谁先遍历完输出谁
}
栈实现后序遍历：
- 后序遍历遍历顺序是 左右中，现将遍历顺序倒过来就是，中右左
- 按照中右左的顺序推入栈中，再将这个栈推出，推出的顺序即为后序遍历
const postorder = (bt) => {
if (!bt) { return; }
const stack = [bt];
const outputStack = [];
while(stack.length > 0) {
const n = stack.pop();
outputStack.push(n);
if (n.left) stack.push(n.left);
if (n.right) stack.push(n.right);
}
while(outputStack.length > 0) {
const n = outputStack.pop();
console.log(n.val);
}
}
