精华内容
下载资源
问答
  • 树与二叉树之层次遍历求二叉树宽度
    千次阅读
    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;
    }
    
    展开全文
  • 二叉树层次遍历二叉树求宽度、图的广度优先搜索 一类问题,层次遍历思想。 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:49
    1、二叉树层次遍历。 二叉树的层序遍历的实现还是比较简单的,由于其层级的关系,很明显要用到队列来辅助实现,主要是从左向右,自上而下,依次将二叉树的各节点入队,这样便可以保证输出的顺序是层序排列的。...
  • 所谓层次遍历,是将二叉树中的元素从根节点按照节点层数一层层的输出。 代码如下: int GetDepth(bitreenode *root) { int depth=0; bitreenode *p=root; queue&lt;bitreenode*&gt; q; q.push(p); //...
  • C语言用递归法将二叉树层序遍历,并出最大宽度。文件类型是.cpp的,c的编译器都可以编译。
  •  说白了,就是一层一层、由上至下、由左至右的搜索遍历二叉树中的元素。    上面这个二叉树,那么层次遍历的输出应该是:1、2、3、4、5、6、7、8、9 2、解题思路  利用队列,依次将根,左子树,右子树存入...
  • C,无复杂代码,无详细注释,自写,请读者视情参考 思想: 利用层次遍历(使用队列),若能记录上一层最后一个节点,那么这一层最后一个节点减去上一层最后一个节点,就是这一层的宽度。 所需知识: C,二叉树层次...
  • 二叉树层次遍历 ...二叉树层次遍历,又称为宽度优先搜索,按照树的层次依次访问树的结点。层次遍历使用队列对遍历结点进行存储,先进入队列的结点,优先遍历拓展其左孩子与右孩子。 1 / 2 5 ...
  • 层次遍历与树的宽度非递归算法求解 #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(...
  • 二叉树层次遍历,又称为宽度优先搜索,按树的层次依次访问树的节点。层次遍历使用队列对遍历节点进行存储,先进入队列的节点,优先遍历拓展其左孩子与右孩子。 #include<stdio.h> #include<vector> #...
  • 二叉树层次遍历(完整版)

    千次阅读 2020-07-04 16:47:08
    二叉树层次遍历 二叉树层次遍历也被称为宽度优先遍历(BFS)。可以用递归实现也可以用队列等数据结构实现,下面介绍以uva的trees on the level 为例介绍BFS的完整代码: ...
  • 利用层次遍历非递归求二叉树高度

    万次阅读 多人点赞 2016-09-30 17:47:42
    利用层次遍历非递归求二叉树高度主要的思想是:一层一层地出队列 — 在我们每次访问完一层时,这时队列中存储的刚好是下一层的所有元素。所以在下一次循环开始时,首先记录该层的元素个数,一次性访问完这一层的所有...
  • # 求二叉树路径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 ...利用先序递归遍历算法创建二叉树并计算该二叉树叶结点的个数。先序递归遍历建立二叉树的方法为:按
  • 二叉树遍历算法 (递归的、非递归的中序、前序、后序遍历 和 层次遍历 以及 求二叉树宽度和深度)
  • 作为一个数据结果初学者,最近在学习二叉树的过程...首先,我们可以用二叉树层次遍历,在层次遍历的基础上,每遍历一层,就在末尾输出一个换行,那么就可以将二叉树的基本层次结构输出出来。层次遍历如何实现呢?...
  • 对刷题过程中的牵扯到树的层次遍历的代码总结。 1. 基础版,树的层次遍历java代码的实现(利用的是队列): /** * Definition for binary tree with next pointer. * public class TreeLinkNode { * int val; *...
  • 二叉树层次遍历 广度优先遍历是按层层推进的方式,遍历每一层的节点。题目要求的是返回每一层的节点值,所以这题用广度优先来做非常合适。 广度优先需要用队列作为辅助结构,我们先将根节点放到队列中,然后不断...
  • 二叉树层次遍历算法(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...
  • 1. 剑指 Offer 32 - I. 从上到下打印二叉树 从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的...【分析】宽度优先搜索BFS /** * Definition for a binary tree node. * struct TreeNode { * int val; *
  • 考研进行时——二叉树层次遍历和计算二叉树宽度 /********************** 先序建立二叉树; 利用C++中的队列实现二叉树层次遍历; Width()函数返回二叉树宽度 ******************************************...
  • 节点数据结构 ...最大深度,基本思路是:使用递归,分别出左子树的深度、右子树的深度,两个深度的较大值+1就是最大深度。 // 获取最大深度 public static int getMaxDepth(TreeNode ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,084
精华内容 1,233
关键字:

层次遍历求二叉树的宽度

友情链接: akaqaaxz.zip