panther
posts - 43,comments - 3,trackbacks - 0
树遍历 非递归 + 栈

 


#include "stdafx.h"
#include <iostream>
#include "windows.h"


#include "stdio.h"
#include "stdlib.h"
#include "signal.h"
#include "process.h"
#include "malloc.h"

#include "fstream"
#include "list"
#include "vector"
#include "algorithm"
#include "time.h"

#include "queue"
#include "stack"

using namespace std;

typedef struct TNode
{
    TNode *left, *right;
    int data;
    TNode(int d){
        left = right = NULL;
        data = d;
    }
} TNode;

void inorderTrave(TNode* root)
{
    stack<TNode*> st;
    st.push(root);
    TNode *p = 0;

    while (!st.empty())
    {
        while(st.top())st.push(st.top()->left);
        st.pop();
        if (!st.empty())
        {
            p = st.top();
            st.pop();
            printf("%d, ", p->data);
            st.push(p->right);
        }
    }
}

void preTrave(TNode* root)
{
    stack<TNode*> st;

    while (root || !st.empty())
    {
        while(root)
        {
            printf("%d, ", root->data);
            if (root->right) st.push(root->right);
            root = root->left;
        }
        if (!st.empty())
        {
            root = st.top();
            st.pop();
        }
    }
}

void postTrave(TNode* root)
{
    stack<TNode*> st;
    stack<int> stF;

    while (root || !st.empty())
    {
        while (root)
        {
            st.push(root);
            stF.push(0);
            root = root->left;
        }

        root = st.top();
        int f = stF.top();
        st.pop();stF.pop();

        if (f == 0)
        {
            st.push(root);
            stF.push(1);
            {
                root = root->right;
            }
        }
        else if (f == 1)
        {
            printf("%d, ", root->data);
            root = 0;
        }
    }
}


int main()
{
    TNode *r = new TNode(1);

    TNode *r1 = new TNode(2);
    TNode *r2 = new TNode(3);


    TNode *r12 = new TNode(4);
    TNode *r21 = new TNode(5);

    r->left = r1;
    r->right = r2;
    r1->right = r12;
    r2->left= r21;
    preTrave(r);
    printf("\n");
    inorderTrave(r);
    printf("\n");
    postTrave(r);
    return 0;
}


posted on 2010-04-28 23:54 RUI 阅读(237) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 RUI Powered By博客园 模板提供：沪江博客