数据结构二叉树的层次遍历c/c++实现-创新互联

目录

在沿滩等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供成都网站建设、网站制作 网站设计制作按需策划,公司网站建设,企业网站建设,高端网站设计,营销型网站建设,外贸营销网站建设,沿滩网站建设费用合理。

1.首先补充点我在这里用到的一些基本结构以及补充操作:

1.1树的结构:

1.2入队操作:

1.3出队操作

1.4初始化操作

1.5队列判空

1.6 队列判满

2.二叉树层次遍历代码实现,假设给定一棵树T(树的结构如上)

3. 层次遍历算法思路分析


1.首先补充点我在这里用到的一些基本结构以及补充操作:
1.1树的结构:
typedef char ElemType;
typedef struct BiTNode
{ ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
1.2入队操作:
void SQ_In(SqQueue &Q, QElemType e)
// 将e入队。即:插入元素e为Q的新的队尾元素。
{
   	if(SQ_IsFull(Q)) return;//队满
	Q.elem[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;
}
1.3出队操作
void SQ_Out(SqQueue &Q, QElemType &e)
// 从队列Q出队一个元素,即:删除Q的队头元素,用e返回其值。
{
    if(SQ_IsEmpty(Q)) return; //队空
	e=Q.elem[Q.front];Q.front=(Q.front+1)%MAXSIZE;
}
1.4初始化操作
void SQ_Initiate(SqQueue &Q)
// 顺序队列的初始化,即构造一个空的顺序队列
{
	Q.elem = (QElemType*)malloc(sizeof(QElemType)*MAXSIZE);
	Q.front=Q.rear=0;
}
  1.5队列判空
bool SQ_IsEmpty(SqQueue Q)
// 判断顺序队列是否为空,为空返回true,否则返回false。
{
	return Q.front==Q.rear;	
}
1.6 队列判满
bool SQ_IsFull(SqQueue Q)
// 判断顺序队列是否为满,为满返回true,否则返回false。
{
	return (Q.rear+1)%MAXSIZE==Q.front;	
}

2.二叉树层次遍历代码实现,假设给定一棵树T(树的结构如上)
void HierarchyOrder(BiTree T)
// 二叉树的层次遍历(借助队列实现)
// 参数:二叉树根指针T
// 输出:二叉树的层次遍历,中间没有空格,末尾不换行。
{
    // 请在这里补充代码,完成本关任务
    SqQueue Q;//定义队列
	SQ_Initiate(Q);//初始化队列
	if(T!=NULL){
		SQ_In(Q,T);//入根,用T来保存入队的元素
	}
	while(!SQ_IsEmpty(Q)){
		 SQ_Out(Q,T);//用T来保存出队的元素
		printf("%c",T->data);
		if(T->lchild!=NULL)
			SQ_In(Q,T->lchild);//入根,用T的左孩子来保存T的左孩子结点
		
		if(T->rchild!=NULL)
			SQ_In(Q,T->rchild);//入根,用T的右孩子来保存T的右孩子结点
	}
}
3. 层次遍历算法思路分析
  1. 借助队列来实现对二叉树的层次遍历,队列每出一个根,就进入两个对应的它的左右孩子,再将这两个左右孩子当作根,出去,然后再分别进入这两个左右孩子的左右孩子,依次类推。
  2. 此处,我们用T表示二叉树的根节点,出谁的时候,T 的指针就会移动到哪里,假设根节点是A,那么第一次首先是A,然后入队A的左右孩子。每出一个根,此时T的指针就指向谁,此时同时入队谁的左右孩子,顺序就不会错。

  3. 上面那个代码实现,看似T的指针好像一直没有更新,但仔细观察队列的出队和入队的函数,会发现,每次出/入队的时候,都会用T保存已经出队或入队的元素地址,以此来完成对根节点指针T的更新。   

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

本文名称:数据结构二叉树的层次遍历c/c++实现-创新互联
本文链接:https://www.cdcxhl.com/article0/joioo.html

成都网站建设公司_创新互联,为您提供外贸网站建设网站改版品牌网站制作标签优化建站公司用户体验

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

成都做网站