Exercise 1 - Getting set up
练习 1：环境准备#

Download the code provided on the website, organise your folders, and get a project set up as usual. You should now see the following files in the project:
从网站下载提供的代码，整理好文件夹，并按常规方式完成项目搭建。此时你应在项目中看到以下文件：

• TreePlay.java - the main program
  TreePlay.java - 主程序
• BinaryTree.java - a class representing binary trees of integers
  BinaryTree.java - 表示整数二叉树的类
• TreeUtilities.java - various utilities, including for generating random trees and for pop-up windows displaying binary trees
  TreeUtilities.java - 各种工具方法，包括生成随机树与弹窗显示二叉树
• TreeNavigator.java - a class with some empty method stubs, which you will complete in the practical
  TreeNavigator.java - 包含若干待补全方法桩的类，你将在本次实践中完成它们

Have a look at the main() method in the main class TreePlay and its comments. Now run the program to see what it does.
先查看主类 TreePlay 中的 main() 方法及其注释，然后运行程序观察其行为。

Please note that you don’t need to know how the creation of a random tree or the display of a tree works (inside TreeUtilities.java) for this practical. These facilities are just provided to make it easier for you to create multiple sample trees to try things out on, and see the contents of the trees.
请注意，在本次实践中你 不需要 理解随机树生成或树可视化显示（TreeUtilities.java 内部）是如何实现的。这些功能只是为了便于你快速创建多个样例树并查看树内容。

Exercise 2 - Traversals
练习 2：遍历#

Implement the method preOrderTraversal() in the TreeNavigator class. After that, add a line of code to the main method in the main class, TreePlay, to look at the results of your traversals, so that you now have
在 TreeNavigator 类中实现 preOrderTraversal()。随后在主类 TreePlay 的 main 方法中添加代码，以查看遍历结果，即：

1
BinaryTree t = TreeUtilities.createRandomTree();
2
System.out.println("PREORDER TRAVERSAL");
3
TreeNavigator.preOrderTraversal(t);
4

5
TreeUtilities.showTree(t);

Run the code - but STOP before clicking on the continue button. Before the program gets to printing out the pre-order traversal of the tree, predict the results: write down on a piece of paper what the tree looks like, and write down what you THINK is the pre-order traversal of the tree. Then click on the continue button. Were you right? If not, try again.
运行代码，但在点击继续按钮前先停下。在程序打印先序遍历结果前，请先预测：把树形结构画在纸上，并写下你“认为”的先序遍历序列。然后再点击继续。你猜对了吗？如果没有，再试一次。

Now implement the postOrderTraversal() and inOrderTraversal() methods, and test them by adding code to the TreePlay class, as you did for the preOrderTraversal() method. Note that it will be easier to check your results if you call your TreeNavigator methods before calling TreeUtilities.showTree().
接着实现 postOrderTraversal() 和 inOrderTraversal() ，并像测试 preOrderTraversal() 一样，在 TreePlay 中添加测试代码。请注意，如果在调用 TreeUtilities.showTree() 之前先调用你的 TreeNavigator 方法，那么检查结果将会更加容易。

Exercise 3 - Counting the Leaves
练习 3：统计叶子节点#

Now implement the leafCount() method in the TreeNavigator class so that you count how many leaves there are in a binary tree:
现在在 TreeNavigator 类中实现 leafCount()，用于统计二叉树中的叶子节点数量：

1
public int leafCount(BinaryTree t)…

For example, in this binary tree →
例如，在这棵二叉树中 →

there are precisely three leaves (containing 30, 33 and 55):
恰好有三个叶子节点（值为 30、33 和 55）：

Add a line in the main method of the TreePlay class, before the tree gets displayed, like this
在 TreePlay 类的 main 方法中、树显示之前，加入如下代码：

1
System.out.println("LEAF COUNT = " + TreeNavigator.leafCount(t));
2
TreeUtilities.showTree(t);

so you can check the result of the leafCount method while the tree is displayed on the screen.
这样你就可以在树可视化显示时同步核对 leafCount 的结果。

Exercise 4 - The Depth of a Binary Tree
练习 4：二叉树深度#

该 depth of a binary tree is the number of edges that you have to traverse to get from the root of the tree to its furthest leaf.
二叉树的深度是指：从树根到最远叶子节点所需经过的边数。

