首页 > 其他 > 详细

非递归遍历二叉树

时间:2015-08-17 00:36:59      阅读:286      评论:0      收藏:0      [点我收藏+]
#include <stack>
#include <stdio.h>
#include <malloc.h>
#include <iostream>
using namespace std;

typedef struct node
{
    int flag;
    char value;
    struct node *lchild;
    struct node *rchild;
}Node, *PNode;

void CreateBinaryTree(PNode &root)                   /* 前序遍历的递归方式动态建立二叉树 */
{
    char ch;
    scanf("\n%c", &ch);
    if(ch == #) {root = NULL; return ;}
    root = (Node *)malloc(sizeof(Node));
    root->flag = 0;                                  // flag==0 ---> 第一次经过:父节点-->自身-->左孩子
                                                     // flag==1 ---> 第二次经过:左孩子-->自身-->右孩子
                                                     // flag==2 ---> 第三次经过:右节点-->自身-->父节点
    root->value = ch;
    CreateBinaryTree(root->lchild);
    CreateBinaryTree(root->rchild);
}
void visit(PNode &pointer)
{
    printf("%c ", pointer->value);
}
void OrderTraversal(PNode &root)                     /* 调整visit(temp)出现位置实现前中后序遍历 */
{
    stack<Node> ss;
    PNode temp = root;

    while(!ss.empty() || temp->flag!=2               /* while内部:if --- else if --- else 结构 */
    {
        if(temp->flag == 0)
        {
            visit(temp);                             // PreorderTraversal
            if(temp->lchild != NULL)
            {
                temp->flag = 1;
                ss.push(*temp);
                temp = temp->lchild;
            }
            else
            {
                //visit(temp);                       // InorderTraversal / PostorderTraversal
                temp = &(ss.top());
                ss.pop();
            }
        }
        else if(temp->flag == 1)
        {
            //visit(temp);                           // InorderTraversal
            temp->flag = 2;
            ss.push(*temp);
            temp = temp->rchild;
        }
        else
        {
            //visit(temp);                           // PostorderTraversal
            temp = &(ss.top());
            ss.pop();
        }
    }
    //visit(temp);                                   // PostorderTraversal
}
int main()
{
    cout << "Input element in preorder:" << endl;
    PNode root;
    CreateBinaryTree(root);
    OrderTraversal(root);
    return 0;
}

 

非递归遍历二叉树

原文:http://www.cnblogs.com/1203ljh/p/4735228.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!