-
2018-12-26 11:19:12
1.层次遍历
算法思想:建立一个循环队列,先将二叉树头结点如队列,然后出队列,访问该结点,若该结点有左子树则左结点队列,如果有右子树入队列,然后出队访问,直到为空
void level(BTNode *p) { BTNode *queue[maxsize]; int front=0,rear=0; BTNode *q; if(p!=NULL) { rear=(rear+1)%maxsize; queue[rear]=p; while(front!=rear) { front=(front+1)%maxsize; q=queue[front]; cout<<q->data; if(q->lchild!=NULL) { rear=(rear+1)%maxsize; queue[rear]=q->lchild; } if(q->rchild!=NULL) { rear=(rear+1)%maxsize; queue[rear]=q->rchild; } } } }
2.二叉树层次遍历应用之求二叉树的宽度
//对所有结点记录层数,通过层次遍历;最后对所有结点统计每一层的结点数,最大即为所求 typedef struct { BTNode *p; int lno; }St; int maxNode(BTNode *b) { St queue[maxsize];int front=0,rear=0; BTNode *q;int max,Lno,i,j,n; if(p!=NULL) { rear++; queue[rear].p=b; queue[rear].lno=1; while(front!=rear) { front++; q=queue[front].p; Lno=queue[front].lno; if(q->lchild!=NULL) { rear++; queue[rear].p=q->lchild; queue[rear].lno=Lno+1; } if(q->rchild!=NULL) { rear++; queue[rear].p=q->lchild; queue[rear].lno=Lno+1; } } max=0; for(i=1;i<=Lno;i++) { n=0; for(j=1;j<=rear;j++) { if(queue[j].lno==i) n++; if(max<n) max=n; } } } return max; }
更多相关内容 -
层次遍历求二叉树最大宽度
2020-11-08 12:58:45核心思想:二叉树层次i的结点遍历结束后,层次i+1的结点已全部进队,此时队列的元素个数即为层次 i + 1的宽度 难点:如何判断二叉树层次i已经遍历结束呢?可采用一个变量width记录层次i的结点个数,每出队一个元素,...核心思想:二叉树层次i的结点遍历结束后,层次i+1的结点已全部进队,此时队列的元素个数即为层次 i + 1的宽度
难点:如何判断二叉树层次i已经遍历结束呢?可采用一个变量width记录层次i的结点个数,每出队一个元素,变量width减一,当width == 0时,表明层次i遍历完毕。
二叉树层次i遍历结束后(width == 0),只需要用当前队列的元素个数来更新width,表示二叉树层次i + 1的结点个数
int BTWidth(BTNode *b) { if(b == NULL) //为空树,返回宽度为0 return 0; int width, max; int i = 1, max_i; //初始化二叉树层次i,最大宽度所在层次max_i BTNode * p; SqQueue * qu; InitQueue(qu); //初始化层次遍历需要借助的队列 enQueue(qu, b); //树不为空,根节点进队 width = 1; // 宽度置为1 max = width; //最大宽度为1 max_i = i; //最大宽度所在层次 while(!QueueEmpty(qu)) //队列为空,表明二叉树遍历完毕,退出循环 { deQueue(qu, p); //节点出队,赋给p width --; //出队一次,width减1 if(p -> lchild != NULL) //出队节点的左孩子进队 enQueue(qu, p -> lchild); if(p -> rchild != NULL) enQueue(qu, p -> rchild); //出队节点的右孩子出队 if(width == 0) //width == 0,表示当前层次i所有节点已遍历完毕 { //此时队列元素个数即为下一层次 i + 1 的节点个数 width = (qu->rear - qu->front + MaxSize) % MaxSize; //更新宽度 i++; //层次变为下一层 i + 1 if(width > max) //如果层次 i + 1 宽度 > max { max = width; //更新max max_i = i; //并记录最大宽度所在层次 } } } printf("二叉树层次 %d 的宽度最大\n", max_i); return max; }
-
层次遍历获取二叉树的宽度
2020-04-30 13:14:17/** * 2020-04-30 * 当第n层的最后一个结点被访问时,第n+1层的最后一个结点已经入队 */ int getWidthOfBinTree(BTNode T) { if(!T) return; BTNode Q[MAX], last == T; int r, f, max, max_tmp;.../** * 2020-04-30 * 当第n层的最后一个结点被访问时,第n+1层的最后一个结点已经入队 */ int getWidthOfBinTree(BTNode T) { if(!T) return; BTNode Q[MAX], last == T; int r, f, max, max_tmp; r = f = max= max_tmp = 0; Q[++r] = T; while(r != f) { BTNode p = Q[++f]; ++max_tmp; if(p->lChild != NULL) Q[++r] = p->lChild; if(p->rChild != NULL) Q[++r] = p->rChild; if(p == pre) { max = max > max_tmp ? max : max_tmp; max_tmp = 0; last = Q[r]; } } return max; }
-
二叉树的层次遍历、二叉树求宽度、图的广度优先搜索
2021-12-12 21:23:38二叉树的层次遍历、二叉树求宽度、图的广度优先搜索 一类问题,层次遍历思想。 1. 二叉树的层次遍历 /* 1.将根结点入队 2.出队访问出队结点,若有左子树将左子树入队,若有右子树将右子树入队 循环2直到队空。 */ ...二叉树的层次遍历、二叉树求宽度、图的广度优先搜索
一类问题,层次遍历思想。
1. 二叉树的层次遍历
/* 1.将根结点入队 2.出队访问出队结点,若有左子树将左子树入队,若有右子树将右子树入队 循环2直到队空。 */ Status LevelOrder(BiTree T) { queue<BiTree> q; BiTree p; q.push(T); while (q.empty() == false) { p = q.front(); q.pop(); visit(p); if (p->lchild != NULL) q.push(p->lchild); if (p->rchild != NULL) q.push(p->rchild); } }
2. 二叉树求宽度
int GetWidth(BiTree T) { if (T == NULL) return 0; //空树 queue <BiTree> q; BiTree p = T; int maxsize = 1; //根节点为一层 int len; q.push(p); while (q.empty() == false) //保证每次大循环,队列里的结点为某一层的全部结点。 { for (len = q.size(); len > 0; len--) //将当前队列里结点出队,将它们的所有孩子入队 { p = q.front(); q.pop(); if (p->lchild) q.push(p->lchild); if (p->rchild) q.push(p->rchild); } int size = q.size(); //当前层的下一层元素个数 maxsize = max(maxsize, size); } return maxsize; }
3. 图的广度优先搜索
/* 1. 访问,入队 2. 出队,将其所有未访问的邻接点,访问并入队 循环2直到队空。 */ void visit(int v){} void BFS(ALGraph G, int v) //用邻接表表示法宽度优先搜索 { queue<int> q; ArcNode* p; //边结点 int visited[MVNum] = {0}; //访问标记数组,0表示未访问 int w; visit(v); visited[v] = 1; //已访问 q.push(v); while (q.empty() == false) { w = q.front(); q.pop(); for (p = G.vertexes[w].firstarc; p != NULL; p = p->nextarc) { if (visited[p->adjvex] == 0) { visit(p->adjvex); visited[p->adjvex] = 1; q.push(p->adjvex); } } } }
-
二叉树的层次遍历和最大宽度
2018-06-29 18:25:491、二叉树的层次遍历。 二叉树的层序遍历的实现还是比较简单的,由于其层级的关系,很明显要用到队列来辅助实现,主要是从左向右,自上而下,依次将二叉树的各节点入队,这样便可以保证输出的顺序是层序排列的。... -
层次遍历求二叉树的高度(非递归)
2018-08-05 15:43:34所谓层次遍历,是将二叉树中的元素从根节点按照节点层数一层层的输出。 代码如下: int GetDepth(bitreenode *root) { int depth=0; bitreenode *p=root; queue<bitreenode*> q; q.push(p); //... -
C语言用递归法求二叉树的最大宽度并层序遍历输出
2018-04-27 12:20:11C语言用递归法将二叉树层序遍历,并求出最大宽度。文件类型是.cpp的,c的编译器都可以编译。 -
python实现二叉树层次遍历(宽度优先遍历或叫广度优先遍历)
2018-09-04 15:47:58说白了,就是一层一层、由上至下、由左至右的搜索遍历二叉树中的元素。 上面这个二叉树,那么层次遍历的输出应该是:1、2、3、4、5、6、7、8、9 2、解题思路 利用队列,依次将根,左子树,右子树存入... -
18924 二叉树的宽度 —— SCAU 数据结构——根据层次遍历确定树的宽度
2021-04-17 14:27:17C,无复杂代码,无详细注释,自写,请读者视情参考 思想: 利用层次遍历(使用队列),若能记录上一层最后一个节点,那么这一层最后一个节点减去上一层最后一个节点,就是这一层的宽度。 所需知识: C,二叉树,层次... -
二叉树的层次遍历(宽度优先)(C++)
2020-02-22 16:24:05二叉树层次遍历 ...二叉树层次遍历,又称为宽度优先搜索,按照树的层次依次访问树的结点。层次遍历使用队列对遍历结点进行存储,先进入队列的结点,优先遍历拓展其左孩子与右孩子。 1 / 2 5 ... -
数据结构——二叉树的宽度【非递归算法与层次遍历】(C语言)
2020-10-08 11:34:23层次遍历与树的宽度非递归算法求解 #include<stdio.h> #include<stdlib.h> #include<queue> #include <iostream> #define MAXSIZE 10010 #define ElemType int using namespace std; ... -
求二叉树宽度的递归算法
2019-07-05 08:07:06所谓二叉树宽度,就是至每一层节点数多的那一层的节点数 我的算法大致思路是: ...最后遍历完求出最大的count即为二叉树宽度,代码很简单如下 int count[100]; int MAX=-1; void FindWidth(BitNode T,int k) { if(... -
C++ 二叉树层次遍历 宽度优先搜索
2020-03-16 14:16:56二叉树层次遍历,又称为宽度优先搜索,按树的层次依次访问树的节点。层次遍历使用队列对遍历节点进行存储,先进入队列的节点,优先遍历拓展其左孩子与右孩子。 #include<stdio.h> #include<vector> #... -
二叉树的层次遍历(完整版)
2020-07-04 16:47:08二叉树的层次遍历 二叉树的层次遍历也被称为宽度优先遍历(BFS)。可以用递归实现也可以用队列等数据结构实现,下面介绍以uva的trees on the level 为例介绍BFS的完整代码: ... -
利用层次遍历非递归求二叉树高度
2016-09-30 17:47:42利用层次遍历非递归求二叉树高度主要的思想是:一层一层地出队列 — 在我们每次访问完一层时,这时队列中存储的刚好是下一层的所有元素。所以在下一次循环开始时,首先记录该层的元素个数,一次性访问完这一层的所有... -
python实现二叉树层次遍历(BFS)
2022-01-23 22:27:25# 求二叉树路径DFS class TreeNode: def __init__(self, val = None): self.left = None self.right = None self.val = val class BTree: def insert(self,root,node): #构建二叉排序树 if root is None: ... -
求二叉树的层次遍历
2018-01-31 17:17:54已知一颗二叉树的前序遍历和中序遍历,求二叉树的层次遍历。 Input 输入数据有多组,输入T,代表有T组测试数据。每组数据有两个长度小于50的字符串,第一个字符串为前序遍历,第二个为中序遍历。 Output ... -
计算二叉树宽度——层次遍历
2015-04-28 21:01:18统计利用先序遍历创建的二叉树叶结点的个数(0973) Time limit(ms): 1000 Memory limit(kb): 10000 ...利用先序递归遍历算法创建二叉树并计算该二叉树叶结点的个数。先序递归遍历建立二叉树的方法为:按 -
二叉树遍历算法 (递归的、非递归的中序、前序、后序遍历 和 层次遍历 以及 求二叉树的宽度和深度)
2015-09-22 16:44:41二叉树遍历算法 (递归的、非递归的中序、前序、后序遍历 和 层次遍历 以及 求二叉树的宽度和深度) -
使用队列层次遍历实现二叉树可视化(没有树枝)
2022-04-08 21:58:53作为一个数据结果初学者,最近在学习二叉树的过程...首先,我们可以用二叉树的层次遍历,在层次遍历的基础上,每遍历一层,就在末尾输出一个换行,那么就可以将二叉树的基本层次结构输出出来。层次遍历如何实现呢?... -
树的层次遍历(求树的深度、宽度、之字形打印二叉树等等)
2020-04-01 15:49:12对刷题过程中的牵扯到树的层次遍历的代码总结。 1. 基础版,树的层次遍历java代码的实现(利用的是队列): /** * Definition for binary tree with next pointer. * public class TreeLinkNode { * int val; *... -
二叉树广度优先搜索、层次遍历
2020-08-11 21:36:26二叉树的层次遍历 广度优先遍历是按层层推进的方式,遍历每一层的节点。题目要求的是返回每一层的节点值,所以这题用广度优先来做非常合适。 广度优先需要用队列作为辅助结构,我们先将根节点放到队列中,然后不断... -
二叉树的层次遍历算法(C语言版)
2018-11-26 22:53:54借助队列来实现 void LevelOrder(BiTree *bt) { InitQueue(Q); //初始化一个队列Q BiTree *p; //p用来跟踪队头元素 EnQueue(Q,bt); //根节点入队 while(!IsEmpty(Q)) { DeQueue(Q,p);... if(p... -
二叉树层次遍历问题汇总
2021-05-28 23:09:081. 剑指 Offer 32 - I. 从上到下打印二叉树 从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的...【分析】宽度优先搜索BFS /** * Definition for a binary tree node. * struct TreeNode { * int val; * -
二叉树的建立和基础操作<二> —— (层次遍历和计算二叉树的宽度)
2015-07-12 22:25:44考研进行时——二叉树的层次遍历和计算二叉树的宽度 /********************** 先序建立二叉树; 利用C++中的队列实现二叉树的层次遍历; Width()函数返回二叉树的宽度 ******************************************... -
Java遍历二叉树深度宽度
2017-03-23 09:37:00节点数据结构 ...最大深度,基本思路是:使用递归,分别求出左子树的深度、右子树的深度,两个深度的较大值+1就是最大深度。 // 获取最大深度 public static int getMaxDepth(TreeNode ...