为什么这些树与有序树相同但与二叉树不同

Question

为什么这些树与有序树相同但与二叉树不同

algorithmdata-structurestreebinary-tree

3

我不明白？按照有序树的定义，它们不应该也是不同的吗？因为它们的顺序是不同的。

- jantristanmilan

3

问自己两件事情：（1）是什么使一棵树“有序”？（2）从图表中可以推断出关于添加节点的顺序的什么信息？然后在每种情况下确定相应有序树的结构。 - dmckee --- ex-moderator kitten

一个有序树包含可以按照特定标准排序的节点（元素），我不明白它如何适用于这张图片… 我想不出它按什么标准排序。 - jantristanmilan

@dmckee 哦！等等，在有序树中唯一重要的是它是否是第n个子节点，对吧？因为这两棵树除了5之外都是相同的，但它们仍然是相同的有序树，因为在这两棵树中，5都是3的孙子，我理解得对吗？还是我误解了什么？ - jantristanmilan

2个回答

0

一个有序树或平面树是指为每个顶点的孩子指定了一个顺序的有根树。这被称为“平面树”，因为孩子的顺序等同于将树嵌入平面中。给定一个在平面中根化树的嵌入，如果固定一个孩子方向（从根开始，然后是第一个孩子，第二个孩子等），比如逆时针，则嵌入会给出孩子的顺序。相反地，给定一个有序树，并惯例性地将根画在顶部，那么有序树中的子节点可以从左到右绘制，从而得到基本唯一的平面嵌入。

Source:http://en.wikipedia.org/wiki/Ordered_tree#ordered_tree

希望你明白了！

- user1657017

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

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

- rici · Accepted Answer

在一个有序树中，子节点从左到右排序。它们与它们的父节点无关（或者可以认为父节点总是在前面）。如果只有一个子节点，则只有一个子节点。

在二叉树中，有一个（可选的）左子节点和一个（可选的）右子节点。如果只有一个子节点，则它可能是左子节点或右子节点，并且这两种情况是不同的。或者，您可以认为父节点位于子节点之间，因此您可以区分在父节点之前的子节点和在父节点之后的子节点。

有序树和具有相同节点数的二叉树之间存在同态映射：即每个有序树唯一对应一个二叉树。要找到与有序树对应的二叉树：使二叉树中每个节点的左子节点指向有序树中节点的最左子节点，并使二叉树中每个节点的右子节点指向有序树中节点右侧的同级节点。（很明显如何反转该过程，以便您可以看到每个二叉树都唯一对应一个有序树。）

因此，具有k个节点的二叉树的数量与具有k个节点的有序树的数量相同。