1

嗨，我已经在 mips 中实现了一个 bst，我需要打印这棵树。每个节点有以下四个信息

  • 它的价值

  • 父母的地址

  • 左孩子的地址

  • 右孩子的地址

我应该按以下格式打印树。（x 表示没有孩子）

12

8-16

x-9  13-17

x-x  x-11 x-x  x-x

您能否建议一种实现此打印方法的方法？

4

2 回答 2

1

由于您需要逐级打印二叉树，因此打印信息最明显的方法是使用广度优先搜索方法遍历树。其余的很简单，应该不是问题。:)

于 2012-04-20T15:04:35.427 回答
1

您打印树的顺序是广度优先（逐级）遍历。一种选择如下：维护一个工作列表，最初以树的根为种子。然后，反复从工作列表中出列，打印当前元素（如果不存在则打印 x），然后将两个子元素添加到工作列表中。当你完成遍历树时，你需要一些方法来跟踪，也许是先计算节点的数量，然后在你打印出那么多节点后停止。

也就是说，由于您在 MIPS 中执行此操作，因此一个更简单的选择是将树线性化为一个数组，然后打印该数组。如果以类似于在隐式二叉堆中对节点进行编号的方式对节点进行编号，则可以递归/迭代地遍历树，用树节点填充数组，然后遍历数组打印出所有内容。

希望这可以帮助！

于 2012-04-20T15:06:49.483 回答