二叉树遍历-速记法

[chaojun-zhang]

先序遍历

栈S;
p= root;
while(p不空 || S不空){
    while(p不空){
        访问p节点；
        p的右子树入S;
        p = p的左子树;
    }
    p = S栈顶弹出;
}

后序遍历

栈S;
p= root;
while(p不空 || S不空){
    while(p不空){
        访问p节点；
        p的左子树入S;
        p = p的右子树;
    }
    p = S栈顶弹出;
}
结果序列逆序;

中序遍历

栈S;
p= root;
while(p不空 || S不空){
    while(p不空){
        p入S;
        p = p的左子树;
    }
    p = S栈顶弹出;
    访问p;
    p = p的右子树;
}