Usually, height is the same as depth.
通常高度（height）与深度（depth）在这里可视为同义。

Note: a tree with only one node has depth 0, an empty tree is taken to have -1, and for example, the height of this tree is 5, because you have to traverse 5 edges to get from the root to the furthest leaf:
注意：只有一个节点的树深度为 0；空树深度视为 -1。下图这棵树高度为 5，因为从根到最远叶子需要经过 5 条边：

Hint: the method Math.max may be useful (look it up in the API documentation).
提示：Math.max 方法可能有帮助（可查阅 API 文档）。

In the TreeNavigator class, implement the method depth() and test it by adding lines to the TreePlay class. The best way to do this is to add a line before the tree gets displayed, like this
在 TreeNavigator 类中实现 depth() 方法，并在 TreePlay 类中添加测试代码。推荐在树显示前加入如下语句：

1
System.out.println("DEPTH = " + TreeNavigator.depth(t));
2
TreeUtilities.showTree(t);

so you can check the result of the depth() method while the tree is displayed on the screen. As before, try it on a few more trees, to test that it seems to work ok.
这样你就能在树显示时核对 depth() 的结果。和之前一样，再多测几棵树，确认实现表现正常。

Further Exercises (optional)
进阶练习（可选）#

These exercises are provided so that if at some point you would like to practise further with binary tree concepts, you have some exercises to try. They would be very good for revision purposes!
这些练习用于你后续继续巩固二叉树概念，非常适合复习使用！

Exercise 5 - More Practice on Recursive Methods
练习 5：递归方法进阶#

Write a recursive method strictlyBinary() (to go in the TreeNavigator class)
编写递归方法 strictlyBinary()（放在 TreeNavigator 类中）：

1
public static boolean strictlyBinary(BinaryTree t)

which returns true if and only if the tree is strictly binary. A tree is strictly binary if it is not empty, and every node that is not a leaf has precisely two subtrees.
当且仅当该树是 strictly binary（严格二叉树）时返回 true。严格二叉树要求：树非空，且每个非叶节点都恰好有两个子树。

Reference Answer#

1
package binary_tree;
2
/**
3
 * @author Anka
4
 */
5
public class TreeNavigator {
6

7
    /**
8
     * Print out a preorder traversal of a binary tree
9
     *
10
     * @param t root of the tree to be traversed
11
     */
12
    public static void preOrderTraversal(BinaryTree t) {
13
        if (t != null) {
14
            System.out.println(t.data);
15
            preOrderTraversal(t.left);
16
            preOrderTraversal(t.right);
17
        }
18
    }
19

20
    /**
21
     * Print out a postorder traversal of a binary tree
22
     *
23
     * @param t root of the tree to be traversed
24
     */
25
    public static void postOrderTraversal(BinaryTree t) {
26
        if (t != null) {
27
            postOrderTraversal(t.left);
28
            postOrderTraversal(t.right);
29
            System.out.println(t.data);
30
        }
31
    }
32

33
    /**
34
     * Print out a inorder traversal of a binary tree
35
     *
36
     * @param t root of the tree to be traversed
37
     */
38
    public static void inOrderTraversal(BinaryTree t) {
39
        if (t != null) {
40
            inOrderTraversal(t.left);
41
            System.out.println(t.data);
42
            inOrderTraversal(t.right);
43
        }
44
    }
45

46
    /**
47
     * Count the leaves on a binary tree
48
     * @param t root of the tree to be examined
49
     * @return the number of leaves in the tree
50
     */
51
    public static int leafCount(BinaryTree t) {
52
        int count = 0;
53
        if (t != null) {
54
            if (t.left == null && t.right == null) {
55
                count = 1;
56
            } else {
57
                count += leafCount(t.left);
58
                count += leafCount(t.right);
59
            }
60
            return count;
61
        } else {
62
            return 0;
63
        }
64
    }
65

66
    /**
67
     * Find the depth of a binary tree
68
     * @param t the root of the tree to be examined
69
     * @return depth of the tree
70
     */
71
    public static int depth(BinaryTree t) {
72
        if (t != null) {
73
            int leftDepth = depth(t.left);
74
            int rightDepth = depth(t.right);
75
            return 1 + Math.max(leftDepth, rightDepth);
76
        } else {
77
            return 0;
78
        }
79
    }
80
    public static int depth2(BinaryTree t) {
81
        if (t == null) {
82
            return -1;
83
        } else {
84
            return 1 + Math.max(depth2(t.left), depth2(t.right));
85
        }
86
    }
87

88
    /**
89
     * Determine whether a tree is strictly binary
90
     * @param t the tree to be examined
91
     * @return true if the tree is strictly binary, false if it is not
92
     */
93
    public static boolean strictlyBinary(BinaryTree t) {
94
        if (t != null) {
95
            if ((t.left == null && t.right != null) || (t.left != null && t.right == null)) {
96
                return false;
97
            } else {
98
                return strictlyBinary(t.left) && strictlyBinary(t.right);
99
            }
100
        } else {
101
            return true;
102
        }
103
    }
104
    public static boolean strictlyBinary2(BinaryTree t) {
105
        if (t == null) {
106
            return false;
107
        } else if (t.left == null && t.right == null) {
108
            return true;
109
        } else {
110
            return strictlyBinary2(t.left) && strictlyBinary2(t.right);
111
        }
112
    }
113
}

