DFS
前序遍历:根结点 ---> 左子树 ---> 右子树
中序遍历:左子树---> 根结点 ---> 右子树
后序遍历:左子树 ---> 右子树 ---> 根结点
// 递归版-前序遍历
let result = [];
let dfs = function (node) {
if(node) {
result.push(node.value);
dfs(node.left);
dfs(node.right);
}
}
dfs(tree);
// 非递归
let dfs = function (nodes) {
let result = [];
let stack = [];
stack.push(nodes);
while(stack.length) {
let node = stack.pop();
result.push(node.value);
// 处理节点,比如 console.log(node.value);
if(node.right) stack.push(node.right); // 先压入右子树
if(node.left) stack.push(node.left); // 后压入左子树
}
return result;
}
dfs(tree);
BFS
Breadth-first Search (BFS) 广度优先搜索,是一种盲目搜索法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能地址,彻底地搜索整张图,直到找到结果为止。它的特点是越是接近根结点的结点将越早地遍历。
可以应用的场景:
- 查找图中所有连接组件(Connected Component)。一个连接组件是图中的最大相连子图。
- 查找连接组件中的所有节点。
- 查找非加权图中任两点的最短路径。
- 测试一图是否为二分图。
- (Reverse)Cuthill–McKee算法
在BFS中,结点的处理顺序与它们添加到队列的顺序是完全相同的顺序,即先进先出,所以广度优先搜索一般使用队列实现。
// 非递归版
function bfs (node) {
let result = [];
let queue = [];
queue.push(node);
while(queue.length) {
node = queue.shift();
result.push(node.value); // 不要忘记访问
// 处理节点,比如 console.log(node.value);
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
return result;
}
bfs(tree);
二分查找
// 递归版
function bsearch(array,low,high,target)
{
if (low > high) return -1;
var mid = Math.floor((low + high)/2);
if (array[mid]> target){
return bsearch(array, low, mid -1, target);
} else if (array[mid]< target){
return bsearch(array, mid+1, high, target);
}ese{return mid;}
}
// 非递归
function bsearchWithoutRecursion(array,low,high,target)
{
while(low <= high)
{
var mid = Math.floor((low + high)/2);
if (array[mid] > target){
high = mid - 1;
}else if (array[mid] < target){
low = mid + 1;
}else{
return mid;
}
}
return -1;
}