二叉树（链表实现）--应用案例（最大深度、折纸问题）_给定一棵 以1为根的树,求树的最大深度,如下图 树的最大深度为5

二叉树–最大深度、折纸问题

二叉树的最大深度问题

需求：

​ 给定一棵树，请计算树的最大深度（树的根节点到最远叶子结点的最长路径上的结点数）;

​ 上面这棵树的最大深度为4。

实现：

public int maxDepth()：计算整个树的最大深度

private int maxDepth(Node x):计算指定树x的最大深度

实现步骤：

1.如果根结点为空，则最大深度为0；

2.计算左子树的最大深度；

3.计算右子树的最大深度；

4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1

代码：

//计算整个树的最大深度
public int maxDepth() {
    return maxDepth(root);
}
// 计算指定树x的最大深度
private int maxDepth(Node x) {
    // 如果x为空，则无深度
    if (x == null) {
        return 0;
    }
    int max = 0; // x的最大深度
    int maxL = 0; // x左子树的最大深度
    int maxR = 0; // x右子树的最大深度
    // 计算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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

折纸问题

需求：

​ 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时 折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。

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

分析：

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

这棵树有这样的特点：

1.根结点为下折痕；

2.每一个结点的左子结点为下折痕；

3.每一个结点的右子结点为上折痕；

实现步骤：

1.定义结点类

2.构建深度为N的折痕树；

3.使用中序遍历，打印出树中所有结点的内容；

构建深度为N的折痕树：

1.第一次对折，只有一条折痕，创建根结点；

2.如果不是第一次对折，则使用队列保存根结点；

3.循环遍历队列：

3.1从队列中拿出一个结点；

3.2如果这个结点的左子结点不为空，则把这个左子结点添加到队列中；

3.3如果这个结点的右子结点不为空，则把这个右子结点添加到队列中；

3.4判断当前结点的左子结点和右子结点都不为空，如果是，则需要为当前结点创建一个值为down的左子结点，一个值为up的右子结点。

代码：

/**
 * 二叉树--折纸问题
 */
public class PaperFoldingTest {
    public static void main(String[] args) {
        // 模拟折纸过程，产生树
        Node tree = createTree(2);
        // 遍历树，打印每个结点(中序遍历)
        printTree(tree);
    }


    /**
     * 遍历树，打印每个结点(中序遍历)
     *
     * @param root
     */
    private 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);
        }
    }

    /**
     * 通过模拟对折N次纸，产生树
     *
     * @param N
     * @return
     */
    private static Node createTree(int N) {
        // 定义根结点
        Node<String> root = null;
        for (int i = 0; i < N; i++) {
            // 当前是第一次对折
            if (i == 0) {
                root = new Node<String>("down", null, null);
            } else {
                // 不是第一次对折（利用层次遍历来寻找无子结点的结点，然后为其添加左down右up的子结点）
                Queue<Node<String>> queue = new Queue<>(); // 层序遍历
                queue.enqueue(root);
                while (!queue.isEmpty()) {
                    Node<String> node = queue.dequeue();
                    // 如果当前结点有子结点，让子结点进队列
                    if (node.left != null) {
                        queue.enqueue(node.left);
                    }
                    if (node.right != null) {
                        queue.enqueue(node.right);
                    }
                    // 寻找无子结点的结点，为其添加左down右up的子结点
                    if (node.left == null && node.right == null) {
                        node.left = new Node("down", null, null);
                        node.right = new Node("up", null, null);
                    }
                }
            }
        }
        return root;
    }

    // 结点类
    private static class Node<T> {
        // 存储值
        private T item;
        // 记录左子结点
        private Node left;
        // 记录右子结点
        private Node right;

        public Node(T item, Node left, Node right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86