二叉树递归与非递归的实现

 

二叉树先、中、后序递归遍历和非递归遍历

#include <iostream>
#include <malloc.h>
#include <stack>
using namespace std;

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

void CreateBitree(BiTNode **root)
{
        char ch;
        cin>>ch;
        if(ch=='#')
                *root=NULL;
    else
        {
                *root=(BiTNode *)malloc(sizeof(BiTNode));
                (*root)->data=ch;
                CreateBitree(&((*root)->lchild));
                CreateBitree(&((*root)->rchild));
        }
}

void PreOrder(BiTNode *T)
{
 if(T==NULL)
 ;
 else
 {
    printf("%c ",T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
 }
}
void InOrder(BiTree *T)
{
 if(*T==NULL)
 ;
 else
 {
    InOrder(&(*T)->lchild);
    printf("%c ",(*T)->data);
    InOrder(&(*T)->rchild);
 }
}

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

void PreOrder_Nonrecursive(BiTree T) //先序遍历的非递归
{
    if(!T)
        return ;

    stack<BiTree> s;
    while(T) // 左子树上的节点全部压入到栈中
    {
        s.push(T);
        cout<<T->data<<" ";
        T = T->lchild;
    }

    while(!s.empty())
    {
        BiTree temp = s.top()->rchild; // 栈顶元素的右子树
        s.pop(); // 弹出栈顶元素
        while(temp) // 栈顶元素存在右子树，则对右子树同样遍历到最下方
        {
            cout<<temp->data<<" ";
            s.push(temp);
            temp = temp->lchild;
        }
    }
        cout<<endl;
}

void InOrderTraverse(BiTree T) // 中序遍历的非递归
{
    if(!T)
        return ;
    stack<BiTree> S;
    BiTree curr = T->lchild; // 指向当前要检查的节点
    S.push(T);
    while(curr != NULL || !S.empty())
    {
        while(curr != NULL) // 一直向左走
        {
            S.push(curr);
            curr = curr->lchild;
        }
        curr = S.top();
        S.pop();
        cout<<curr->data<<" ";
        curr = curr->rchild;
    }
        cout<<endl;
}

void PostOrder_Nonrecursive(BiTree T) // 后序遍历的非递归
{
    stack<BiTree> S;
    BiTree curr = T ; // 指向当前要检查的节点
    BiTree previsited = NULL; // 指向前一个被访问的节点
    while(curr != NULL || !S.empty()) // 栈空时结束
    {
        while(curr != NULL) // 一直向左走直到为空
        {
            S.push(curr);
            curr = curr->lchild;
        }
        curr = S.top();
        // 当前节点的右孩子如果为空或者已经被访问，则访问当前节点
        if(curr->rchild == NULL || curr->rchild == previsited)
        {
            cout<<curr->data<<" ";
            previsited = curr;
            S.pop();
            curr = NULL;
        }
        else
            curr = curr->rchild; // 否则访问右孩子
    }
        cout<<endl;
}

int main()
{
        BiTree *root; //定义一个根结点
        root=(BiTree *)malloc(sizeof(BiTNode));
        CreateBitree(root);
        PreOrder_Nonrecursive(*root);
        InOrderTraverse(*root);
        PostOrder_Nonrecursive(*root);
        PreOrder(*root);
        printf("\n");
        InOrder(root);
        printf("\n");
        PostOrder(root);
        printf("\n");
        return 0;
}

结果

123##4##56##7##
1 2 3 4 5 6 7
3 2 4 1 6 5 7
3 4 2 6 7 5 1
1 2 3 4 5 6 7
3 2 4 1 6 5 7
3 4 2 6 7 5 1