练习15.5-1中的输出函数是有问题的

[leewwe]

当我运行你的实现函数的时候，是没有问题。
我仿照你的程序写了我自己的版本，不同之处在于我使用了vector，却出现了数组越界的问题。
当前答案中的实现程序中也会出现数组越界的问题，没有出现运行时错误的原因是C/C++不做数组越界检测。
所以，我对你的程序做了修改，在计算整颗树的根节点值之前进行一次边界检查。
由于每次输出伪关键字的时候，和当前的根节点值是没有关系的，所以我调整了输出伪关键字和计算当前节点值的顺序，保证在到达边界条件的时候能提前递归返回。

---

原代码的数组越界的截图

---

1. /* 输出最优搜索二叉树结构的辅助函数 */
2. /* 参数：
3. i：起点
4. j：终点
5. r：根
6. */
7. void constructOptimalBST_aux(const vector<vector<int>>& root, int i, int j, int r) {
8. 	if (j < i - 1) {
9. 		return;
10. 	}
11. 	// 调整计算节点值和输出伪关键字的顺序
12. 	// 先输出伪关键字，能保证数组下标越过数组下标之前提前返回
13. 	if (j == i - 1) {
14. 		if (j < r) {
15. 			cout << 'd' << j << "是k" << r << "的左孩子" << endl;
16. 		}
17. 		else {
18. 			cout << 'd' << j << "是k" << r << "的右孩子" << endl;
19. 		}
20. 		return;	// 遇到伪关键字要返回，不能再继续向下走
21. 	}
22. 
23. 	int rootNode = root[i][j];//子树根节点
24. 	if (rootNode < r) {
25. 		cout << "k" << rootNode << "是" << "k" << r << "的左孩子" << endl;
26. 	}
27. 	else {
28. 		cout << "k" << rootNode << "是" << "k" << r << "的右孩子" << endl;
29. 	}
30. 
31. 	constructOptimalBST_aux(root, i, rootNode - 1, rootNode);
32. 	constructOptimalBST_aux(root, rootNode + 1, j, rootNode);
33. }
34. 
35. 
36. /* 输出最优二叉搜索树的结构 */
37. /* 参数：
38. root -> 构造使用的辅助数组
39. i：起点
40. j：终点
41. */
42. void constructOptimalBST(const vector<vector<int>>& root, int i, int j) {
43. 	if (i >= root.size() || j >= root.size()) {
44. 		return;
45. 	}
46. 	int rootNode = root[i][j];//子树根节点
47. 	if (rootNode == root[1][root[0].size() - 1]) {
48. 		// 输出整个树的根
49. 		cout << 'k' << rootNode << "是根" <<endl;
50. 		constructOptimalBST_aux(root, i, rootNode - 1, rootNode);
51. 		constructOptimalBST_aux(root, rootNode + 1, j, rootNode);
52. 	}
53. }