树--06---二叉树--03---二叉搜索树(BST)--最大深度问题、折纸问题

提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录最大深度问题需求API求最大深度实现步骤代码测试;折纸问题需求分析实现步骤构建深度为N的折痕树每一次对折,所有叶子节点都需增加其左子结点和右子结点代码:最大深度问题需求给定一棵树请计算树的最大深度树的根节点到最远叶子结点的最长路径上的结点数;上面这棵树的最大深度为4。API求最大深度实现步骤如果根结点为空则最大深度为0计算左子树的最大深度计算右子树的最大深度当前树的最大深度左子树的最大深度,和右子树的最大深度中的较大者1代码//获取整个树的最大深度publicintmaxDepth(){returnmaxDepth(root);}//获取指定树x的最大深度privateintmaxDepth(Nodex){if(xnull){return0;}//x的最大深度intmax0;//左子树的最大深度intmaxL0;//右子树的最大深度intmaxR0;//计算x结点左子树的最大深度if(x.left!null){maxLmaxDepth(x.left);}//计算x结点右子树的最大深度if(x.right!null){maxRmaxDepth(x.right);}//比较左子树最大深度和右子树最大深度取较大值1即可maxmaxLmaxR?maxL1:maxR1;returnmax;}测试;Testpublicvoidtest04(){//创建树对象BinaryTreeString,StringtreenewBinaryTree();//往树中添加数据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);intmaxDepthtree.maxDepth();System.out.println(maxDepth);}折纸问题需求请把一段纸条竖着放在桌子上然后从纸条的下边向上方对折1次压出折痕后展开。此时 折痕是凹下去的即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次压出折痕后展开此时有三条折痕从上到下依次是下折痕、下折痕和上折痕。给定一 个输入参数N代表纸条都从下边向上方连续对折N次请从上到下打印所有折痕的方向 例如N1时打印 downN2时打印 down down up分析我们把对折后的纸张翻过来让粉色朝下这时把第一次对折产生的折痕看做是根结点那第二次对折产生的下折痕就是该结点的左子结点而第二次对折产生的上折痕就是该结点的右子结点这样我们就可以使用树型数据结构来描述对折后产生的折痕。这棵树有这样的特点根结点为下折痕每一个结点的左子结点为下折痕每一个结点的右子结点为上折痕实现步骤定义结点类构建深度为N的折痕树使用中序遍历打印出树中所有结点的内容构建深度为N的折痕树每一次对折,所有叶子节点都需增加其左子结点和右子结点循环遍历队列,然后判断是否是子节点如果该节点是叶子结点只需要给该节点添加左子结点和右子结点即可代码:importjava.util.Queue;importjava.util.concurrent.LinkedBlockingDeque;publicclassPagerFoldingTest{publicstaticvoidmain(String[]args){//模拟这只过程产生树NodeStringtreecreateTree(3);//遍历树打印每个结点printTree(tree);}//通过模拟对折N次纸产生树publicstaticNodeStringcreateTree(intN){//定义根结点NodeStringrootnull;for(inti0;iN;i){//1.当前是第一次对折if(i0){rootnewNode(down,null,null);continue;}//2.当前不是第一次对折//定义一个辅助队列通过层序遍历的思想找到叶子结点叶子结点添加子节点QueueNodequeuenewLinkedBlockingDeque();queue.add(root);//循环遍历队列while(!queue.isEmpty()){//从队列中弹出一个结点NodeStringtmpqueue.poll();//如果有左子结点则把左子结点放入到队列中if(tmp.left!null){queue.add(tmp.left);}//如果有右子结点则把右子结点放入到队列中if(tmp.right!null){queue.add(tmp.right);}//如果同时没有左子结点和右子结点那么证明该节点是叶子结点只需要给该节点添加左子结点和右子结点即可if(tmp.leftnulltmp.rightnull){tmp.leftnewNodeString(down,null,null);tmp.rightnewNodeString(up,null,null);}}}returnroot;}//打印树中每个结点到控制台publicstaticvoidprintTree(NodeStringroot){//需要使用中序遍历完成if(rootnull){return;}//打印左子树的每个结点if(root.left!null){printTree(root.left);}//打印当前结点System.out.print(root.item );//打印右子树的每个结点if(root.right!null){printTree(root.right);}}//结点类privatestaticclassNodeT{publicTitem;//存储元素publicNodeleft;publicNoderight;publicNode(Titem,Nodeleft,Noderight){this.itemitem;this.leftleft;this.rightright;}}}