0

我正在做一个名为数据结构和算法的单元。我们刚刚开始，我的教授刚刚教给我们什么是代数语义以及什么是公理等基础知识。到目前为止，我只是以数组的形式使用树。不使用预排序树的签名作为树（值，树，树），其中值是节点中的值，左节点是第一棵树，右节点是第二棵树。

现在我将我的树定义为树（值，树，树）或 Nil，我不知道如何去定义 addNode（值，树）的代数。

每个级别都变得越来越复杂，另外，我无论如何都想不到一次扫描一个级别，现在已经尝试了一个小时。当我们沿着树向下走时，代数只是分支成越来越多的 if-else。我做对了吗？你能为我指出正确的方向吗？或者树不能实现为树（值，树，树）？

这是我教程的一部分（在附加问题中不值得任何标记），但我不是在寻找即时答案，我喜欢这个主题，并想了解更多。

编辑1：我查看了维基百科，我不想使用教科书来获得明确的答案，我只是在寻找正确方向的提示，无论我的方法是正确的还是完全不可能将树定义为树（值，树，树）。我知道您可以以列表的形式表示树 ADT。但我真的想好好想想。希望这是有道理的。非常感谢你们！

编辑2：嗯，很难通过互联网解释。假设我正在定义一个名为“树”的新数据结构。我可以以任何我想要的方式定义它，它必须表现得像一个平衡的二叉树（虽然，父母和孩子的值无关紧要）所以我将它定义为树：树（值，树，树）或无它不是编程代码，这就是我的定义。Tree 是一个值 + 2 棵其他树，或者 Tree 是 nil。现在 addNode(value, tree) 向树添加一个节点，同时仍然保持平衡。它不是编程代码，它只是代数语义。不知道能不能解释清楚。但是我找到了一个可以使用队列或堆栈实现的解决方案，但这是我必须定义的另一个 ADT，它是无效的。

编辑3：似乎我已经假设了许多使问题变得比实际应该更难的事情。首先，从我给出的一点解释来看，Gamecat 的回答是完美的。但我同意这些评论，包括其他 ADT 是完全有效的。事实上，当我们构建任何使用 Int 的东西时，我们正在为该结构使用 ADT。我认为每个 ADT 都必须是独一无二的。无论如何，非常感谢您的回答！

4

2 回答 2

2

如果要将节点添加到树中，可以使用递归函数。

我假设这棵树是有序的。所以你应该得到这样的东西：

AddNode(value, tree)

if tree is empty, create a new tree with value as node and no subtrees.
if value lesser than the treenode, call AddNode on the left branch.
else call AddNode on the right branch. (if duplicates are allowed).

如果子树发生更改，请务必更新它们！

您可以通过以下方式将其转换为非递归函数：

if tree is empty, return a new tree with value as node and no subtrees.
if value is lesser than treenode, and there is no left subtree, create a new left subtree with value as node and no subtrees.
if value is lesser that treenode, and there is a left subtree, try again with the left subtree.
if value is greater or equal than treenode, and there is no right subtree, create a new right subtree with value as node and no subtrees.
if value is greater or equal than treenode, and there is a right subtree, try again with the right subtree.

如果树需要平衡。您需要存储一个平衡重量（可以是-1、0 或1）。如果您需要在“重”站点上添加节点，则需要重新洗牌。例如，如果左侧比右侧多一个节点，您需要在左侧多添加一个节点。您需要从左子树中获取具有最高值的节点并将其提升到当前顶部。前一个顶部被添加到右子树。一定要保持子树的平衡。

示例：添加节点 0,1,2,3,4

Add(0)           0

Add(1)           0
                  \
                   1

Add(2)           0 (2)  =>      1 (2) =>  1
                  \            /         / \
                   1          0         0   2

Add(3)           1
                / \
               0   2
                    \ 
                     3

Add(4)           1 (4)     => 2 (4)  =>      2
                / \          / \            / \
               0   2        1   3          1   3
                    \      /              /     \
                     3    0              0       4
于 2009-03-12T12:13:40.593 回答
1

这是一个很难的问题，因为它太模糊了。我假设你有一本教科书或类似的东西作为你的课程材料的一部分。即便如此，感觉好像您遇到的许多问题都可以通过基本资源来解释，例如二叉树上的维基百科条目。

本页描述了如何进行各种树遍历，以及如何表示树。

于 2009-03-12T10:05:59.747 回答