提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
//获取整个树的最大深度 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
我们把对折后的纸张翻过来,让粉色朝下,这时把第一次对折产生的折痕看做是根结点,那第二次对折产生的下折痕就是该结点的左子结点,而第二次对折产生的上折痕就是该结点的右子结点,这样我们就可以使用树型数据结构来描述对折后产生的折痕。
这棵树有这样的特点:
每一次对折,所有叶子节点都需增加其左子结点和右子结点
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; } } }