C++后根遍历二叉树的两种递归算法

    法一：（通常）
 
    用一般的二叉链表做存储结构，用到一个栈，同时为这个栈设置一个等大的辅助数组，用以标识栈中节点被访问的次数状态。实现如下：

 // 存储结构：
 
typedef struct BTnode......{
          char data;
          struct BTnode* lchild;
          struct BTnode* rchild;
          }BTnode,*BTree;
  //C实现：
 
int postOrd(BTree T)......{
        int top = 0;
        int tags[MAX_TREE_DEGREE];//tag stack
        BTree p = T;
        BTree nodePointer[MAX_TREE_DEGREE];

        while(p || top > 0)......{
            if(p)......{
                nodePointer[top] = p;
                //初始化当前入栈接点指针的初值为0
                tags[top] = 0;
                ++ top;
                p = p->lchild;
            }
            else if( tags[--top] == 0)......{//访问右子树并且设置tag为1
                tags[top] = 1;
                p = nodePointer[top];
                p = p->rchild;
                //下面的自增运算表示是\"copy\"而不是\"pop\"接点指针
                ++ top; [Page]
            }else......{//出栈 No \"++top\"
                p = nodePointer[top];
                print(p);
            }
            return 1;
        }//while
    }

    法二：（有上面转化而来）

    在法一中用到了栈和一个等大辅助数组，在这里我们把这些东西搬到节点内部，从而又有一种更简洁的后根遍历实现方式。如下：

 //存储结构：
 
typedef struct BTnode ...{
    char data;
    //mark the status of node
    int mark;
       //parent代替stack的功能
    struct BTnode* parent;
    struct BTnode* lchild;
    struct BTnode* rchild;
}BTnode,*BTree; //C具体实现：
 
void PostTraverse(BTree root) ...{
    while(root) ...{
        switch(root->mark) ...{
            //The first visit that means never visiting before
        case 0:
            root->mark = 1;
            if(root->lchild)
                root = root->lchild;
            break;
            //The second visit:
        case 1:
            root->mark = 2;
if(root->rchild)
                root = root->rchild;
            break;
            //The lase visit & print the node value
        case 2:
            root->mark = 0;
            printf(\"%c\",root->data);
            root = root->parent;
            break;
        }
    }
}/**////~PostTraverse()