网站建设后期需要做什么,二次开发招聘,培训公司网站源码,如何查询自己二建的状态参考资料#xff1a;
DFS 参考文章BFS 参考文章DFS 参考视频二叉树遍历规律递归原理源码N叉树规律总结#xff1a;
由前面二叉树的遍历规律和递归的基本原理#xff0c;我们可以看到#xff0c;二叉树遍历口诀和二叉树递推公式有着紧密的联系 前序遍历#xff1a;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并列递归口诀 公式1F(x) op1(x) F(x左) F(x中) F(x右) 口诀根左中右 公式2F(x) F(x左) op1(x) F(x中) F(x右) 口诀左根中右 公式3F(x) F(x左) F(x中) op1(x) F(x右) 口诀左中根右 公式4F(x) F(x左) F(x中) F(x右) op1(x) 口诀左中右根 其中op1(x)表示对数据X的操作 4叉树4并列递归口诀 公式1F(x) op1(x) F(x上) F(x下) F(x左) F(X右) 口诀根上下左右 公式2F(x) F(x上) op1(x) F(x下) F(x左) F(X右) 口诀上根下左右 公式3F(x) F(x上) F(x下) op1(x) F(x左) F(X右) 口诀上下根左右 公式4F(x) F(x上) F(x下) F(x左) op1(x) F(X右) 口诀上下左根右 公式5F(x) F(x上) F(x下) F(x左) F(X右) op1(x) 口诀上下左右根 其中op1(x)表示对数据X的操作 扩展至n叉树n并列递归口诀 公式1F(x) op1(x) F(x属性1) F(x属性2) ......F(x属性n) 口诀根属性1属性2,......属性n N叉树规律验证
由上述总结出的n叉树规律 公式1F(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右) 口诀根左中右 从根节点开始根据口诀根左中右得到结果0123以未遍历的节点1为根根据口诀根左中右即1456得到结果0145623以未遍历的节点2为根根据口诀根左中右即2null78得到结果014562783以未遍历的节点3为根根据口诀根左中右即39nullnull得到结果0145627839以未遍历节点456789为根根据口诀根左中右即nnullnullnull值不计结果不变所以根据递推公式总结的口诀得到遍历结果为145627839
然后我们执行程序 Testpublic void test(){//首先进行初始化TreeNode headNode initNode();//深度优先遍历deepSortOutFont(headNode);//deepSortOutMiddle(headNode);//deepSortOutAfter(headNode);// 广度优先遍历//layerTranverse(headNode);} 得到结果 程序执行结果和口诀推导得到的结果一致验证成功 总结n项并列递归理解以及向非递归的转化
根据代码总结出递推函数
对于一个n项递归函数我们可以很轻易的写出他的递推函数例如一个归并排序 mearge函数的意思是将数组的left下标到right下标进行倒序排序这里为了方便说明就不写出文章后面会贴出完整代码
得到递推函数 Farray,left,right op1 F(array,left,middle) F(array,middle,right) op2 op表示数据操作
F(array,left,middle) 为 Farray,left,right的左半部分
F(array,middle,right) 为 Farray,left,right的右半部分
根据递推函数得到遍历口诀
拆分公式确保每一个公式只有一个op操作,并得到遍历口诀 Farray,left,right op1 F(array,left,middle) F(array,middle,right) 口诀根左右 Farray,left,right F(array,left,middle) F(array,middle,right) op2 口诀左右根 例举样本数据从根节点开始以未遍历的节点为根按照遍历口诀对各个节点进行排序
创建样本数据 array:{ 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 }
left0
right: 9 画出二叉树当然三并列就是三叉树n并列就是n叉树
根据函数表述两个递归函数是将数组的左半部分和右半部分不断分解直到leftright注意终止条件不画出得到如下二叉树 以第二个公式为例 Farray,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) {Queueint[] 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 (r1 N grid[r1][c] 0) {grid[r1][c] 2;queue.add(new int[]{r1, c});}if (c-1 0 grid[r][c-1] 0) {grid[r][c-1] 2;queue.add(new int[]{r, c-1});}if (c1 N grid[r][c1] 0) {grid[r][c1] 2;queue.add(new int[]{r, c1});}}}
}其实就是二叉树层级遍历的变形
