二叉树算法总结

二叉树的相关算法,建立、遍历等。

结构体定义

1
2
3
4
typedef struct BiTNode {
ElemType data;
struct BiTNode *left, *right;
}BiTNode, *BiTree;

递归遍历(前序)

1
2
3
4
5
6
7
void PreOrderTraverse(BiTree T) {
if ( T == NULL)
return;
print(T->data);
PreOrderTraverse(T->left);
PreOrderTraverse(T->right);
}

非递归遍历(前序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PreOrderTraverse(BiTree T) {
if (T == NULL)
return;
BiTree p = T;
Stack<BiTree> s;

while (p!=NULL || !s.empty()) {

while (p != NULL) {
print(p->data);
s.push(p);
p = p->left;
}

if (!s.empty()) {
p = s.pop();
p = p->right;
}

}
}

非递归遍历(中序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void InOrderTraverse(BiTree T) {
if (T == NULL)
return;
BiTree p = T;
Stack<BiTree> s;

while (p!=NULL || !s.empty()) {

while (p!=NULL) {
s.push(p);
p = p->left;
}

if (!s.empty()) {
p = s.pop();
print(p->data);
p = p->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
void PostOrderTraverse(BiTree T) {
if (T == NULL)
return;
BiTree p;
BTNode temp;
Stack<BTNode> s;

while (p !=NULL || !s.empty()) {
BTNode btn = malloc();
btn->node = p;
btn->isFirst = true;
s.push(btn);
p = p->left;
}

if (!s.empty()) {
temp = s.pop();
if (temp->isFirst == true) {
temp->isFirst = false;
s.push(temp);
p = temp->node->right;
}
else {
print(temp->node->data);
p = NULL;
}
}

}

个人GitHub: http://github.com/icodeu

CSDN博客:http://blog.csdn.net/icodeyou

个人微信号:qqwanghuan 技术交流

image