Exercise 1#

Set up a project from the sources supplied on the student website, in the usual way.
用学生网站提供的源码按常规方式搭建项目。

Take a look at the two files you are provided with:
查看提供给你的文件：

• Xrefs.java - the main program (DO NOT ALTER)
  Xrefs.java - 主程序（不要修改）
• WordTree.java - where the binary search tree is (DO NOT ALTER)
  WordTree.java - 二叉搜索树数据结构定义（不要修改）
• TreeUtils.Java - this contains various routines for processing trees, and it is the only file that you should alter
  TreeUtils.java - 包含各种树处理例程，也是唯一需要你修改的文件

The data structure for the binary search tree to store the words is provided for you, in the file WordTree.java. In the exercises below, you will modify the file TreeUtils.java so as to implement the following methods:
用于存储单词的二叉搜索树数据结构已在 WordTree.java 提供。接下来你需要修改 TreeUtils.java，实现以下方法：

• recordWord() - adding a word to a tree
  recordWord() - 向树中添加单词
• display() - for the displaying a tree
  display() - 显示树中内容
• numberOfEntries() - counting how many different words there are in a tree
  numberOfEntries() - 统计树中不同单词的数量

Study the Java classes, and, in particular, in TreeUtils.java the specifications as pre- and post-conditions of the methods.
请阅读这些 Java 类，尤其关注 TreeUtils.java 中各方法的前置条件与后置条件说明。

Start editing the file TreeUtils.java by putting your name as the author.
先在 TreeUtils.java 中将作者信息改为你的名字。

Note that when you add a word to the tree, if the word is new, then a new node should be added to the tree, but if the word has been seen before, then the line-number of the new occurrence of the word should be added to the list of line numbers accompanying the word in the tree.
注意：向树中添加单词时，若该词是新词则应新建节点；若该词已存在，则应将此次出现的行号加入该词对应的行号列表。

Exercise 2#

Implement the method
实现下列方法：

1
recordWord(WordTree tree, String word, int lineNo)

This method should insert the word word into the tree tree, and should return a reference to the tree that results from this insertion. If tree is null then the method should create a tree containing just the word word.
该方法应将单词 word 插入树 tree，并返回插入后的树引用。若 tree 为 null，则应创建一棵仅含 word 的新树并返回。

Note: you do not need to copy existing nodes into a new tree. Just insert the word supplied and return a reference to the modified tree.
注意： 你不需要把已有节点复制到新树中，只需在原树上插入该词并返回修改后的树引用。

Note: you can compare strings by using suitable methods from the String class, in particular look up the methods equalsIgnoreCase() and compareToIgnoreCase(). For example if word1 and word2 are the two strings to be compared, then the expression word1.compareToIgnoreCase(word2) will return 0 if the two words are the same (ignoring upper/lower case), will return a number less than 0 if word1 occurs before word2 in the dictionary, and will return a number greater than 0 if word1 occurs after word2 in the dictionary.
注意： 比较字符串可使用 String 类方法，特别是 equalsIgnoreCase() 与 compareToIgnoreCase()。例如比较 word1 与 word2 时，word1.compareToIgnoreCase(word2)：若两词相同（忽略大小写）返回 0；若 word1 在词典序中位于 word2 之前则返回小于 0；反之返回大于 0。

