一种改进的二叉树的顺序遍历

Question

这是在一次采访中问我的，但我搞砸了。我们给出了一个二叉树，但是，它被修改了，使得它的子节点永远不为空，如果一个非叶节点没有子节点，那么它的右/左子节点指向该节点本身。对于叶节点，它们指向下一个左节点和右节点。对于最左边和最右边的节点，它将指向自身和前一个/下一个元素。

示例：

        1
     /     \
    2       3
  /  \     / \
(4 =  5 = 6 = 7)

这里4.左=4,4.右=5,5.左=4和5.右=6以此类推。

我们需要对这棵树进行顺序遍历。

 if(root.right==root || root.left == root || root.left.right == root || root.right.left == root)

请帮我弄一下。我无法为递归提供适当的条件检查。

我们只需要对这棵树进行顺序遍历。产出：4 2 5 1 6 3 7

Answer 1

以下算法应该做到：

visit(vertex v) {
    if (v.left != v && v.left.right != v) visit(v.left)
    print v
    if (v.right != v && v.right.left != v) visit(v.right)
}

我认为你的问题是你试图一次做太多的事情。与其检测顶点是否为叶子，不如先检测它是否有左子节点，然后再检测它是否有右子节点。