二叉树的层次遍历及求节点个数的算法

古城微笑少年丶 2023-10-17 16:28 4阅读 0赞

**（1）访问根结点，并将根结点入队；**

**（2）当队列不空时，重复下列操作：**

**从队列退出一个结点；**

**若其有左孩子，则访问左孩子，并将其左孩子入队；**

**若其有右孩子，则访问右孩子，并将其右孩子入队；**

**![SouthEast][]**

**\#include<stdio.h>  
\#include<stdlib.h>  
typedef struct binode  
\{  
char data;  
struct binode \*lchild,\*rchild;  
\}binode,\*bitree; //定义树结点结构  
typedef struct queuenode  
\{  
bitree ch;  
struct queuenode \*next;  
\}queuenode,\*queueptr; //定义队列结点结构  
typedef struct  
\{  
queueptr front;  
queueptr rear;  
\}linkqueue; //定义队列指针  
//建树  
int createbitree(bitree &T,int &sum)  
\{  
char ch;  
scanf("%c",&ch);  
if(ch=='\#') //当输入为\#时树为空  
T=NULL;  
else  
\{  
if(!(T=(bitree)malloc(sizeof(binode))))  
return 0;  
T->data=ch;  
sum++;  
createbitree(T->lchild,sum);  
createbitree(T->rchild,sum);  
\}  
return 1;  
\}  
//初始化一个带头结点的队列  
void initqueue(linkqueue &q)  
\{  
q.front=q.rear=(queueptr)malloc(sizeof(queuenode));  
q.front->next=NULL;  
\}  
//入队列  
void enqueue(linkqueue &q,bitree p)  
\{  
queueptr s;  
int first=1;  
s=(queueptr)malloc(sizeof(queuenode));  
s->ch=p;  
s->next=NULL;  
q.rear->next=s;  
q.rear=s;  
\}  
//出队列  
void dequeue(linkqueue &q,bitree &p)  
\{  
char data;  
queueptr s;  
s=q.front->next;  
p=s->ch;  
data=p->data;  
q.front->next=s->next;  
if(q.rear==s)  
q.rear=q.front;  
free(s);  
printf("%c ",data);  
\}  
//判断队列是否为空  
int queueempty(linkqueue q)  
\{  
if(q.front->next==NULL)  
return 1;  
return 0;  
\}  
//按层次遍历树中结点  
void traverse(bitree bt)  
\{  
linkqueue q;  
bitree p;  
initqueue(q);  
p=bt;  
enqueue(q,p);  
while(queueempty(q)!=1)  
\{  
dequeue(q,p);  
if(p->lchild!=NULL)  
enqueue(q,p->lchild);  
if(p->rchild!=NULL)  
enqueue(q,p->rchild);  
\}  
printf("\\n");  
\}  
//主函数  
int main()  
\{  
int n=0;  
bitree bt;  
createbitree(bt,n);  
printf("该二叉树共有%d个结点.\\n",n);  
printf("按层次遍历树中结点其输出顺序为:\\n");  
traverse(bt);  
return 0;  
\}**

**输入\# 树为空 输入回车结束**

**代码已实现 运行结果如下：**

**![SouthEast 1][]**

**转载请注明出处**

http://m.blog.csdn.net/printf88

[SouthEast]: https://img-blog.csdn.net/20171023131505028?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcHJpbnRmODg=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20171023131917915?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcHJpbnRmODg=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast