北京网站制作推广,建盏公司简介,网站建设的有什么需求,嘉兴专业做网站的公司问题描述#xff1a;
给你一个二叉树#xff0c;请你返回其按 层序遍历 得到的节点值。 #xff08;即逐层地#xff0c;从左到右访问所有节点#xff09;。
示例#xff1a; 二叉树#xff1a;[3,9,20,null,null,15,7]
返回其层次遍历结果#xff1a;
[ [3], [9,…问题描述
给你一个二叉树请你返回其按 层序遍历 得到的节点值。 即逐层地从左到右访问所有节点。
示例 二叉树[3,9,20,null,null,15,7]
返回其层次遍历结果
[ [3], [9,20], [15,7] ] 通过
来源力扣LeetCode 二叉树的层序遍历
目录
1.非递归用循环队列 2.递归实现层次遍历
在栈与队列匹配问题都是栈的强项中提到「递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中」然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因。
知识前提循环队列二叉树的基本运算
非递归用循环队列
//思路 进行层次遍历时构建一个辅助队列先将二叉树根节点入队然后出队访问出队结点若它有左子树将左子树根节点入队然后出队访问出队结点…右子树也同样如此循环往复直到队列为空
1.构建好辅助队列Q和二叉树T 2.首先将二叉树的T根节点入队列 3.进入while循环退出条件 队列为空 4.循环内部首先将队列中的队首元素出栈并且输出他的值 若队首元素刚刚出队的元素有左子树将其左子树入队 若队首元素刚刚出队的元素有右子树将其右子树入队 详细代码可直接运行
补充如何让输出为一层一行
方法说起来很简单只要仔细想应该都能想出这种方法来。
定义两个变量curLevelCount和nextLevelCount来分别保存当前层和下一层的结点数。
显然curLevelCount的初始值为1因为只有一个根结点而nextLevelCount由于未知故置为0.
思路 1.输出一行一行的与之前输出为一行的代码大体相似 2.构建好辅助队列Q和二叉树T 3.再定义两个变量curLevelCount用于记录当前层次结点个数nextLevelCount用于记录当前层次的下一层结点的个数 4.将二叉树的根节点入栈同时curLevelCount1nextLevelCount0 5.进入while循环退出条件 队列为空 6.循环内部首先将队列中的队首元素出栈并且输出他的值与此同时将curLevelCount–) 若队首元素刚刚出队的元素有左子树将其左子树入队.(与此同时将nextLevelCount); 若队首元素刚刚出队的元素有右子树将其右子树入队.与此同时将nextLevelCount); 若curLevelCount减到零输出一个换行符将nextLevelCount赋值给curLevelCount nextLevelCount0 代码非递归用循环队列
#includestdio.htypedef int Status;
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
#includemalloc.h
#includestdlib.h
#includestdio.h
#includebits/stdc.h typedef char TElemType;
typedef int status;
typedef struct BiNode
{TElemType data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;
typedef BiTree ElemType;
typedef BiTree QElemType;
//----------循环队列 --顺序存储结构-----------------------
#define MAXQSIZE 100 // 最大队列长度1
typedef struct {ElemType *base; // 初始化的动态分配存储空间int front; // 头指针若队列不空指向队列头元素int rear; // 尾指针若队列不空指向队列尾元素的下一个位置
} SqQueue;
void InitQueue(SqQueue Q)
{ // 构造一个空队列QQ.base (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));if(!Q.base) // 存储分配失败exit(0);Q.front Q.rear 0;
}
void DestroyQueue(SqQueue Q)
{ // 销毁队列QQ不再存在if(Q.base)free(Q.base);Q.base NULL;Q.front Q.rear 0;
}
int QueueLength(SqQueue Q)
{return ((Q.rear-Q.frontMAXQSIZE)%MAXQSIZE);
}
Status EnQueue(SqQueue Q, QElemType e)
{ // 插入元素e为Q的新的队尾元素if((Q.rear 1) % MAXQSIZE Q.front) // 队列满return ERROR;Q.base[Q.rear] e;Q.rear (Q.rear 1) % MAXQSIZE;return OK;
}
Status DeQueue(SqQueue Q, QElemType e)
{ // 若队列不空则删除Q的队头元素用e返回其值// 并返回OK否则返回ERRORif(Q.front Q.rear) // 队列空return ERROR;e Q.base[Q.front];Q.front (Q.front 1) % MAXQSIZE;return OK;
}
Status GetHead(SqQueue Q, QElemType e)
{ // 若队列不空则用e返回Q的队头元素并返回OK// 否则返回ERRORif(Q.front Q.rear) // 队列空return ERROR;e Q.base[Q.front];return OK;
}
Status QueueEmpty(SqQueue Q)
{// 若队列Q为空队列则返回TRUE否则返回FALSEif(Q.front Q.rear) // 队列空的标志return TRUE;elsereturn FALSE;
}
void traverse(SqQueue Q)
{int x;xQ.front;int numQueueLength(Q);for(int i0;inum;i){printf(%d--,Q.base[(x)%MAXQSIZE]);}
}void CreateBiTree(BiTree T)//二叉树的先序创建
{TElemType ch;scanf(%c,ch);if(ch#)TNULL;else {T(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);T-datach;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}
}void DestroyBiTree(BiTree T)//二叉树的销毁算法
{if(TNULL)exit(-1);else{DestroyBiTree(T-lchild);DestroyBiTree(T-rchild);free(T);}
}int preorderTraverse(BiTree T)//二叉树的先序递归遍历算法
{if(TNULL)return 0;else {printf(%c ,T-data);preorderTraverse(T-lchild);preorderTraverse(T-rchild);}} int InorderTraverse(BiTree T)//二叉树的中序递归遍历算法
{if(TNULL)return 0;else {InorderTraverse(T-lchild);printf(%c ,T-data);InorderTraverse(T-rchild);}}int PostorderTraverse(BiTree T)//二叉树的后序递归遍历算法
{if(TNULL)return 0;else {PostorderTraverse(T-lchild);PostorderTraverse(T-rchild);printf(%c ,T-data);}}void BiTree_level_traversal1(BiTree T)//按层输出一行
{SqQueue Q;InitQueue(Q);EnQueue(Q,T);BiTree temp;while(!QueueEmpty(Q)){DeQueue(Q, temp);printf(%c ,temp-data);if(temp-lchild!NULL)EnQueue(Q,temp-lchild);if(temp-rchild!NULL)EnQueue(Q,temp-rchild);}} void BiTree_level_traversal(BiTree T)// 层次遍历输入一层一层的
{SqQueue Q;InitQueue(Q);EnQueue(Q,T);BiTree temp;int curLevelCount1,nextLevelCount0; while(!QueueEmpty(Q)){DeQueue(Q, temp);printf(%c ,temp-data);curLevelCount--;if(temp-lchild!NULL){EnQueue(Q,temp-lchild);nextLevelCount;}if(temp-rchild!NULL){EnQueue(Q,temp-rchild);nextLevelCount;}if(curLevelCount0){printf(\n); curLevelCount nextLevelCount;nextLevelCount0;}}} int main()
{BiTree T;printf(创建树输入树T的先序序列(其中使用#代表空节点)\n);CreateBiTree(T);printf(先序遍历算法);preorderTraverse(T);printf(\n中序遍历算法);InorderTraverse(T);printf(\n后序遍历算法);PostorderTraverse(T);printf(\n遍历结果为\n);BiTree_level_traversal1(T);printf(\n一层一层的输出\n); BiTree_level_traversal(T);
}递归实现层次遍历
思路 1.先利用BiTree_height1(BiTree T)求二叉树高度算法求得高度 2.levelOrder( BiTree T)层次遍历递归算法这个函数仅一个for循环用for将二叉树一层一层的输出每一层输出完再输出一个换行符。 3.printNodeAtLevel(BiTree T,int level)真正的递归遍历输出函数。 若level0输入此时的T-data; int BiTree_height1(BiTree T)//求树的深度算法1
{if(TNULL)return 0;else{if(BiTree_height1(T-lchild)BiTree_height1(T-rchild))return 1BiTree_height1(T-lchild);elsereturn 1BiTree_height1(T-rchild);}}
void printNodeAtLevel(BiTree T,int level)
{ if(TNULL||level0) return; if(level0) { printf(%c ,T-data);return; } // 左子树的 level - 1 级 printNodeAtLevel(T-lchild,level-1); // 右子树的 level - 1 级 printNodeAtLevel(T-rchild,level-1);
}void levelOrder(const BiTree T)
{if(TNULL)return;int totalLevel BiTree_height1(T);for(int i 0; i totalLevel; i){printNodeAtLevel(T, i);printf(\n);//打印完一层换行}
} 代码递归实现全部代码
#includestdio.h
#includebits/stdc.h typedef char TElemType;
typedef int status;
typedef struct BiNode
{TElemType data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;
void CreateBiTree(BiTree T)//二叉树的先序创建
{TElemType ch;scanf(%c,ch);if(ch#)TNULL;else {T(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);T-datach;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}
}void DestroyBiTree(BiTree T)//二叉树的销毁算法
{if(TNULL)exit(-1);else{DestroyBiTree(T-lchild);DestroyBiTree(T-rchild);free(T);}
}int preorderTraverse(BiTree T)//二叉树的先序递归遍历算法
{if(TNULL)return 0;else {printf(%c ,T-data);preorderTraverse(T-lchild);preorderTraverse(T-rchild);}} int InorderTraverse(BiTree T)//二叉树的中序递归遍历算法
{if(TNULL)return 0;else {InorderTraverse(T-lchild);printf(%c ,T-data);InorderTraverse(T-rchild);}}int PostorderTraverse(BiTree T)//二叉树的后序递归遍历算法
{if(TNULL)return 0;else {PostorderTraverse(T-lchild);PostorderTraverse(T-rchild);printf(%c ,T-data);}}int BiTree_height1(BiTree T)//求树的深度算法1
{if(TNULL)return 0;else{if(BiTree_height1(T-lchild)BiTree_height1(T-rchild))return 1BiTree_height1(T-lchild);elsereturn 1BiTree_height1(T-rchild);}}
void printNodeAtLevel(BiTree T,int level)
{ if(TNULL||level0) return; if(level0) { printf(%c ,T-data);return; } // 左子树的 level - 1 级 printNodeAtLevel(T-lchild,level-1); // 右子树的 level - 1 级 printNodeAtLevel(T-rchild,level-1);
}void levelOrder(const BiTree T)
{if(TNULL)return;int totalLevel BiTree_height1(T);for(int i 0; i totalLevel; i){printNodeAtLevel(T, i);printf(\n);//打印完一层换行}
} int main()
{BiTree T;printf(创建树输入树T的先序序列(其中使用#代表空节点)\n);CreateBiTree(T);printf(先序遍历算法);preorderTraverse(T);printf(\n中序遍历算法);InorderTraverse(T);printf(\n后序遍历算法);PostorderTraverse(T);printf(\n二叉树层次遍历算法\n);levelOrder(T);}
