什么是有根树？

Question

5

什么是建立根树的意思？我在这里阅读了定义，但即使我们将节点指定为根，为什么树只采用以下形状？我的意思是，我可以画出具有4个顶点的根树，其形状不止以下4种吗？对吧？

- Square-root

1

你能画出什么其他的形状？ - Thilo

我在考虑只是将方向从左改为右...你是在暗示无论我改变方向还是翻转图形，结果都是一样的吗？ - Square-root

1

足够“相同”以至于没有真正的区别（当然取决于上下文）。这被称为同构。你可以把图形倒过来，但它仍然是同一个图形（某种程度上而言）。 - Thilo

http://mathworld.wolfram.com/RootedTree.html - Abhishek

好的，我明白了。谢谢 :) - Square-root

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steve Cooper · Accepted Answer

我认为唯一的区别在于树中的一个节点是特殊的起始节点。

通常，树是递归的; 所有树节点本身都是树。 “有根树”只是其中一个节点与其他子节点标记不同。这可能意味着算法无法递归实现，或者需要对根节点进行特殊处理。

我想到的例子是红黑树。红黑树中的节点被标记为红色或黑色。但是有一个特殊规则，“根节点总是黑色”。因此，我们必须对根节点进行特殊处理，仅限于根节点。根节点的子节点可以是红色的; 这意味着根节点的第一级子节点不能被视为其自己的红黑树中的根节点。

因此，您可能会期望有“区分”的代码，例如：

 if(node.isRoot):
    node.Color = black

自由树是二叉搜索树中的任何节点；选择哪个节点并不重要，像查找和插入这样的操作总是按照相同的方式进行。它们的算法是递归的。自由树上的算法从不包括“它是否为根节点”的问题。