C语言非递归实现二叉树的先序、中序、后序、层

C语言非递归实现二叉树的先序、中序、后序、层序遍历代码如下:

#include <stdio.h>   
#include <stdlib.h> 
#include <stack>
#include <queue>
using namespace std;

//*****二叉树的二叉链表存储表示*****//   
typedef struct BiNode   
{   
    char data;   
    struct BiNode *lchild, *rchild;
    int visitCount;
}BiNode, *BiTree;   

//*****按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树构造二叉链表表示的二叉树T*****//   
void CreateBiTree(BiTree &T)           
{                                     
    char ch;   
    scanf("%c", &ch);   
    if(ch == ' ')   
    {   
        T = NULL;   
    }   
    else   
    {   
        if(!(T = (BiNode *)malloc(sizeof(BiNode))))   
        {   
            return;   
        }   
        T->data = ch;                            //生成根结点   
        T->lchild = NULL;
        T->rchild = NULL;
        CreateBiTree(T->lchild);                //构造左子树   
        CreateBiTree(T->rchild);                //构造右子树   
    }   

return;   
}   

//*****先序遍历二叉树*****//   
void PreOrderTraverse(BiTree T)   
{   
    stack<BiTree> TreeStack;
    BiTree p = T;

while (p || !TreeStack.empty())
    {
        if (p)
        {
            printf("%c ", p->data);
            TreeStack.push(p);
            p = p->lchild;
        }
        else
        {
            p = TreeStack.top();
            TreeStack.pop();
            p = p->rchild;
        }
    }
}   

//*****中序遍历二叉树*****//   
void InOrderTraverse(BiTree T)   
{   
    stack<BiTree> TreeStack;
    BiTree p = T;

while (p || !TreeStack.empty())
    {
        if (p)
        {
            TreeStack.push(p);
            p = p->lchild;
        }
        else
        {
            p = TreeStack.top();
            printf("%c ", p->data);
            TreeStack.pop();
            p = p->rchild;
        }
    }
}   

//*****后序遍历二叉树*****//   
void PostOrderTraverse(BiTree T)   
{   
    stack<BiTree> TreeStack;
    BiTree p = T;

while (p || !TreeStack.empty())
    {
        if (p)
        {
            p->visitCount = 1;
            TreeStack.push(p);
            p = p->lchild;
        }
        else
        {
            p = TreeStack.top();
            TreeStack.pop();
            if (p->visitCount == 2)
            {
                printf("%c ", p->data);
                p = NULL;
            }
            else
            {
                p->visitCount++;
                TreeStack.push(p);
                p = p->rchild;
            }
        }
    }

//*****层序遍历二叉树*****//
void LevelOrderTraverse(BiTree T)
{
    if (!T)
    {
        return;
    }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/9347b61486d1069c6166b5f531ad9740.html