树--06---二叉树--03---二叉搜索树(BST)--最大深度问题、折纸问题
2021/9/5 23:38:12
本文主要是介绍树--06---二叉树--03---二叉搜索树(BST)--最大深度问题、折纸问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 最大深度问题
- 需求:
- API求最大深度:
- 实现步骤:
- 代码:
- 测试;
- 折纸问题
- 需求:
- 分析:
- 实现步骤:
- 构建深度为N的折痕树:
- 每一次对折,所有叶子节点都需增加其左子结点和右子结点
- 代码:
最大深度问题
需求:
- 给定一棵树,请计算树的最大深度(树的根节点到最远叶子结点的最长路径上的结点数);
上面这棵树的最大深度为4。
API求最大深度:
实现步骤:
- 如果根结点为空,则最大深度为0;
- 计算左子树的最大深度;
- 计算右子树的最大深度;
- 当前树的最大深度=左子树的最大深度,和右子树的最大深度中的较大者+1
代码:
//获取整个树的最大深度 public int maxDepth(){ return maxDepth(root); } //获取指定树x的最大深度 private int maxDepth(Node x){ if (x==null){ return 0; } //x的最大深度 int max=0; //左子树的最大深度 int maxL=0; //右子树的最大深度 int maxR=0; //计算x结点左子树的最大深度 if (x.left!=null){ maxL = maxDepth(x.left); } //计算x结点右子树的最大深度 if (x.right!=null){ maxR = maxDepth(x.right); } //比较左子树最大深度和右子树最大深度,取较大值+1即可 max = maxL>maxR?maxL+1:maxR+1; return max; }
测试;
@Test public void test04(){ //创建树对象 BinaryTree<String, String> tree = new BinaryTree<>(); //往树中添加数据 tree.put("E", "5"); tree.put("B", "2"); tree.put("G", "7"); tree.put("A", "1"); tree.put("D", "4"); tree.put("F", "6"); tree.put("H", "8"); tree.put("C", "3"); int maxDepth = tree.maxDepth(); System.out.println(maxDepth); }
折纸问题
需求:
请把一段纸条竖着放在桌子上,然后从纸条的下边向上方对折1次,压出折痕后展开。此时 折痕是凹下去的,即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次,压出折痕后展开,此时有三条折痕,从上到下依次是下折痕、下折痕和上折痕。
给定一 个输入参数N,代表纸条都从下边向上方连续对折N次,请从上到下打印所有折痕的方向 例如:N=1时,打印: down;N=2时,打印: down down up
分析:
我们把对折后的纸张翻过来,让粉色朝下,这时把第一次对折产生的折痕看做是根结点,那第二次对折产生的下折痕就是该结点的左子结点,而第二次对折产生的上折痕就是该结点的右子结点,这样我们就可以使用树型数据结构来描述对折后产生的折痕。
这棵树有这样的特点:
- 根结点为下折痕;
- 每一个结点的左子结点为下折痕;
- 每一个结点的右子结点为上折痕;
实现步骤:
- 定义结点类
- 构建深度为N的折痕树;
- 使用中序遍历,打印出树中所有结点的内容;
构建深度为N的折痕树:
每一次对折,所有叶子节点都需增加其左子结点和右子结点
- 循环遍历队列,然后判断是否是子节点
- 如果该节点是叶子结点,只需要给该节点添加左子结点和右子结点即可
代码:
import java.util.Queue; import java.util.concurrent.LinkedBlockingDeque; public class PagerFoldingTest { public static void main(String[] args) { //模拟这只过程,产生树 Node<String> tree = createTree(3); //遍历树,打印每个结点 printTree(tree); } //通过模拟对折N次纸,产生树 public static Node<String> createTree(int N){ //定义根结点 Node<String> root=null; for (int i = 0; i < N; i++) { //1.当前是第一次对折 if (i==0){ root = new Node<>("down",null,null); continue; } //2.当前不是第一次对折 //定义一个辅助队列,通过层序遍历的思想,找到叶子结点,叶子结点添加子节点 Queue<Node> queue = new LinkedBlockingDeque<>(); queue.add(root); //循环遍历队列 while(!queue.isEmpty()){ //从队列中弹出一个结点 Node<String> tmp = queue.poll(); //如果有左子结点,则把左子结点放入到队列中 if (tmp.left!=null){ queue.add(tmp.left); } //如果有右子结点,则把右子结点放入到队列中 if (tmp.right!=null){ queue.add(tmp.right); } //如果同时没有左子结点和右子结点,那么证明该节点是叶子结点,只需要给该节点添加左子结点和右子结点即可 if (tmp.left==null && tmp.right==null){ tmp.left = new Node<String>("down", null,null); tmp.right = new Node<String>("up",null,null); } } } return root; } //打印树中每个结点到控制台 public static void printTree(Node<String> root){ //需要使用中序遍历完成 if (root==null){ return; } //打印左子树的每个结点 if (root.left!=null){ printTree(root.left); } //打印当前结点 System.out.print(root.item+" "); //打印右子树的每个结点 if (root.right!=null){ printTree(root.right); } } //结点类 private static class Node<T>{ public T item;//存储元素 public Node left; public Node right; public Node(T item, Node left, Node right) { this.item = item; this.left = left; this.right = right; } } }
这篇关于树--06---二叉树--03---二叉搜索树(BST)--最大深度问题、折纸问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)