我这样定义了pre order：
void pre_order(binary_tree_t* root) { //D<root>L<left>R<right>
if (root) {
printf("%d ", root->data);
pre_order(root->left);
pre_order(root->right);
}
}发现迭代算法很难
void in_order(binary_tree_t* root) { //L<left>D<root>R<right> -- inorder -- gives sorted list
if (root) {
in_order(root->left);
display_element(root->data);
in_order(root->right);
}
}
void iter_in_order(binary_tree_t* root) {//L<left>D<root>R<right>
stack_t *s = create_stack(size_binary_tree(root)+1)
push(s, root)
while (!is_empty_stack(s)) {
push(s, root->left);
root = pop(s);
display_element(root->data);
push(s, root->right);
}
}你能帮助阐明这可能是如何做到的吗？
1条答案
按热度按时间5m1hhzi41#
当开始遍历时，应该首先将路径上的所有节点推到最左边的节点--因为这是您希望首先输出的节点。在循环中，您将立即弹出一个节点并打印它。然后，只有当正确的子节点存在时才推送该子节点。如果它存在，就像一开始一样处理它：遍历到它的最左边的decendent，并推动这些节点。
下面是你的更新代码：