后续遍历关键在于,当节点的 右子树存在且被访问后 或者是 右子树为空 才能访问自身。
在遍历过程中,先将节点从的左孩子到最左节点压栈, 设置标志变量 flag 来判断是否访问过左孩子, pre指针来指向先前访问过的节点。
所有左孩子压栈后, 最后一个节点的左孩子为空,已被访问p = NULL , 令flag=1
当左孩子被访问时,进入循环,取栈顶节点。
1. 当栈顶节点的右孩子 等于 空 或 前一个被访问的节点 时, 访问该节点, 令pre 等于当前节点,pre = p, 当前节点出栈。
2. 当栈顶节点的右孩子不为空时, 继续遍历以右孩子为根节点的右子树。
1 Status PostOrderTraverse(BiTree T){ 2 BiTree p = T, S[100], pre; 3 int top = 0, flag = 1; 4 if(p) 5 do{ 6 while(p){ 7 S[top++] = p; 8 p = p->lchild; 9 } 10 // p所有左节点入栈 11 flag = 1; 12 13 while(top != 0 && flag == 1){ 14 p = S[top-1]; 15 if(p->rchild == pre || p->rchild == NULL){ 16 //右孩子不存在或右孩子已访问 17 top--; 18 printf("%c ", p->data); 19 pre = p; 20 //指向被访问节点 21 } 22 else{ 23 //继续遍历右子树 24 p = p->rchild; 25 flag = 0; 26 } 27 } 28 }while(top != 0); 29 return OK; 30 }//PostOrderTraverse