（JAVA）开始熟悉 “二叉树” 的数据结构-3. 折纸问题

时间：2024-10-07 20:43:27

需求:

请把一段纸条竖着放在桌子上，如何从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。

如果纸条的下边向上方连续对着2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。

  • 给定一个输入参数N，代表纸条都从下边向上方连续对着N次，请从上到下打印所有折痕的方向
  • 例如：N=1时，打印：down；N=2时，打印：down down up

在这里插入图片描述

如图：粉色为正面，黑色为背面。向粉色面折一次代表down，向黑色面折一次代表up

分析：

​ 我们把对着后的纸张翻过来，让粉色朝下，这时把第一次对着产生的折痕看作是根节点，那第二次对着产生的下折痕就是该节点的左子节点，而第二次对着产生的折痕就是该节点的右子节点，这样我们就可以使用数据结构来描述对着后产生的折痕。

  • 这棵树有这样的特点：
    1. 根节点为下折痕
    2. 每一个节点的左子节点为下折痕
    3. 每一个节点的右子节点为上折痕

在这里插入图片描述

实现步骤：

  1. 定义节点类
  2. 构建深度为N的折痕树
  3. 使用中序遍历，打印出数中所有节点的内容

构建深度为N的折痕树：

  1. 第一次对折，只有一条折痕，创建根节点
  2. 如果不是第一次对着，则使用队列保存根节点
  3. 循环遍历队列
    1. 从队列中弹出一个节点
    2. 如果这个节点的左子节点不为空，则把这个左子节点添加到队列中
    3. 如果这个节点的右子节点不为空，则把这个右子节点添加到队列中
    4. 判断当前节点的左子节点和右子节点都不为空，如果是，则需要为当前节点创建一个值为down的左子节点，一个值为up的右子节点

实现代码

/**
* 模拟对折过程，产生树
* @param n 对折次数
* @return
*/
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 Queue<>();
        queue.enqueue(root);

        // 3. 循环遍历队列
        while (!queue.isEmpty()){
            // 从队列中弹出节点
            Node<String> tmp = queue.dequeue();

            // 如果有左子节点，则把左子系欸但放入到队列中
            if (tmp.left != null){
                queue.enqueue(tmp.left);
            }

            // 如果有右子节点，则把左子系欸但放入到队列中
            if (tmp.right != null){
                queue.enqueue(tmp.right);
            }
            // 如果左右两个子节点都没有，那么该节点为叶子节点，只需要给该节点添加左子节点和右子节点
            if (tmp.right == null && tmp.left == 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);
    }
}


// 节点类
public 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;
    }
}

相关文章