非递归算法，以孩子兄弟为存储结构的计算树的深度 这个程序什么意思 该怎么理解
14．[题目分析]由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一子女为空，高度为1和兄弟子树的高度的大者；否则，高度为第一子女树高度加1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。int Height(CSTree bt) //递归求以孩子兄弟链表表示的树的深度{int hc,hs; if (bt==null) return (0);elseif (!bt->firstchild) return (1+height(bt->nextsibling);//子女空，查兄弟的深度else // 结点既有第一子女又有兄弟，高度取子女高度+1和兄弟子树高度的大者{hc=height(bt->firstchild)； //第一子女树高hs=height(bt->nextsibling)；//兄弟树if(hc+1>hs)return(hc+1); elsereturn (hs); }}//结束heightint height(CSTree t) //非递归遍历求以孩子兄弟链表表示的树的深度{if(t==null) return(0);else{int front=1,rear=1; //front,rear是队头队尾元素的指针int last=1,h=0; //last指向树中同层结点中最后一个结点，h是树的高度Q[rear]=t; //Q是以树中结点为元素的队while(frontfirstchild) Q[++rear]=t->firstchild; //第一子女入队t=t->nextsibling; //同层兄弟指针后移}if(front>last) //本层结束，深度加1（初始深度为0）h++;last=rear;} //last再移到指向当前层最右一个结}//while(front<=last)}//else }//Height
太深，建 议搜一搜百度
首先树的儿子会有很多的，为了解决儿子很多且不定的情况：也采用二叉树的存储结构类型，但做了一点改进：
左节点vp表示大儿子，右节点hp表示兄弟，这样“树”就变成“二叉树”
的结构了。 右节点串在一起，表示同一层。
另要搞懂队列，是数组做的循环队列qu[ ], 头front ,尾rear;
又增加一个数组 level [ ]是队列qu[ ]的辅助单元, 存放 队列节点的层号，两数组
下标是一一对应的；
这两个概念是基础，一定要懂。不懂是看不下去的。
算法的核心：
1. 用队列的方法遍历所有节点，从队列中取出一个节点指针进行访问，同时
取出层号，并把这个节点的所有子节点及它的层号放入队列，以便以后取出访问;
为了启动遍历，初始队列须压入根节点；
2. 遍历时知道这个节点层号(m)，就可比较，最大值(max)就是树的深度。
3. 遍历访问一个节点时，左节点vp就是大儿子，属下一层，层号是m+!,
右节点开始就是同层兄弟（第二个while就是)，须压入队列，层号仍是m+1;
4. 反复循环取出队列中节点进行访问（直到为空），并把它的把有儿子压入队列
以便再次访问；
这个经典算法，不复杂， 有不明白的再追问
...B是T所对应的二叉树。在B中,X是其双亲的右孩子,下列正确()_百度知...
高时间效率：算法的执行时间越短，时间效率越高。 果。高空间效率：算法执行时占用的存储空间越少，空间效率越高。可读性：算法的可读性有利于人们对算法的理解。2.4：度量算法的时间效率，时间复杂度，（课本39页）。2.5：递归定义：即用一个概念本身直接或间接地定义它自己。递归定义有两个条件...
Pascal算法之回溯及递推详细介绍、
例2:n皇后问题的递归算法如下:程序1:program hh;const n=8;var i,j,k:integer; x:array[1..n] of integer;function place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then place:=false ; end;...
树- 线索二叉树 (四)
② 该算法的时间复杂性为O(n) 因为是非递归算法 常数因子上小于递归的遍历算法 因此 若对一棵二叉树要经常遍历 或 查找结点在指定次序下的前趋和后继 则应采用线索链表作为存储结构为宜 ③ 以上介绍的线索二叉树是一种全线索树(即左右线索均要建立) 许多应用中只要建立左右线索中的一种 ④ 若在...
PHP怎么递归
下面我举一个其他的例子，虽然不是族谱，但是原理都是一样的。在一些复杂的系统中，要求对信息栏目进行无限级的分类，以增强系统的灵活性。那么PHP是如何实现无限级分类的呢？我们在本文中使用递归算法并结合mysql数据表实现无限级分类。递归，简单的说就是一段程序代码的重复调用，当把代码写到一个自定义...
C++ 解决圆桌骑士问题
兰斯洛特在巫师的欺骗下和佩莱斯的公主伊莱恩结合并产下一子,取名加拉哈德,那个孩子在幼时就遇到过同样的圣杯显圣,并由持杯的少女宣布成年后会由他坐上...递归算法。#include <iostream>using std::cout;using std::endl;using std::cin;int count = 0;int pair_num;int oppo[66][2];void round(int*...
jsp目录树 连数据库的 谢谢了
JSP页面文件目录树源码(递归算法)<%@ page contentType="text\/html; charset=gb2312" language="java" import="java.sql.*" errorPage="" %><!--function MM_goToURL() { \/\/v3.0 var i, args=MM_goToURL.arguments; document.MM_returnValue = false; for (i=0; i<(args.length-1); i+=2...
求北邮 数据结构期末考试试题
5.一组记录的关键码为(46,79,56,38,40,84),则采用快速排序的方法,以第一个记录为基准得到的一次划分结果为 。 A.38,40,46,56,79,84 B.40,38,46,79,56,84 C.40,38,46,56,79,84 D.40,38,46,84,56,79n 参考答案 C6.若一个问题的求解既可以用递归算法,也可以用递推算法,则往往用 (1) ...
已知一棵二叉树是以二叉链表的形式存储的求出以T为根的子树的结点个数...
已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下:structnode{intdata;structnode*left;structnode*right;};要求写出2个具有下面功能的算法:①...5.普通树转换成二叉树:凡是兄弟就用线连起来,然后去掉父亲到儿子的连线,只留下父母到其第一个子女的连线。 6.二叉树的遍历运算(递归定义) (1)先序...
应用问题求解,加油站有效加油位问题!
M=20，根据 0-1 背 包动态规划的递推式求出最优解。2.按要求完成以下关于排序和查找的问题。①对数组 A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所...
急!(最后半天了)!!学过C++的请进
1.\/\/x1为起点x坐标，x2为终点x坐标,因为是横线，所以只有一个y坐标 void Line(int x1, int x2, int y){ if(x1 < x2)Line(x1 + 1, x2, y);SetPixel(x1, y);\/\/此为画点函数，在(x1,y)处画点，把你自己的画点函数替换就可以了 } 2.int MaxFactor(int x, int y, int& ...
蓝骆复方： 14.[题目分析]由孩子兄弟链表表示的树,求高度的递归模型是:若树为空,高度为零;若第一子女为空,高度为1和兄弟子树的高度的大者;否则,高度为第一子女树高度加1和兄弟子树高度的大者.其非递归算法使用队列,逐层遍历树,取得树...
卢湾区18768773536： 非递归算法,以孩子兄弟为存储结构的计算树的深度 这个程序什么意思 该怎么理解 - ？
蓝骆复方： 首先树的儿子会有很多的,为了解决儿子很多且不定的情况:也采用二叉树的存储结构类型,但做了一点改进: 左节点vp表示大儿子,右节点hp表示兄弟,这样“树”就变成“二叉树” 的结构了. 右节点串在一起,表示同一层. 另要搞懂队列...
卢湾区18768773536： 求树的遍历算法,高手赐教~~ - ？
蓝骆复方： 使用孩子兄弟链表作为树的数据结构:每个结点有两个分支,左分支代表该结点的第一个孩子,右分支代表该结点的下一个兄弟.这样就可以将树转化为与二叉树类似的数据结构 该数据结构的C代码如下: typedef struct CSNode { ElemType ...
卢湾区18768773536： 数据结构知识归纳？
蓝骆复方： 第一章:数据结构概述 一、什么是数据结构 1、作者开篇谈到: 一般来说解决一个具体的问题时,大致需要经过下列几个步骤:首先要从具体的问题抽象出一个适当的数学模型,然后设计一个解此数学模型的算法,最后编写出程序代码,进行...
卢湾区18768773536： 设树采用孩子兄弟表示法存放,用类C语言设计算法计算树的高度. - ？
蓝骆复方： 采用递归求解,先求左子树的高度和右子树的高度,然后整棵树的高度就是两颗子树高度的最大值+1.假定叶子节点高度为0.代码如下: struct node {int val;struct node* left;struct node* right; };int height(struct node* root) {int h, lh, rh;if ( root...
卢湾区18768773536： 什么是“孩子兄弟表示法”(请不要给我发代码,我想了解一下原理),谢谢 - ？
蓝骆复方： 就是说,在树的存储结构中,每个节点有三个域,一个存储此节点的数据,一个指向此节点的第一个孩子节点的指针,另一个指向此节点的下一个兄弟的节点指针!!!!说的简单点,就是通过查找节点的孩子,兄弟来存储!!!!
卢湾区18768773536： 一棵采用孩子兄弟表示法存储的树,设计算法,按层次依次输出该树的所有结点用队列啊 - ？
蓝骆复方：[答案] 1.输出根 2.将根进队列保存,将指针移到该根的右孩子. 3.指针不为空则重复1,2一直到指针为空 4.如果队列不为空,则出队列头,指针移到队列头的左孩子,重复1-4直到队列为空
卢湾区18768773536： 图的邻接表的构建算法、图的深度优先遍历搜索递归算法、图的广度优先遍历搜索非递归算法. - ？
蓝骆复方： //第一次深度优先遍历建立finished数组 if(!visited[v]) DFS1(G,v); 分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块
卢湾区18768773536： 一棵采用孩子兄弟表示法存储的树,设计算法,按层次依次输出该树的所有结点？
蓝骆复方： 1.输出根 2.将根进队列保存,将指针移到该根的右孩子. 3.指针不为空则重复1,2一直到指针为空 4.如果队列不为空,则出队列头,指针移到队列头的左孩子,重复1-4直到队列为空
