遍历二叉树的操作

我自己实现的二叉树的操作，比较简易的版本。更具体的见我的上一篇博客。

 

#include<iostream>
#include<stack>
using namespace std;

typedef struct BiTNode
{
    char data;
    BiTNode*lchild;
    BiTNode*rchild;
}BiTNode,*BiTree;


//°????ò?ò???¨???????÷
void CreateBiTree(BiTree &T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        T=NULL;
    else
    {
        T=(BiTNode*)malloc(sizeof(BiTNode));
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

//?°?ò±é?ú??·¨
void PreOrder(BiTree &T) //???é???°?ò±é?ú
{
    if(T)
    {
        printf("%c ",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }

    else return;

}

void InOrder(BiTree &T) //???ò???é±é?ú
{
    if(T)
    {
        InOrder(T->lchild);
        printf("%c ",T->data);
        InOrder(T->rchild);
    }
    else return ;
}

void PostOrder(BiTree &T)
{
    if(T)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%c ",T->data);
    }
    else
        return;

}

void PreOrder_Nonrecursive(BiTree &T) //·????é?°?ò
{
    if(!T)
        return;
    stack<BiTree> s;
    s.push(T);
    while(!s.empty())
    {
        BiTree tmp=s.top();
        cout<<tmp->data<<" ";
        s.pop();
        if(tmp->rchild)
            s.push(tmp->rchild);
        if(tmp->lchild)
            s.push(tmp->lchild);
    }

}

void InOrder_Nonrecursive(BiTree &T) //·????é???ò±é?ú???????é??????·¨
{
    BiTree p,tmp;
    p=T;
    stack<BiTree> s;
    while(p || !s.empty())
    {
     if(p)
        {
            s.push(p);
            p=p->lchild;
        }
        else
        {
            tmp=s.top();
            cout<<tmp->data<<" ";
            s.pop();
            p=tmp->rchild;
        }

    }

}


void PostOrder_Nonrecursive(BiTree &T) //·????é?ó??±é?ú??????·¨
{
    stack<BiTree> s1,s2;
    BiTree curr;
    s1.push(T);
    while(!s1.empty())
    {
        curr=s1.top();
        s2.push(curr);
        s1.pop();

        if(curr->lchild)
            s1.push(curr->lchild);
        if(curr->rchild)
            s1.push(curr->rchild);
    }
    while(!s2.empty())
    {
        printf("%c ",s2.top()->data);
        s2.pop();
    }
}

int main()
{
    BiTree T=NULL;
    CreateBiTree(T);
    PreOrder(T);
    printf("\n");
    InOrder(T);
    printf("\n");
    PostOrder(T);
    printf("\n");
    PreOrder_Nonrecursive(T);
    printf("\n");
    InOrder_Nonrecursive(T);
    printf("\n");
    PostOrder_Nonrecursive(T);
    printf("\n");
    return 0;
}