Suggestion: don’t worry about the line numbers at first, but produce a first version of your program that just produces an alphabetically ordered list of all the (different) words that appeared in the input file.
建议：开始阶段先不处理行号，先做出一个版本，只输出输入文件中所有不同单词的字母序列表。

Also, don’t forget that, if a word appears on a line of the text more than once, then the line number should appear only once.
同时别忘了：若同一单词在同一行出现多次，该行号也只应记录 一次。

Exercise 3#

Implement the method display(). If you traverse the binary search tree in the right order then the words will come out in alphabetical order. You will not need to sort the list of words if you have built it in the right way.
实现 display() 方法。若你按正确顺序遍历二叉搜索树，输出单词将天然按字母序排列。只要树构建正确，你不需要额外排序。

You may assume that the list of line numbers for any one word will fit on one line of the display.
你可以假设：任意单词对应的行号列表都能在显示中放在同一行。

Exercise 4#

Implement the method numberOfEntries().
实现 numberOfEntries() 方法。

Reference Answer#

1
package binary_search_tree;
2
/**
3
 * @author GitHub Copilot
4
 */
5
public class TreeUtils {
6
    /**
7
     * Records a new occurrence of a given word into a WordTree.
8
     *
9
     * @param tree The WordTree into which the word should be recorded (N.B.
10
     * this can be null, in which case a new tree should be created and returned)
11
     * @param word the word to be recorded
12
     * @param lineNo the line number on which the word occurred
13
     * @return a reference to the modified tree, with the new word inserted.
14
     * N.B if tree is null, the method should create a WordTree
15
     * containing the word to be inserted, and should return it.
16
     * PRECONDITION: tree is a well formed binary search tree
17
     * POSTCONDITION: if word was not in tree, then the word and its line number
18
     * (lineNo) have been inserted into ordered word tree, else line has been
19
     * appended to line-number list for word (if we haven't already recorded
20
     * that line number for this word)
21
     */
22
    public static WordTree recordWord(WordTree tree, String word, int lineNo) {
23
        // If tree is empty, create a new node and return it
24
        if (tree == null) {
25
            return new WordTree(word, lineNo);
26
        }
27

28
        // Compare words ignoring case to maintain dictionary order
29
        int cmp = word.compareToIgnoreCase(tree.word);
30
        if (cmp == 0) {
31
            // Word already in this node: add the line number if not already present
32
            if (!tree.lineNumbers.contains(lineNo)) {
33
                tree.lineNumbers.add(lineNo);
34
            }
35
        } else if (cmp < 0) {
36
            // Insert into left subtree
37
            tree.left = recordWord(tree.left, word, lineNo);
38
        } else {
39
            // Insert into right subtree
40
            tree.right = recordWord(tree.right, word, lineNo);
41
        }
42

43
        return tree;
44
    }
45

46
    /**
47
     * Displays all the words in a WordTree.
48
     *
49
     * @param tree the WordTree whose contents are to be displayed
50
     * PRECONDITION: tree is a well formed binary search tree
51
     * POSTCONDITION words have been written out in alphabetical order, each
52
     * followed by ascending list of line numbers on which the word occurs
53
     */
54
    public static void display(WordTree tree) {
55
        if (tree == null) return;
56

57
        // In-order traversal to display words in alphabetical order
58
        display(tree.left);
59

60
        // Print word followed by its line numbers (ascending order)
61
        System.out.print(tree.word + ": ");
62
        for (int i = 0; i < tree.lineNumbers.size(); i++) {
63
            System.out.print(tree.lineNumbers.get(i));
64
            if (i < tree.lineNumbers.size() - 1) System.out.print(", ");
65
        }
66
        System.out.println();
67

68
        display(tree.right);
69
    }
70

71
    /**
72
     * Counts how many different words there are in a WordTree
73
     *
74
     * @param tree the WordTree whose words are to be counted
75
     * @return the number of different words in tree
76
     * PRECONDITION: tree is a well formed binary search tree
77
     */
78
    public static int numberOfEntries(WordTree tree) {
79
        if (tree == null) return 0;
80
        return 1 + numberOfEntries(tree.left) + numberOfEntries(tree.right);
81
    }
82
}

