《黑马程序员》—折纸问题

《黑马程序员》—折纸问题

折纸问题： 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折 1 次，压出折痕后展开。此时 折痕是凹下去的，即折 痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。 分析思路： 我们把对折后的纸张翻过来，让粉色朝下，这时把第一次对折产生的折痕看做是根结点，那第二次对折产生的下折痕就是该结点的左子结点，而第二次对折产生的上折痕就是该结点的右子结点，这样我们就可以使用树型数据结构来描述对折后产生的折痕。 这棵树有这样的特点： 1.根结点为下折痕； 2.每一个结点的左子结点为下折痕； 3.每一个结点的右子结点为上折痕； 实现步骤： 1. 定义结点类 2.构建深度为N 的折痕树； 3.使用中序遍历，打印出树中所有结点的内容；

package tree2;import java.util.LinkedList;
import java.util.Queue;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++){//第一次对折if(i==0){root = new Node<>("down", null, null);//continue语句用于循环语句中，作用是不执行循环体剩余部分，直接进行下次循环。continue;}//非第一次对折//关键：通过层序遍历的思想，找到叶子节点，给叶子节点添加子节点Queue<Node> queue = new LinkedList<>();queue.offer(root);//循环遍历队列while(!queue.isEmpty()){Node temp = ve();if(temp.left!=null){queue.offer(temp.left);}if(temp.right!=null){queue.offer(temp.right);}//判断当前节点是不是叶子节点if(temp.left==null && temp.right==null){temp.left = new Node("down",null,null);temp.right = new Node("up",null,null);}}}return root;}//中序遍历打印public static void printTree(Node 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>{//T是自定义泛型，泛型的主要目的是实现 java的类型安全，消除了强制类型转换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;}}
}