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

Question

我不明白？它们不应该与有序树不同吗？因为顺序不同

Answer 1

在有序树中，子节点从左到右排序。它们没有相对于它们的父节点排序(或者，您可以认为父节点总是排在第一位)。如果只有一个 child ，就只有一个 child 。

在二叉树中，有一个(可选的)左 child 和一个(可选的)右 child 。如果只有一个 child ，则可能是左 child ，也可能是右 child ，这两种情况是不同的。或者，您可以认为父节点位于子节点之间，这样您就可以区分位于父节点之前的子节点和位于父节点之后的子节点。

具有相同节点数的有序树和二叉树之间存在同态性:即每棵有序树都唯一对应于一棵二叉树。求一棵有序树对应的二叉树:使二叉树中每个节点的左 child 指向有序树中该节点的最左 child ，使二叉树中每个节点的右 child 指向有序树中节点右侧的兄弟节点。 (应该很明显如何反转这个过程，这样你就可以看到每棵二叉树都唯一对应于一棵有序树。)

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