二叉树的遍历

还记得那些面试题吗? 二叉树的遍历

前序遍历

前序遍历:根结点->左子树->右子树

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
伪代码

//递归
function preorder(root) {
if (root) {
printf("%d\n", root->data);

preorder(root->left);
preorder(root->right);
}
}

//非递归,栈
//思路:
//1. 根结点开始,开始遍历,并输出,将结点压入到栈
//2. 当到达最左结点的时候,访问右结点
//第一步已经输出了根结点,和最左结点
function preorderInteration(root) {
if (root == NULL) {
return ;
}
node = root;
while (node != NULL && !stack.isempty()) {
while (node != NULL) {
//输出根结点,最后输出了最左结点
printf("%d\n", node->data);
stack.push(node);
node = node->left
}
if (! stack.isempty()) {
node = stack.top();
stack.pop();
node = node->right;
}
}
}

中序遍历

中序遍历:左子树->根结点->右子树

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
伪代码 

//递归
function midorder(root) {
if (root) {
midorder(root->left);
printf("%d\n", root->data);
midorder(root->right);
}
}

//非递归 栈来实现
//思路:
//1. 从根结点开始,开始遍历
//2. 递归输出直至最左,然后输出(中序先输出左孩子,而中序遍历第一个输出的是其最左叶子结点)
//3. 当到达最左结点的时候,访问右结点
function midorderinteration(root) {
if (root == NULL) {
return ;
}
node = root;
while (node != NULL && !stack.isempty()) {
while (node != NULL) {
stack.push(node);
node = node->left
}
if (! stack.isempty()) {
node = stack.top();
printf("%d\n", node->data);
stack.pop();
node = node->right;
}
}
}

后序遍历

后序遍历:左子树->右子树->根结点

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
伪代码 

//递归
function postorder(root) {
if (root) {
postorder(root->left);
postorder(root->right);
printf("%d\n", root->data);
}
}

//非递归 栈来实现
//思路:保证根结结点在左右访问之后才能访问
//1. 对于任意结点N先入栈
//2. 如果N不存在左右孩子,则访问
// 如果N的左孩子刚被输出,而N的右孩子为NULL,则访问
// 如果N的右孩子刚被输出,则访问
function postorderiteration(root) {
if (root == NULL) {
return ;
}
pre; // 上一次访问的结点
cur; // 当前结点
stack.push(root);

while (!stack.empty()) {
cur = stack.top();
if (
(cur->left == NULL && cur->right == NULL) ||
(cur->left == pre && cur->right == NULL) ||
(pre == cur->right)
) {
printf("%d\n", cur->data);
// 出栈
stack.pop();
pre = cur;
} else {
if (cur->right != NULl) {
push(cur->right);
}
if (cur->left != NULl) {
push(cur->left);
}
}
}
}

层次遍历/广度优先

从最顶层,一层层向下遍历,又可称为广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
伪代码

// 迭代,不能用递归实现

function levelOrder(root) {
tempNode = root;
while (tempNode) {
printf("%d\n", tempNode->data);
if (tempNode->left) {
// 左子树存在,入队列
enQueue(queue, tempNode->left);
}
if (tempNode->right) {
// 右子树存在,入队列
enQueue(queue, tempNode->right);
}
// 获取出队列的值
tempNode = deQueue(queue);
}
}

深度优先遍历(包含前序遍历、中序遍历、后序遍历)


1
2
3
4
5
6
7
8
9
10
伪代码

//递归
function getList(head)
{
if (!head.left && !head.right) {
return head.val;
}
return head.val + getList(head.left) + getList(head.right);
}

xpisme wechat
微信号