2019-10-5
3.2.30 # 解答 # 本题在原书后续印刷中已修改，这里仍然采用中文版的题目。
与上一题非常类似，条件有：
根结点必须在 min 和 max 范围内，
且左右子树要么不存在，要么小于/大于根结点的键，
左右子树同样满足上述条件。
代码 # protected static bool IsOrdered(Node x, TKey min, TKey max) { if (x == null) { return true; // 空树显然是满足要求的。 } return IsOrdered(x.Left, min, max) && IsOrdered(x.Right, min, max) && // 左右子树都满足要求。 x.Key.CompareTo(max) <= 0 && x.Key.CompareTo(min) >= 0 && // 当前结点位于范围内。 (x.Left == null || x.Left.Key.CompareTo(x.Key) < 0) && (x.Right == null || x.Right.Key.CompareTo(x.Key) > 0); // 当前结点与子结点满足大小关系。 } 另请参阅 # BinarySearchTree 库
2019-10-5
3.2.31 # 解答 # 本题在原书后续印刷中已删除，这里仍然采用中文版的题目。
注意这个题并没有递归的要求，直接广度优先搜索即可，随时记录和检查已找到的键。
代码 # protected static bool HasNoDuplicates(Node x) { var keys = new List<TKey>(); // 也可以用 HashSet 之类的数据结构提高效率。 var queue = new Queue<Node>(); queue.Enqueue(x); while (queue.Count > 0) { var node = queue.Dequeue(); if (node == null) { continue; } if (keys.Contains(node.Key)) { return false; } keys.Add(node.Key); queue.Enqueue(node.Left); queue.Enqueue(node.Right); } return true; } 另请参阅 # BinarySearchTree 库
2019-10-5
3.2.32 # 解答 # 本题在原书后续印刷中已修改，这里仍然采用中文版的题目。
官网解答见：https://algs4.cs.princeton.edu/32bst/BST.java.html （isBST()）
书中已经给出了答案，当然在 Java 和 C# 里，&& 总是从左向右计算的，而且遇到 false 会直接返回结果。
如果数据结构中存在环，IsOrdered 有可能会陷入无限递归的情况，因此调用顺序比较重要。
代码 # public static bool IsBST(BST<TKey, TValue> bst) { return IsBinaryTree(bst) && IsOrdered(bst) && HasNoDuplicates(bst); } 另请参阅 # Boolean logical operators (C# reference)
Equality, Relational, and Conditional Operators
BinarySearchTree 库
2019-10-6
3.2.33 # 解答 # 官网解答见：https://algs4.cs.princeton.edu/32bst/BST.java.html （isRankConsistent()）
按照题目要求实现即可，分为两步进行测试。
代码 # public static bool IsRankConsistent(BST<TKey, TValue> bst) { for (var i = 0; i < bst.Size(); i++) { if (i != bst.Rank(bst.Select(i))) { return false; } } foreach (var key in bst.Keys()) { if (key.CompareTo(bst.Select(bst.Rank(key))) != 0) { return false; } } return true; } 另请参阅 # BinarySearchTree 库
2019-10-6
3.2.34 # 解答 # 其实就是将所有的结点按照中序序列排成了一个双向链表，对树进行修改时要同时更新这个双向链表。
当插入新结点时，插到左侧的结点会变为父结点的新前驱，同理右侧会变为新后继。
注意要更新父结点原来的前驱和后继结点（如果有）。
删除结点时较为简单，只要更新需要删除结点的前驱和后继结点即可。
原本操作 left 和 right 的代码不需要更改，只需要加上对 prev 和 next 做操作的代码即可。
Prev 方法实现如下（Next 类似），修改了内部的 Get 方法使之返回 Node 而非 TValue。
public TKey Prev(TKey key) { var node = Get(root, key); if (node == null || node.Prev == null) return null; return node.Prev.Key; } 代码 # 处理结点关系的几个方法。
private void DeleteNode(Node x) { if (x.Prev != null) x.Prev.Next = x.Next; if (x.Next != null) x.Next.Prev = x.
...
2019-10-6
3.2.35 # 解答 # 根据书中已经给出的归纳关系式（中文版 P255/英文版 P403）：
$$ C_N=N-1+(C_0+C_{N-1})/N+(C_1+C_{N-2})/N+\cdots+(C_{N-1}+C_0)/N $$
整理得：
$$ C_N=N-1+(C_0+C_1+\cdots+C_{N-1})/N+(C_{N-1}+\cdots+C_1+C_0)/N $$
这和快速排序的式子基本一致，只是 $N+1$ 变成了 $N-1$。
遵循相同的推导过程，我们可以获得类似的结果，两边同乘以 $N$：
$$ NC_N=N(N-1)+2(C_0+C_1+\cdots+C_{N-1}) $$
用 $N+1$ 时的等式减去该式得：
$$ (N+1)C_{N+1}-NC_N=2N+2C_N \newline (N+1)C_{N+1}=2N+(N+2)C_N \newline \frac{C_{N+1}}{N+2}=\frac{2N}{(N+1)(N+2)} + \frac{C_N}{N+1} $$
令 $T_N = \frac{C_N}{N+1}$，得到：
$$ T_{N+1}=\frac{2N}{(N+1)(N+2)} + T_N \newline T_{N+1}-T_{N} = \frac{2N}{(N+1)(N+2)} $$
归纳得：
$$ \begin{aligned} T_N &= 2 \sum_{i=2}^{N} \frac{i-1}{i(i+1)} \newline C_N&=2(N+1)\sum_{i=2}^{N} \frac{i-1}{i(i+1)} \newline C_N&=2(N+1)\sum_{i=2}^{N}(i-1) (\frac{1}{i}-\frac{1}{i+1}) \newline C_N&=-2(N-1)+ 2(N+1)\sum_{i=2}^{N}\frac{1}{i}\newline C_N&=-2(N-1)+ 2(N+1)(-1+\sum_{i=1}^{N}\frac{1}{i})\newline C_N&=-4N+2(N+1)(\ln N+\gamma) \end{aligned} $$
...
2019-10-7
3.2.36 # 解答 # 用一个栈来模拟递归即可，将路径上的结点记录到栈里。
注意 Queue<TKey> 不算额外空间，因为它在keys执行完毕之后不会被回收。
代码 # private void Keys(Node x, Queue<TKey> queue, TKey lo, TKey hi) { var stack = new Stack<Node>(); while (x != null || stack.Count > 0) { if (x != null) { var cmpLo = lo.CompareTo(x.Key); var cmpHi = hi.CompareTo(x.Key); if (cmpHi >= 0) stack.Push(x); if (cmpLo < 0) x = x.Left; else x = null; } else { x = stack.
...
2019-10-8
3.2.37 # 解答 # 二叉树层序遍历，出队一个结点，打印它，将结点的左右子树入队，循环即可。
代码 # private void PrintLevel(Node x) { var queue = new Queue<Node>(); queue.Enqueue(x); while (queue.Count > 0) { var node = queue.Dequeue(); if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); Console.Write(node.Key + ", "); } } 另请参阅 # BinarySearchTree 库
2019-10-25
3.2.38 # 解答 # 通过层序遍历计算结点的坐标，然后绘制即可。
先算出最大深度，确定每一层的高度 Y，
再将每一层的宽度分成 $2^n-1$ 份，从左到右依次对结点赋值。
效果如下：
代码 # 计算坐标的函数。
public void DrawTree(Graphics pen, RectangleF panel) { var depth = Depth(root); // 确定最大深度。 var layerHeight = panel.Height / depth; var nowLayer = new Queue<Node>(); var nextLayer = new Queue<Node>(); nextLayer.Enqueue(root); for (var layer = 0; layer != depth; layer++) { var unitSizeX = (float)(panel.Width / Math.Pow(2, layer)); var temp = nowLayer; nowLayer = nextLayer; nextLayer = temp; var cursorX = 0.
...
2019-10-31
3.2.39 # 解答 # 测试结果：
可以看到和公式给出的结果十分一致。
测试时先生成 0~2n 顺序序列，奇数插入二叉树中，偶数用于测试查找失败的情况。
代码 # static void Main(string[] args) { var n = 10000; var trial = 100; for (var i = 0; i < 3; i++) { var odds = new int[n]; var evens = new int[n]; var bst = new BSTAnalysis<int, int>(); for (var j = 100; j < n; j++) { evens[j] = j; odds[j] = j + 1; } Shuffle(odds); foreach (var item in odds) { bst.
...