C语言数据结构二叉树的层序、先序、中序、后序遍历（完整代码）-创新互联

先序、中序、后序遍历相似，区别在输出和递归顺序。

层次遍历需要用到队列，原理是：把根节点入队，如果队列里不为空->出队输出 结点内容->如果左孩子不为空,入队；右孩子不为空，入队。在队不为空的条件下进行循环。

完整代码在下面，可以运行嗷

#include#includetypedef struct BiTNode
{char data;
    struct BiTNode *rchild,*lchild;
}BiTNode,*BiTree;

//队列的结构体 为层序遍历定义
typedef struct queue
{BiTNode arr[50]; //开50数组
    int front,rear;
}Queue;

//前序遍历输入二叉树
void creattree(BiTree *T)
{char ch;
    scanf("%c",&ch);
    if(ch=='#')
    {*T=NULL;
    }
    else
    {*T=(BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(0);
         (*T)->data=ch;
         creattree(&(*T)->lchild);
         creattree(&(*T)->rchild);
    }
}

//前序遍历
void pretra(BiTree T)
{if(T==NULL)
        return;
    printf("%c",T->data);
    pretra(T->lchild);
    pretra(T->rchild);
}

//中序遍历
void intra(BiTree T)
{if(T==NULL)
        return;
    intra(T->lchild);
    printf("%c",T->data);
    intra(T->rchild);
}

//后序遍历
void posttra(BiTree T)
{if(T==NULL)
        return;
    intra(T->lchild);
    intra(T->rchild);
    printf("%c",T->data);
}

void initequeue(Queue *q)
{q->front=0;
    q->rear=0;
}
int length(Queue *q)
{return ((q->rear-q->front)%50);
}

int enqueue(Queue *q,BiTNode e)
{if((q->rear+1)%50==q->front)   //判断队列是否满了
    return 0;

    q->arr[q->rear]=e;
    q->rear=(q->rear+1)%50;
    return 1;
}
BiTNode dequeue(Queue *q)
{if(q->rear==q->front)     //判断是否为空
        exit(0);

    BiTNode e;
    e=q->arr[q->front];
    q->front=(q->front+1)%50;
    return e;
}
//层序遍历    需要使用队列
void leveltra(BiTree T)
{if(T==NULL)
    return;

    Queue *Q=(Queue*)malloc(sizeof(Queue));
    initequeue(Q);
    enqueue(Q,*T);
    while (Q->front!=Q->rear)   //如果队列不为空
    {BiTNode x=dequeue(Q);
        printf("%c",x.data);
        if(x.lchild)
        {enqueue(Q,*x.lchild);
        }
        if(x.rchild)
        {enqueue(Q,*x.rchild);
        }
    }

}

int main()
{printf("请以前序顺序输入二叉树，以#隔开\n");
    BiTree T;
    creattree(&T);
    printf("前序输出二叉树\n");
    pretra(T);
    printf("层序输出二叉树\n");
    leveltra(T);
    return 0;
}

此代码是学习数据结构课的笔记，如有建议或错误，请留言哦。谢谢！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