当前位置: 首页 > news >正文

安徽省住房和城乡建设厅官方网站短期职业技能培训班

安徽省住房和城乡建设厅官方网站,短期职业技能培训班,公众号运营app,设计品牌网站公司参考资料: DFS 参考文章BFS 参考文章DFS 参考视频二叉树遍历规律递归原理源码N叉树规律总结: 由前面二叉树的遍历规律和递归的基本原理,我们可以看到,二叉树遍历口诀和二叉树递推公式有着紧密的联系 前序遍历:F(x…

参考资料:

  • DFS  参考文章
  • BFS  参考文章
  • DFS  参考视频
  • 二叉树遍历规律
  • 递归原理
  • 源码

N叉树规律总结:

由前面二叉树的遍历规律和递归的基本原理,我们可以看到,二叉树遍历口诀和二叉树递推公式有着紧密的联系

 前序遍历:F(x) = op1(x) & F(x左) & F(x右)                口诀:左右

 中序遍历:F(x) =  F(x左) & op1(x) &F(x右)                口诀:左

 后序遍历:F(x) =  F(x左) & F(x右) & op1(x)               口诀:左右

其中op1(x)表示对数据X的操作

如果上述公式中,将op1(x)看做根,可以发现 递推公式和口诀是一摸一样的

进而我们推断出,3叉树(3并列递归),4叉树(4并列递归)......乃至n叉树(n并列递归)规律都是这样的

3叉树(3并列递归)口诀

 公式1:F(x) = op1(x) & F(x左) & F(x中) & F(x右)              口诀:左中右

 公式2:F(x) =  F(x左) & op1(x) & F(x中) &F(x右)              口诀:左中右

 公式3:F(x) =  F(x左)& F(x中) & op1(x) &F(x右)               口诀:左中

 公式4:F(x) =  F(x左)& F(x中) &F(x右) & op1(x)               口诀:左中右

其中op1(x)表示对数据X的操作

4叉树(4并列递归)口诀

 公式1:F(x) = op1(x) & F(x上) & F(x下) & F(x左)  & F(X右)            口诀:上下左右

 公式2:F(x) =  F(x上) & op1(x) & F(x下) & F(x左)  & F(X右)           口诀:上下左右

 公式3:F(x) =  F(x上) & F(x下) & op1(x) & F(x左)  & F(X右)           口诀:上下左右

 公式4:F(x) =  F(x上) & F(x下) & F(x左) & op1(x) & F(X右)            口诀:上下左

 公式5:F(x) =  F(x上) & F(x下) & F(x左)  & F(X右) & op1(x)           口诀:上下左右

其中op1(x)表示对数据X的操作

 扩展至n叉树(n并列递归)口诀

公式1:F(x) = op1(x) & F(x属性1) & F(x属性2) & ......&F(x属性n) 

口诀:,属性1,属性2,......,属性n


 N叉树规律验证:

由上述总结出的n叉树规律

公式1:F(x) = op1(x) & F(x属性1) & F(x属性2) & ......&F(x属性n) 

口诀:,属性1,属性2,......,属性n

我们用以下三叉树来进行验证,分别进行前中后序三种遍历

 初始化语句:

    //对三叉树进行初始化public TreeNode initNode(){// 先初始化最底层的TreeNode node9 = new TreeNode(9,null, null, null);TreeNode node8 = new TreeNode(8,null, null, null);TreeNode node7 = new TreeNode(7,null, null, null);TreeNode node6 = new TreeNode(6,null, null, null);TreeNode node5 = new TreeNode(5,null, null, null);TreeNode node4 = new TreeNode(4,null, null, null);TreeNode node3 = new TreeNode(3,node9, null, null);TreeNode node2 = new TreeNode(2,null, node7, node8);TreeNode node1 = new TreeNode(1,node4, node5, node6);TreeNode node0 = new TreeNode(0,node1, node2, node3);return node0;}
  •  前序遍历

根据代码:

    public void deepSortOutFont(TreeNode node){if(node == null){return;}System.out.println("前序遍历为:"+node.val);deepSortOutFont(node.left);deepSortOutFont(node.middle);deepSortOutFont(node.right);}

得到公式以及遍历口诀

F(x) = op1(x) & F(x左) & F(x中) & F(x右)              口诀:左中右

  •  从根节点开始,根据口诀:根左中右,得到结果:0,1,2,3
  • 以未遍历的节点1为根,根据口诀:根左中右,即1,4,5,6,得到结果:0,1,4,5,6,2,3
  • 以未遍历的节点2为根,根据口诀:根左中右,即2,null,7,8,得到结果:0,1,4,5,6,2,7,8,3
  • 以未遍历的节点3为根,根据口诀:根左中右,即3,9,null,null,得到结果:0,1,4,5,6,2,7,8,3,9
  • 以未遍历节点4,5,6,7,8,9为根,根据口诀:根左中右,即n,null,null,null值不计,结果不变
  • 所以根据递推公式总结的口诀:得到遍历结果为:,1,4,5,6,2,7,8,3,9

然后我们执行程序

    @Testpublic void test(){//首先进行初始化TreeNode headNode = initNode();//深度优先遍历deepSortOutFont(headNode);//deepSortOutMiddle(headNode);//deepSortOutAfter(headNode);// 广度优先遍历//layerTranverse(headNode);}

 得到结果:

程序执行结果和口诀推导得到的结果一致,验证成功


 总结:n项并列递归理解以及向非递归的转化:

  • 根据代码总结出递推函数

对于一个n项递归函数,我们可以很轻易的写出他的递推函数,例如一个归并排序

mearge函数的意思是,将数组的left下标到right下标进行倒序排序,这里为了方便说明就不写出,文章后面会贴出完整代码

得到递推函数:

F(array,left,right) =  op1 &  F(array,left,middle)  & F(array,middle,right) & op2

op表示数据操作,

F(array,left,middle) 为  F(array,left,right)的左半部分

F(array,middle,right) 为  F(array,left,right)的右半部分

  • 根据递推函数得到遍历口诀

拆分公式,确保每一个公式只有一个op操作,并得到遍历口诀

F(array,left,right) =  op1 &  F(array,left,middle)  & F(array,middle,right)   口诀:根左右

F(array,left,right) =  F(array,left,middle)  & F(array,middle,right) & op2   口诀:左右根

  • 例举样本数据,从根节点开始,以未遍历的节点为根,按照遍历口诀,对各个节点进行排序

创建样本数据

array:{ 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 }
left:0
right: 9

 画出二叉树(当然三并列就是三叉树,n并列就是n叉树)

根据函数表述:两个递归函数是将数组的左半部分和右半部分不断分解,直到left>=right(注意终止条件不画出),得到如下二叉树

 

 以第二个公式为例:

F(array,left,right) =  F(array,left,middle)  & F(array,middle,right) & op2   口诀:左右根

 从根节点开始,根据:左右根口诀,得到merge函数的入参顺序,根据merge定义:将下标范围内的数字进行倒序排列,得到每一次入参后的结果

  • 将排序后的数据依次作为数据操作函数的入参,归纳总结出该递推函数的作用

根据二叉树的分解以及执行流程,理解了此归并排序的含义:将数组不断地利用二分法进行分解,直至两个元素,然后再对每一部分进行排序

  • 并且将循环套用的递归函数转化为了线性的,有多个入参的操作函数,且总结出递归函数的执行顺序


 深度、广度优先遍历

其实,二叉树的深度,层级遍历,对应的就是简易的深度、广度优先遍历,见上一级

 下面将简单介绍下他们在二维数组中的应用,以岛屿问题为例

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

 

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

深度优先遍历的解决办法是:详情见

void dfs(int[][] grid, int r, int c) {// 判断 base caseif (!inArea(grid, r, c)) {return;}// 如果这个格子不是岛屿,直接返回if (grid[r][c] != 1) {return;}grid[r][c] = 2; // 将格子标记为「已遍历过」// 访问上、下、左、右四个相邻结点dfs(grid, r - 1, c);dfs(grid, r + 1, c);dfs(grid, r, c - 1);dfs(grid, r, c + 1);
}// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}

 其实就是4并列递归

广度优先遍历的遍历方法为:详情见

// 网格结构的层序遍历
// 从格子 (i, j) 开始遍历
void bfs(int[][] grid, int i, int j) {Queue<int[]> queue = new ArrayDeque<>();queue.add(new int[]{r, c});while (!queue.isEmpty()) {int n = queue.size();for (int i = 0; i < n; i++) { int[] node = queue.poll();int r = node[0];int c = node[1];if (r-1 >= 0 && grid[r-1][c] == 0) {grid[r-1][c] = 2;queue.add(new int[]{r-1, c});}if (r+1 < N && grid[r+1][c] == 0) {grid[r+1][c] = 2;queue.add(new int[]{r+1, c});}if (c-1 >= 0 && grid[r][c-1] == 0) {grid[r][c-1] = 2;queue.add(new int[]{r, c-1});}if (c+1 < N && grid[r][c+1] == 0) {grid[r][c+1] = 2;queue.add(new int[]{r, c+1});}}}
}

其实就是二叉树层级遍历的变形 


http://www.ritt.cn/news/3530.html

相关文章:

  • 做化妆品的网站有哪些百度关键词seo排名软件
  • 简述商务网站建设步骤简述网站建设的流程
  • 建设直播网站软件网站开发软件有哪些
  • 做外贸如何浏览国外网站谷歌自然排名优化
  • 企业信息查询平台官网河南自助建站seo公司
  • 怎么样通过做网站赚钱吗百度服务平台
  • 东省住房和城乡建设厅网站如何推广自己成为网红
  • 没有做等保的网站不能上线对吗高级搜索百度
  • 备案网站出售怎么做网络推广最有效
  • 华强北商城官网app最新seo新手教程
  • 西安网站建设制作价格低爱链网中可以进行链接买卖
  • 西安做网站魔盒文军seo
  • wordpress复制的图片不显示图片广州网站优化步骤
  • 网站怎么做推广seo推广招聘
  • wpdx主题wordpress免费油烟机seo关键词
  • 创建网站制作仪表企业nba哈登最新消息
  • 新农村建设网站网站排名靠前的方法
  • wordpress外贸商城aso优化app推广
  • 贵阳有哪些可以制作网站的公司人民日报新闻
  • 移动网站开发教学大纲搜索引擎营销方式
  • 高校网站建设资料库百度一下百度下载
  • 唐山网站建设报价南昌seo搜索优化
  • python做网站比php好营销培训课程有哪些
  • 大良营销型网站设计公司网络营销的工具和方法有哪些
  • 邢台各种类型网站建设售后完善互联网营销方法有哪些
  • 网站项目的流程广告设计公司
  • wordpress网站托管我在百度下的订单如何查询
  • 重庆做网站开发的集中网站关键词优化代理
  • 别人帮我做的网站没用要交费用吗免费广告发布平台app
  • 网站做语言切换整合营销传播案例