【算法练习八】二叉树的分层遍历

代码难点:
    第一点:先将初始化过得数组,变成符合规范的二叉树(规范:双亲结点大于左子树,小于右子树)的过程;
    第二点:存储结点的队列,只要输出一个结点,就将它的左右子树按照顺序存储的队列中,这样,当遍历完这一层的右半边时,可以回到下一行的最左边的结点;


代码难点解释:
    第一点:
        A>首先建立根结点,赋给BitTree *bt;
        B>之后使用for循环建立剩下的结点,BitTree *p用来表示,需要建立的结点,并将根结点bt赋给head;
        C>BitTree *parent表示双亲结点,进入while循环,用来找到可以放置新建p的父亲结点;
        D>先将head赋给双亲结点parent,在判断p与head的数据域大小,如果p->data<head->data,说明新建结点p在head结点的左子树部分,否则为右子树部分;
        E>一直到head为空,while条件不满足,说明head已经到了叶子结点,该结点没有左右子树,将这个这个结点赋给双亲结点;
        F>之后新建结点p再与双亲结点parent比较大小,如果双亲结点parent的数据域data大于新建结点的数据域data,则新建结点p的位置为双亲结点的的左子树,否则为右子树;
        G>之后按照上述步骤,进行for循环,直到退出循环,给主函数返回二叉树的根结点bt,这样一个二叉树就建立好了;
    第二点:
        A>定义一个BitTree *p表示shu要输出的结点,BitTree **Q表示队列,用来存储二叉树结点的地址,先将根结点存入队列;
        B>用一个while循环判断分层遍历是否完成,只要队列为空,就表示已经完成分层遍历,while循环条件不成立;
        C>进入出队元素赋给p,之后输出这个结点的数据域,这是第一层;
        D>之后将结点p的左子树存入队列中,没有就不存,在存p的右子树到队列中,没有就不存;
        E>第一次循环结束,判断while条件,条件成立,继续循环,将队头元素赋给p,并输出p的数据域;
        F>队列的特点:队头输出,队尾输入,先进先出,所以刚刚先进的是根结点的左子树,所以先输出左子树的数据域,并将p的左右子树存入到队列中;
        G>循环上述的DEF部分,知道while循环不成立退出循环,结束整个Level函数,返回主函数,继续执行代码;

#include<stdio.h>
#include<stdlib.h>
#define N 10 //初始化结点个数;

//结点类型;
typedef struct tree
{
int data; //数据域;
struct tree *lchild; //指针类型的左子树;
struct tree *rchild; //指针类型的右子树;
}BitTree;

BitTree *Create(int a[])
{
BitTree *bt,*head,*parent,*p;
//建立根结点;
bt=(BitTree *)malloc(sizeof(BitTree));
bt->data=a[0];
bt->lchild=bt->rchild=NULL;

//建立剩下的结点;
for(int i=1;i<N;i++)
{
//p表示当前需要建立的结点;
p=(BitTree *)malloc(sizeof(BitTree));
p->data=a[i];
p->rchild=p->lchild=NULL;

head=bt;
//找到要这个结点要插入的位置;
//找到的插入位置为叶子结点;
while(head) //head和parent两指针联动;
{
parent=head; //将指针head的指向赋给指针parent的指向;
if(p->data<head->data) //如果需要建立二叉树的结点小于当前结点;
head=head->lchild; //就需要改变当前结点,只是改变后的结点数据域小于原先head结点的数据域;
else //如果需要建立二叉树的结点大于当前结点;
head=head->rchild; //同样需要改变当前结点,只是改变后的结点数据域大于原先的head结点的数据域;
} //结束循环,找到指针判所对应的双亲结点 ==> parent;

if(p->data<parent->data) //如果指针p的数据域小于双亲结点;
parent->lchild=p; //则p为双亲结点的左子树;
else
parent->rchild=p; //否则,p为双亲结点的右子树;
}
return bt; //返回建立好的二叉树根结点;
}

//层次遍历二叉树,用队列来实现
void Level(BitTree *bt)
{
BitTree *p; //待输出结点;
BitTree **Q; //指向队列;
int front,rear; //队首指针,队尾指针;
//声明队列;
Q=(BitTree **)malloc(sizeof(BitTree *));
//初始化队列;
front=rear=0;
Q[++rear]=bt; //将树根存入;
//按层输出;
while(front-rear) //循环条件:栈不为空;
{
p=Q[++front]; //队头出元素;
printf(“%d “,p->data); //输出出队的指针的数据域;
if(p->lchild) //如果当前指针p指向结点的左子树不为空;
Q[++rear]=p->lchild; //就将这个结点的左子树入队;
if(p->rchild) //如果当前指针p指向结点的右子树不为空;
Q[++rear]=p->rchild; //就将这个结点的右子树入队;
}
}

int main(void)
{
int data[N]={3,2,5,8,4,7,6,9,1,2};
printf(“数组的数据集合为: \n”);
for(int i=0;i<N;i++)
printf(“%d “,data[i]);
printf(“\n\n”);
BitTree *bt=Create(data);
printf(“分层遍历后的结果为: \n”);
Level(bt);
printf(“\n”);
return 0;
}


							

发表评论

电子邮件地址不会被公开。 必填项已用*标注