算法与数据结构（六）：树之折纸问题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法与数据结构（六）：树之折纸问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3345字，纯文字阅读大概需要5分钟。

内容图文

算法与数据结构（六）：树之折纸问题

• 博主会对算法与数据结构会不断进行更新，敬请期待，如有什么建议，欢迎联系。
• 树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事物，例如家谱、单位的组织架构、等等。树是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
• 树的相关术语：

结点的度：
一个结点含有的子树的个数称为该结点的度；
叶结点：
度为0的结点称为叶结点，也可以叫做终端结点
分支结点：
度不为0的结点称为分支结点，也可以叫做非终端结点
结点的层次：
从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推
结点的层序编号：

将树中的结点，按照从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数。
树的度：

树中所有结点的度的最大值
树的高度(深度)：

树中结点的最大层次
森林：

m（m>=0）个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林；给森林增加一个统一的根结点，森林就变成一棵树

孩子结点：
一个结点的直接后继结点称为该结点的孩子结点
双亲结点(父结点)：
一个结点的直接前驱称为该结点的双亲结点
兄弟结点：
同一双亲结点的孩子结点间互称兄弟结点

折纸问题：

• 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时 折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。给定一 个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向 例如：N=1时，打印： down；N=2时，打印： down down up

实现思路：

• 对于折纸问题，完全二叉树是一种实现思路，把第一次折痕看做这个树的根节点，左边的折痕为down，右边的折痕为up，每折一次都对叶子节点进行增加两个子节点，左子节点为down，右子节点为up
• 找到叶子节点通过层序遍历查找，也可通过前序，中序，后序遍历查找到叶子节点
• 打印从上到下打印折痕，说明是中序遍历打印

折纸问题的实现代码如下：

---

package com.victor.tree;

import com.victor.linear.Queue;

/**
 * @description: 利用完全二叉树解决折纸问题
 * @author: victor
 * @date: 2020/12/12  9:41
 */
public class PageFolding {
    public static void main(String[] args) {
        Node<String> tree = createTree(2);
        printTree(tree);
    }

    /**
     * 内部类节点类
     *
     * @param <T> 泛型
     */
    private static class Node<T> {
        T item;
        Node<T> left;
        Node<T> right;

        public Node(T item, Node<T> left, Node<T> right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 生成N层深度的树
     *
     * @param N 深度
     * @return 树
     */
    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;
            }
            //层序遍历，找到叶子节点，将down和up放进去
            Queue<Node<String>> nodes = new Queue<>();
            nodes.enqueue(root);    //放入根节点
            while (!nodes.isEmpty()) {
                Node<String> node = nodes.dequeue();
                //如果有左子节点，把左子节点放入队列中
                if (node.left != null) nodes.enqueue(node.left);
                //如果有右子节点，把右子节点放入队列中
                if (node.right != null) nodes.enqueue(node.right);
                //如果没有左子节点，也没有右子节点，生成新的节点
                if (node.left == null && node.right == null) {
                    node.left = new Node<>("down", null, null);
                    node.right = new Node<>("up", null, null);
                }
            }
        }

        return root;
    }

    /**
     * 以递归的方式，采用中序遍历打印树
     *
     * @param node 树
     */
    public static void printTree(Node<String> node) {
        //如果为null直接返回
        if (node == null) return;
        //打印左子树
        if (node.left != null) printTree(node.left);
        //打印节点
        System.out.print(node.item + " ");
        //打印右子树
        if (node.right != null) printTree(node.right);

    }

}

内容总结

以上是互联网集市为您收集整理的算法与数据结构（六）：树之折纸问题全部内容，希望文章能够帮你解决算法与数据结构（六）：树之折纸问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---