二叉树的遍历(C语言)

递归遍历

#include 
#include 
#include

typedef int  Elemtype;

typedef struct BiTNode  //树结点
{
    Elemtype data;
    struct BitTNode *lchild,*rchild; //指向左右子树的指针
} BiTNode,*BiTree;


BiTree CreateLink() //二叉树的递归创建
{
    int data;

    BiTree T;

    scanf("%d",&data);//读入当前结点
    if(data==-1)
    {
        return NULL;
    }
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data=data;

        printf("请输入%d的左子树: ",data); //读入最左结点
        T->lchild=CreateLink();
        printf("请输入%d的右子树: ",data);//读入右结点
        T->rchild=CreateLink();
        return T;
    }
}

void visit(BiTree T)
{
    printf("%d  ",T->data);
}

//先序遍历
void PreOrder(BiTree T)
{
    if(T!=NULL)
    {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//中序遍历
void InOrder(BiTree T)
{
    if(T!=NULL)
    {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

void PostOrder(BiTree T)
{
    if(T!=NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}


int main()
{

    BiTree T;
    printf("请输入根节点数据: ");
    T=CreateLink();// 1 2 -1 4 6 -1 -1 -1 3 -1 5 -1 -1
    PreOrder(T);//1 2 4 6 3 5
    printf("\n");
    InOrder(T);// 2 6 4 1 3 5
    printf("\n");
    PostOrder(T);//6 4 2 5 3 1
    printf("\n");





    return 0;
}

非递归遍历

#include 
#include 
#include

#define MaxSize 50

typedef int  Elemtype;


typedef struct BiTNode  //树结点
{
    Elemtype data;
    struct BitTNode *lchild,*rchild; //指向左右子树的指针
} BiTNode,*BiTree;

typedef struct Stack
{
    BiTree data[MaxSize]; 
    int top;
} SqStack;

void InitStack(SqStack *S)
{
    S->top=-1;
}

bool Push(SqStack *S,BiTree T)
{
    if(S->top==MaxSize-1)return false;
    S->data[++S->top]=T;
    return true;
}

bool Pop(SqStack *S,BiTree *T)
{
    if(S->top==-1)return false;
    *T=S->data[S->top--];
    return true;
}

bool IsEmpty(SqStack *S)
{
    if(S->top==-1)return true;
    return false;
}

bool GetTop(SqStack *S,BiTree *T)
{
    if(S->top==-1)return false;
    *T=S->data[S->top];
    return true;
}

BiTree CreateLink() //二叉树的递归创建
{
    int data;

    BiTree T;

    scanf("%d",&data);//读入当前结点
    if(data==-1)
    {
        return NULL;
    }
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data=data;

        printf("请输入%d的左子树: ",data); //读入最左结点
        T->lchild=CreateLink();
        printf("请输入%d的右子树: ",data);//读入右结点
        T->rchild=CreateLink();
        return T;
    }
}

void visit(BiTree T)
{
    printf("%d  ",T->data);
}
//先序遍历(非递归)
void PreOrder(BiTree T)
{
    SqStack S;
    InitStack(&S);
    BiTree p=T;
    while(p||!IsEmpty(&S))
    {
        if(p)
        {
            visit(p);  //与中序遍历拜访位置不同
            Push(&S,p);  //左结点入队
            p=p->lchild;
        }
        else
        {
            Pop(&S,&p); //如果为空遍历右结点
            p=p->rchild;
        }
    }
}


//中序遍历(非递归)
void InOrder(BiTree T)
{
    SqStack S;
    InitStack(&S); //初始化栈S
    BiTree p=T;// p用于遍历

    while(p||!IsEmpty(&S))
    {
        if(p)
        {
            Push(&S,p); //左儿子存在,直接入栈
            p=p->lchild;
        }
        else
        {
            Pop(&S,&p); //左儿子不存在,出栈
            visit(p); //注意visit的位置
            p=p->rchild;
        }
    }
}

//后续遍历(非递归)
void PostOrder(BiTree T)
{
    SqStack S;
    InitStack(&S);
    BiTree p=T,r=NULL;

    while(p||!IsEmpty(&S))
    {
        if(p)
        {
            Push(&S,p); //一直走到树最左端
            p=p->lchild;
        }
        else //向右
        {
            GetTop(&S,&p); // 获取栈顶元素,此时不需要出栈
            if(p->rchild&&p->rchild!=r)
            {
                p=p->rchild; //如果最左侧结点的右子树存在,则继续向右侧遍历
            }
            else//如果不存在则d出该结点
            {
                Pop(&S,&p);
                visit(p);
                r=p;//记录最近访问过的结点
                p=NULL; //访问完后重置p指针,意味着下一次一定执行else
            }
        }
    }

}


int main()
{

    BiTree T;
    printf("请输入根节点数据: ");
    T=CreateLink();// 1 2 -1 4 6 -1 -1 -1 3 -1 5 -1 -1
    PreOrder(T);
    printf("\n");
    InOrder(T);
    printf("\n");
    PostOrder(T);






    return 0;
}

队列层次遍历

#include 
#include 
#include

#define MaxSize 50

typedef int  Elemtype;


typedef struct BiTNode  //树结点
{
    Elemtype data;
    struct BitTNode *lchild,*rchild; //指向左右子树的指针
} BiTNode,*BiTree;


typedef struct SqQueue
{
    BiTree data[MaxSize];
    int front;
    int rear;
} SqQueue;

bool InitQueue(SqQueue *Q)
{
    Q->front=0;
    Q->rear=0;//队尾指向下一个要入队的元素
    return true;
}

bool IsEmpty(SqQueue *Q)
{
    if(Q->front==Q->rear)return true;
    return false;
}


bool EnQueue(SqQueue *Q,BiTree T)
{
    if((Q->rear+1)%MaxSize==Q->front) return false;
    Q->data[Q->rear]=T;
    Q->rear=(Q->rear+1)%MaxSize;
    return true;
}

bool DeQueue(SqQueue *Q,BiTree *T)
{
    if(Q->front==Q->rear)return false;//队空
    *T=Q->data[Q->front];
    Q->front=(Q->front+1)%MaxSize;
    return true;
}

BiTree CreateLink() //二叉树的递归创建
{
    int data;

    BiTree T;

    scanf("%d",&data);//读入当前结点
    if(data==-1)
    {
        return NULL;
    }
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data=data;
        printf("请输入%d的左子树: ",data); //读入最左结点
        T->lchild=CreateLink();
        printf("请输入%d的右子树: ",data);//读入右结点
        T->rchild=CreateLink();
        return T;
    }
}

void visit(BiTree T)
{
    printf("%d  ",T->data);
}

bool QueuePrint(SqQueue *Q)
{
    int i=Q->front;
    while(i!=Q->rear)
    {
        printf("%d-->",Q->data[i]->data);
        i=(i+1)%MaxSize;
    }
    printf("\n");
    return true;
}

//层次遍历
void LevelOrder(BiTree T)
{
    SqQueue Q;
    InitQueue(&Q);
    BiTree p;
    EnQueue(&Q,T);
    while(!IsEmpty(&Q))
    {
        DeQueue(&Q,&p);
        visit(p);
        if(p->lchild!=NULL)
        {
            EnQueue(&Q,p->lchild);
        }
        if(p->rchild!=NULL)
        {
            EnQueue(&Q,p->rchild);
        }
    }
}


int main()
{

    BiTree T;
    printf("请输入根节点数据: ");
    T=CreateLink();// 1 2 -1 4 6 -1 -1 -1 3 -1 5 -1 -1
    LevelOrder(T);






    return 0;
}