//非递归后序遍历 void postOrder2(BiTree& T){ SqStack Stack; initSqStack(Stack); BiTNode * p = T,*r =NULL; while (p!=NULL||!isEmpty(Stack)){ if(p!=NULL){ push(Stack,p); p = p->lchild; } else{ getStackTop(Stack,p); if(p->rchild!=NULL&&p->rchild!=r){ p = p->rchild; } else{ //访问结点 pop(Stack,p); printf("%d ",p->data); r = p; p=NULL; } } } }算法时间复杂度和空间复杂度

该算法的时间复杂度为 $O(n)$，其中 $n$ 为二叉树中的结点数。

该算法的空间复杂度为 $O(h)$，其中 $h$ 为二叉树的高度，即最长路径上的结点数。在最坏情况下，二叉树为单链表，高度为 $n-1$，此时空间复杂度为 $O(n)$。在最好情况下，二叉树为满二叉树，高度为 $\log_2(n+1)$，此时空间复杂度为 $O(\log_2(n+1))$。