1
2
3
4
5
6
7
8
9
|
/*
先序遍历,首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问
根结点,然后遍历左子树,最后遍历右子树,如果二叉树为空则返回。
*/
//处理过如下
//对于任一结点p:
// 1)将结点p入栈,访问节点p,节点p出栈;
// 2)判断结点p的右孩子是否为空,其次判断p的左孩子是否为空,这样先压右子树入栈,左子
// 树后压就可以先访问;
|
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
|
void
PrevOrder_NonR()
{
stack<BinaryTreeNode<T>*> s;
if
(_root)
{
s.push(_root);
//将树入栈
}
while
(!s.empty())
//栈不为空,根节点先出栈
{
BinaryTreeNode<T>* top = s.top();
s.pop();
cout << top->_data <<
" "
;
if
(top->_right)
//压入右子树
{
s.push(top->_right);
}
if
(top->_left)
//压入左子树
{
s.push(top->_left);
}
}
cout << endl;
}
|
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
|
/*
中序遍历,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,
仍然先遍历左子树,再访问根结点,最后遍历右子树。即:若二叉树为空则结束返回
否则:
(1)中序遍历左子树。
(2)访问根结点。
(3)中序遍历右子树。
*/
// 处理过程如下:
// 对于任一结点cur,
// 1)若其左孩子不为空,则将cur入栈并将cur的左孩子置为当前的cur,然后对当前结点cur再进行相
// 同的处理;
// 2)若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的cur置为栈顶
// 结点的右孩子;
// 3)直到cur为NULL并且栈为空则遍历结束
void
InOrder_NonR()
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T>* cur = _root;
while
(cur || !s.empty())
{
while
(cur)
{
s.push(cur);
cur = cur->_left;
}
if
(!s.empty())
{
BinaryTreeNode<T>* top = s.top();
cout << top->_data <<
" "
;
s.pop();
cur = top->_right;
}
}
cout << endl;
}
|
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
|
/*
后序遍历,
后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子
树,然后遍历右子树,最后遍历根结点。即:若二叉树为空则结束返回
*/
// 要保证根结点在左孩子和右孩子访问之后才能访问,因此对于任一结点P,先将其入栈。如果P不存在
// 左孩子和右孩子,则可以直接访问它;或者P存在左孩子或者右孩子,但是其左孩子和右孩子都已被
// 访问过了,则同样可以直接访问该结点。若非上述两种情况,则将P的右孩子和左孩子依次入栈,这
// 样就保证了每次取栈顶元素的时候,左孩子在右孩子前面被访问,左孩子和右孩子都在根结点前面被
// 访问。
void
PostOrder_NonR()
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T>* cur = _root;
BinaryTreeNode<T>* pre = NULL;
while
(cur || !s.empty())
{
while
(cur)
{
s.push(cur);
cur = cur->_left;
}
BinaryTreeNode<T>* top = s.top();
//根节点要想被访问则该节点没有右子树或者没有孩子节点
if
(top->_right == NULL || top->_right == pre)
{
cout << top->_data <<
" "
;
pre = top;
s.pop();
}
else
{
cur = top->_right;
}
}
cout << endl;
}
|
二叉树层次遍历即按照层次访问,通常用队列来做。访问根,访问子女,再访问子女的子女(越往后的层次越低)(两个子女的级别相同)
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
|
void
LevelOrder()
{
queue<BinaryTreeNode<T>*> q;
if
(_root)
{
q.push(_toot);
}
while
(!q.empty())
{
BinaryTreeNode<T>* front = q.front();
q.pop();
cout << front->_data <<
" "
;
if
(front->_left)
{
q.push(front->_left);
}
if
(front->_right)
{
q.push(front->_right);
}
}
cout << endl;
}
|
本文转自 七十七快 51CTO博客,原文链接:http://blog.51cto.com/10324228/1755467