为什么镜像树在使用无序遍历访问所有节点时不起作用?

Question

所以基本上我需要编写一个镜像二叉树的函数。 [镜像树示例1

我的方法是：访问所有节点一次，然后交换左右子节点。 要遍历，我们可以使用三个遍历中的任何一个。 当我使用预购和后序时，我得到了想要的结果，但没有无序！

void asd(struct node* root)
{if(root == NULL)
return;
asd(root->leftChild);
struct node* t;
t=root->leftChild;
root->leftChild= root->rightChild;
root->rightChild =t;
asd(root->rightChild);
}

我的镜像函数与无序遍历。 我不明白为什么？

Answer 1

我认为问题出在您的遍历顺序上

所以，这就是我所能预见的发生的事情——

{if(root == NULL)
return;

完全没问题。然后你交换左子和右子——

struct node* t;
t=root->leftChild;
root->leftChild= root->rightChild;
root->rightChild =t;

到目前为止还不错，但现在你的右孩子变成了你的左孩子，左孩子变成了右孩子。 现在你打电话

asd(root->rightChild);

假设你正在处理右孩子，但实际上你又在处理左孩子，因为它已经交换了它的位置。

解决方案要么是pre-order，要么是postorder，这将是直截了当的。如果您热衷于使用 inorder，那么您将不得不稍微调整代码。过程又是左子，因为它原来是右子。

void asd(struct node* root)
{if(root == NULL)
return;
asd(root->leftChild);
struct node* t;
t=root->leftChild;
root->leftChild= root->rightChild;
root->rightChild =t;
asd(root->leftChild);
}

希望这有帮助！