Sun's Blog
0%

二叉树遍历非递归算法

发表于 更新于
先序遍历

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> inorderTraversal(TreeNode* root) {
	vector<int> ret;
	stack<TreeNode*> st;
	TreeNode* p = root;
	while (p||!(st.empty())) {
		if (p)
		{
            printf("p:%d\n", p->val);
			st.push(p);
			p = p->left;
		}
		else {
			p = st.top();
			st.pop();
			p = p->right;

		}
	}
	return ret;
}
中序遍历

C++代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> inorderTraversal(TreeNode* root) {
	vector<int> ret;
	stack<TreeNode*> st;
	TreeNode* p = root;
	while (p||!(st.empty())) {
		if (p)
		{
			st.push(p);
			p = p->left;
		}
		else {
			p = st.top();
			st.pop();
			printf("p:%d\n", p->val);
			p = p->right;

		}
	}
	return ret;
}
后序遍历

伪代码:

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
void PostOrderTraverse(BinTree b)
{
    InitStack(S);///初始化创建栈
    BinTree p=b, r=NULL;///p为工作指针,辅助指针r
    while(p||!isEmpty(s))
    {
        if(p)///从根节点到最左下角的左子树都入栈
        {
            Push(S,p);///中序现将结点进栈保存
            p=p->lchild;
        }
        else
        {
            GetTop(S,p);///取栈顶，注意！不是出栈！
            if(p->rchild&&p->rchild!=r)///1.右子树还没有访问并且右子树不空，第一次栈顶
            {
                p=p->rchild;///进入右子树
            }
            else///右子树已经访问或为空，接下来出栈访问结点，第二次栈顶
            {
                p=Pop(s);
                printf(" %c ",p->data);
                r=p;///指向访问过的右子树结点
                p=NULL;///使p为空继续访问栈顶
            }
        }
    }
}
层次遍历

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void LevelOrder(BiTree b)
{
    InitQueue(Q);///初始化建立队列
    BinTree p;
    EnQueue(Q,b);///根节点入队
    while(!isEmpty(Q))///队列不空循环
    {
        DeQueue(Q,p);///队头元素出队
        printf(" %c ",p->data);
        ///左右孩子入队
        if(p->lchild!=NULL)
        {
            EnQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL)
        {
            EnQueue(Q,p->rchild);
        }
    }
}