二叉树的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var tree = {
val:'F',
left: {
val: 'B',
left: {val: 'A'},
right: {
val: 'D',
left: {val: 'C'},
right: {val: 'E'}
}
},
right: {
val: 'G',
right: {
val: 'I',
left:{val: 'H'}
}
}
}

深度优先搜索

深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

常见的做法是采用栈(LIFO)或队列(FIFO)。由于树本身是一种自我引用(即递归定义)的数据结构,因此很自然也可以用递归方式,或者更准确地说,用corecursion,来实现延迟节点的保存。这时(采用递归的情况)这些节点被保存在call stack中。

前序遍历(Pre-Order Traversal)

指先访问根,然后访问左子树,再访问右子树的遍历方式。

深度优先遍历 - 前序遍历:F, B, A, D, C, E, G, I, H.

遍历顺序:F, B, A, D, C, E, G, I, H

  • 使用递归

递归调用遍历方法,唯一的区别只是在于访问自身节点的位置不同:前序在所有节点之前,后序在所有节点之后,中序则是在两节点之间。

1
2
3
4
5
6
7
function pre_order_traversal_recursion(root) {
if(root) {
console.log(root.val)
pre_order_traversal_recursion(root.left)
pre_order_traversal_recursion(root.right)
}
}

  • 非递归 使用栈

栈的特点是先进后出,所以进栈是要先进根节点,出栈的时候访问,再进右子节点再进左子节点,再出栈访问,重复以上操作,直到栈空。

在入栈前判定空节点,这样可以减少出入栈的次数,也减少内存使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function pre_order_traversal(root) {
if(root) {
let stack = []
stack.push(root)

while(stack.length > 0) {
//console.log(stack.map(item => item.val))
root = stack.pop()
console.log(root.val)

if(root.right) {
stack.push(root.right)
}

if(root.left) {
stack.push(root.left)
}
}
}
}

中序遍历(In-Order Traversal)

指先访问左(右)子树,然后访问根,最后访问右(左)子树的遍历方式。

深度优先遍历 - 中序遍历:A, B, C, D, E, F, G, H, I.

遍历顺序:A, B, C, D, E, F, G, H, I.

  • 使用递归

    1
    2
    3
    4
    5
    6
    7
    function in_order_traversal_recursion (root) {
    if(root) {
    in_order_traversal_recursion(root.left)
    console.log(root.val)
    in_order_traversal_recursion(root.right)
    }
    }
  • 非递归 使用栈
    中序遍历的非递归实现需要不停地将左子节点入栈,直到遇到空节点为止。然后就可以出栈输出一个节点进行访问,之后将转向其右子节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    function in_order_traversal(root) {
    if(root) {
    let stack = []

    while(stack.length > 0 || !!root) {
    //console.log(stack.map(item => item.val))
    if(root) {
    stack.push(root)
    root = root.left
    }else {
    root = stack.pop()
    console.log(root.val)
    root = root.right
    }
    }
    }
    }

后序遍历(Post-Order Traversal)

指先访问子树,然后访问根的遍历方式

深度优先搜索 - 后序遍历:A, C, E, D, B, H, I, G, F.

遍历顺序:A, C, E, D, B, H, I, G, F.

  • 使用递归

    1
    2
    3
    4
    5
    6
    7
    function post_order_traversal_recursion(root) {
    if(root) {
    post_order_traversal_recursion(root.left)
    post_order_traversal_recursion(root.right)
    console.log(root.val)
    }
    }
  • 非递归 使用栈

使用一个栈实现

对于任一节点,将其入栈,然后沿其左子树一直往下搜索,直到搜索到没有左孩子的节点,此时该节点出现在栈顶,但是此时不能将其出栈并访问,因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理,当访问完其右孩子时,该节点又出现在栈顶,此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出,在这个过程中,每个节点都两次出现在栈顶,只有在第二次出现在栈顶时,才能访问它。因此需要多设置一个变量标识该节点是否是第一次出现在栈顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function post_order_traversal(root) {
if(root) {
let stack = []
stack.push(root)
let tmp = null

while(stack.length > 0) {
//console.log(stack.map(item => item.val))
tmp = stack[stack.length - 1]

if(tmp.left && root !== tmp.left && root !== tmp.right) {
stack.push(tmp.left)
}else if(tmp.right && root !== tmp.right) {
stack.push(tmp.right)
}else {
console.log(stack.pop().val)
root = tmp
}
}
}
}

使用两个栈实现

后序遍历的结构,相当于前序遍历访问左右子树的顺序互换,再把最后的结构前后反一下就可以了。

此方式是先遍历根节点,再遍历右子树,最后遍历左子树。

再借助第二个栈,将顺序倒转过来访问,就是后序遍历的顺序了。

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
function post_order_traversal_two_stack(root) {
if(root) {
let stack1 = []
let stack2 = []
stack1.push(root)

while(stack1.length > 0) {
// console.log('stack1:',stack1.map(item => item.val))
// console.log('stack2:',stack2.map(item => item.val))
root = stack1.pop()
stack2.push(root)

if(root.left) {
stack1.push(root.left)
}
if(root.right) {
stack1.push(root.right)
}
}

while(stack2.length !== 0) {
console.log(stack2.pop().val);
}


}
}

广度优先搜索

和深度优先遍历不同,广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。

广度优先遍历 - 层次遍历:F, B, G, A, D, I, C, E, H.

使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候,执行循环:取出队列的一个节点,如果该节点的左子树为非空,则将该节点的左子树入队列;如果该节点的右子树为非空,则将该节点的右子树入队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function layer_traversal(note) {
if(!node) {
throw new Error('Empty Tree')
}

var que = []
que.push(node)
while(que.length !== 0) {
node = que.shift()
console.log(node.value)
if(node.left) que.push(node.left)
if(node.right) que.push(node.right)
}
}

参考资料