Appendix
附录#

If you want to entertain yourself look at:
如果你想放松一下，可以看看：

https://www.youtube.com/watch?v=TKlub5vB9z8

Here is an example output for Moses.txt, which contains a nonsense poem from the film Singing in the Rain:
下面是 Moses.txt 的输出示例；该文本来自电影 Singing in the Rain 中的一首无厘头诗：

1
************************************
2
Producing a cross-reference for the file:
3
Moses.txt
4
************************************
5
1: Moses supposes his toeses are Roses,
6
2: But Moses supposes erroneously,
7
3: Moses he knowses his toeses aren't roses,
8
4: As Moses supposes his toeses to be!
9
5: Moses supposes his toeses are Roses,
10
6: But Moses supposes erroneously,
11
7: A mose is a mose!
12
8: A rose is a rose!
13
9: A toes a toes!
14
10: Hooptie doodie doodle
15
11: Moses supposes his toeses are Roses,
16
12: But Moses supposes erroneously,
17
13: For Moses he knowses his toeses aren't roses,
18
14: As Moses supposes his toeses to be!
19
15: Moses
20
16: (Moses supposes his toeses are roses)
21
17: Moses
22
18: (Moses supposes erroneously)
23
19: Moses
24
20: (Moses supposes his toeses are roses)
25
21: As Moses supposes his toeses to be!
26
22: A Rose is a rose is a rose is a rose is
27
23: A rose is for Moses as potent as toeses
28
24: Couldn't be a lily or a daphi daphi dilli
29
25: It's gotta be a rose cuz it rhymes with mose!
30
26: Moses!
31
27: Moses!
32
28: Moses!
33
A: 7, 8, 9, 22, 23, 24, 25
34
are: 1, 5, 11, 16, 20
35
aren't: 3, 13
36
As: 4, 14, 21, 23
37
be: 4, 14, 21, 24, 25
38
But: 2, 6, 12
39
Couldn't: 24
40
cuz: 25
41
daphi: 24
42
dilli: 24
43
doodie: 10
44
doodle: 10
45
erroneously: 2, 6, 12, 18
46
For: 13, 23
47
gotta: 25
48
he: 3, 13
49
his: 1, 3, 4, 5, 11, 13, 14, 16, 20, 21
50
Hooptie: 10
51
is: 7, 8, 22, 23
52
it: 25
53
It's: 25
54
knowses: 3, 13
55
lily: 24
56
mose: 7, 25
57
Moses: 1, 2, 3, 4, 5, 6, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 26, 27, 28
58
or: 24
59
potent: 23
60
rhymes: 25
61
rose: 8, 22, 23, 25
62
Roses: 1, 3, 5, 11, 13, 16, 20
63
supposes: 1, 2, 4, 5, 6, 11, 12, 14, 16, 18, 20, 21
64
to: 4, 14, 21
65
toes: 9
66
toeses: 1, 3, 4, 5, 11, 13, 14, 16, 20, 21, 23
67
with: 25
68
number of words: 144
69
number of different words: 35

常见二叉树类型#

完美二叉树#

如下图所示，完美二叉树（perfect binary tree）所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 $0$ ，其余所有节点的度都为 $2$ ；若树的高度为 $h$ ，则节点总数为 $2^{h+1} - 1$ ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。

Tip

请注意，在中文社区中，完美二叉树常被称为满二叉树。

完全二叉树#

如下图所示，完全二叉树（complete binary tree）仅允许最底层的节点不完全填满，且最底层的节点必须从左至右依次连续填充。请注意，完美二叉树也是一棵完全二叉树。

完满二叉树#

如下图所示，完满二叉树（full binary tree）除了叶节点之外，其余所有节点都有两个子节点。

平衡二叉树#

如下图所示，平衡二叉树（balanced binary tree）中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

二叉树的退化#

下图展示了二叉树的理想结构与退化结构。当二叉树的每层节点都被填满时，达到“完美二叉树”；而当所有节点都偏向一侧时，二叉树退化为“链表”。

• 完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。
• 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至 $O(n)$ 。

如下表所示，在最佳结构和最差结构下，二叉树的叶节点数量、节点总数、高度等达到极大值或极小值。