【数据结构】——【树】算法代码实现（C/C++语言实现）（整理不易，请多关注）

目录

1.树的长子-兄弟表示法

2.树的父指针表示法

3.树的子表表示法

4.树的后根周游的递归算法

5.树的先根周游的非递归算法

6.树的中根周游的递归算法

7.树的后根周游的递归算法

8.树的广度优先周游算法

9.二叉树的链接表示

10.二叉树的顺序表示

11.线索二叉树的定义,构造算法和中根周游算法

12.二叉树前根周游的递归算法

13.二叉树对称根周游的递归算法

14.二叉树后根周游的递归算法

15. 二叉树后根周游的非递归算法

1.树的长子-兄弟表示法

#include

typedef int DataType ;
struct  CSNode;                                      
typedef  struct  CSNode   *PCSNode;   
struct  CSNode 
{                                     
    DataType info;                                   
    PCSNode  lchild;                          
    PCSNode  rsibling;                        
};

typedef  struct CSNode  *CSTree;      
typedef  CSTree   *PCSTree;

PCSNode leftChild_cstree(PCSNode p ) 
{
    return p->lchild;
}

PCSNode rightSibling_cstree(PCSNode p ) 
{
    return p->rsibling;
}

PCSNode root_cstree(PCSTree t ) 
{
    return *t;
}

int isNull_cstree(PCSTree t ) 
{
    return *t==NULL;
}

int main()
{
    return 0;
}

2.树的父指针表示法

#define MAXNUM 20

typedef int DataType;

struct ParTreeNode 
{
    DataType info;             
    int     parent;    
};

struct  ParTree 
{ 
    int n;                     
    struct ParTreeNode nodelist[MAXNUM];      
};

typedef struct ParTree *PParTree;             

int rightSibling_partree(PParTree t, int p) 
{
    int i;
    if (p >= 0 && p < t->n) {
        for (i = p+1; i <= t->n; i++)
            if (t->nodelist[i].parent == t->nodelist[p].parent)
                return i;
    }
    return -1;
}



int leftChild_partree(PParTree t, int p) 
{     
    if (t->nodelist[p+1].parent == p)
        return p+1;
    else
        return -1;
}

int main()
{
    return 0;
}

3.树的子表表示法

#include
#define MAXNUM 20

typedef int DataType ;

struct EdgeNode 
{       
    int             nodeposition;
    struct EdgeNode *link;
};

struct ChiTreeNode 
{   
    DataType        info;
    struct EdgeNode *children;
};

struct ChiTree 
{              
    int                n;             
    int                root;   
    struct ChiTreeNode nodelist[MAXNUM];
};

typedef struct ChiTree *PChiTree;             

int rightSibling_chitree(PChiTree t, int p) 
{
    int i;
    struct EdgeNode  *v;
    for (i = 0; i < t->n; i++) {
        v = t->nodelist[i].children;
        while (v != NULL)
            if (v->nodeposition == p)
                if (v->link == NULL)
                    return -1;
                else
                    return(v->link->nodeposition);
            else
                v = v->link;
    }
    return -1;
}

int parent_chitree(PChiTree t, int p) 
{
    int i;
    struct EdgeNode *v;
for (i = 0; i < t->n; i++) 
{    
        v = t->nodelist[i].children;
        while (v!=NULL)
            if (v->nodeposition == p)
                return(i);
            else
                v = v->link;
    }
    return -1;  
}

int main() 
{
    return 0;
}

4.树的后根周游的递归算法

#include
#include

#define  MAXNUM 20
#define null -1


struct  ParTreeNode    
{
    
    int parent; 
};

struct ParTree 
{ 
    int n;                     
    struct ParTreeNode nodelist[MAXNUM];      
};

typedef struct ParTree *PParTree;             

int rightSibling_partree(PParTree t, int p) 
{
    int i;
if (p >= 0 && p < t->n) 
{
        for (i = p+1; i <= t->n; i++)
            if (t->nodelist[i].parent == t->nodelist[p].parent)
                return(i);
    }
    return null;
}



int leftChild_partree(PParTree t, int p) 
{ 
    if (t->nodelist[p+1].parent == p)
        return(p+1);
    else
        return null;
}

typedef int Node;

void visit(Node p) { printf("%d ",p); }

void preOrder( PParTree t,  Node p ) 
{
    Node c;
    visit( p );
    c = leftChild_partree ( t, p );
while (c!=null) 
{
        preOrder ( t, c );
        c = rightSibling_partree (t, c );
    }
}

struct  ParTree tree = {10, -1,0,1,1,3,3,3,0,7,7};

int main()
{
    PParTree t = &tree;
    preOrder(t, 0);
    putchar('n');
        return 0;
}

5.树的先根周游的非递归算法

#include
#include

typedef int DataType;
#define MAXNUM 20       
struct  SeqStack 
{      
    DataType  s[MAXNUM];
    int  t;                    
};
typedef  struct SeqStack  *PSeqStack;  


PSeqStack  createEmptyStack_seq( void ) 
{
    PSeqStack pastack;
    pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
    if (pastack==NULL)
        printf("Out of space!! n");
    else
        pastack->t = -1;
    return  pastack;
}


int  isEmptyStack_seq( PSeqStack pastack ) 
{
    return pastack->t == -1;
}


void  push_seq( PSeqStack pastack, DataType x ) 
{
    if( pastack->t >= MAXNUM - 1  )
        printf( "Overflow! n" );
else 
{
        pastack->t++;
        pastack->s[pastack->t] = x;
    }
}


void  pop_seq( PSeqStack pastack ) 
{
    if (pastack->t == -1 )
        printf( "Underflow!n" );
    else
        pastack->t = pastack->t - 1;
}


DataType  top_seq( PSeqStack pastack ) 
{
    return (pastack->s[pastack->t]);
}

struct  ParTreeNode    
{
    
    int parent; 
};

#define  MAXNUM   20
#define null -1

struct  ParTree
{ 
    int   n;                   
    struct ParTreeNode  nodelist[MAXNUM];     
};

typedef struct ParTree  *PParTree;            

int rightSibling_partree(PParTree t, int p) 
{
    int i;
if (p >= 0 && p < t->n) 
{
        for (i = p+1; i <= t->n; i++)
            if (t->nodelist[i].parent == t->nodelist[p].parent) 
return i;
    }
    return null;
}


int leftChild_partree(PParTree t, int p) 
{
    if (t->nodelist[p+1].parent == p)
        return p + 1;
    else
        return null;
}

typedef int Node;

void visit(Node p) { printf("%d ",p); }

void npreOrder ( PParTree t, Node p ) 
{
    Node c;
    PSeqStack s;       
    s = createEmptyStack_seq ( );
    
    c = 0; 
do 
{
        while ( c!=null ) 
{
            visit ( c );
            push_seq( s, c );
            c = leftChild_partree ( t, c );
        }
        while ( c == null && !isEmptyStack_seq(s)) 
{
            c = rightSibling_partree(t, top_seq(s));
            pop_seq(s);
        }
    } while(c != null);
}

struct  ParTree tree = {10, -1,0,1,1,3,3,3,0,7,7};

int main()
{
    npreOrder(&tree, 0);
    putchar('n');
    return 0;
}

6.树的中根周游的递归算法

#include

#define  MAXNUM 20
#define null -1


struct  ParTreeNode    
{
    
    int parent; 
};

struct ParTree 
{ 
    int n;                     
    struct ParTreeNode nodelist[MAXNUM];      
};

typedef struct ParTree *PParTree;             

int rightSibling_partree(PParTree t, int p) 
{
    int i;
if (p >= 0 && p < t->n) 
{
        for (i = p+1; i <= t->n; i++)
            if (t->nodelist[i].parent == t->nodelist[p].parent)
                return(i);
    }
    return null;
}


int leftChild_partree(PParTree t, int p) 
{ 
    if (t->nodelist[p+1].parent == p)
        return(p+1);
    else
        return null;
}

typedef int Node;

void visit(Node p) { printf("%d ",p); }

void inOrder( PParTree t, Node p ) 
{
    Node c;  
    c = leftChild_partree ( t, p );
    if (c == null) visit( p );
    else {
        inOrder(t, c);
        visit( p );
        c = rightSibling_partree (t, c );
        while (c != null) {
            inOrder ( t, c );
            c = rightSibling_partree (t, c );
        }
    }
}

struct  ParTree tree = {10, -1,0,1,1,3,3,3,0,7,7};

int main()
{
    inOrder(&tree, 0);
    putchar('n');
    return 0;
}

7.树的后根周游的递归算法

#include

#define MAXNUM 20
#define null -1


struct  ParTreeNode    
{
    
    int parent; 
};

struct ParTree 
{ 
    int n;                     
    struct ParTreeNode nodelist[MAXNUM];      
};

typedef struct ParTree *PParTree;             

int rightSibling_partree(PParTree t, int p) 
{
    int i;
    if (p >= 0 && p < t->n) {
        for (i = p+1; i <= t->n; i++)
            if (t->nodelist[i].parent == t->nodelist[p].parent)
                return(i);
    }
    return null;
}


int leftChild_partree(PParTree t, int p) 
{ 
    if (t->nodelist[p+1].parent == p)
        return(p+1);
    else
        return null;
}

typedef int Node;

void visit(Node p) { printf("%d ",p); }

void postOrder( PParTree t, Node p ) 
{
    Node c;
    c = leftChild_partree (t, p);
while (c != null) 
{
        postOrder (t, c);
        c = rightSibling_partree (t, c);
    }
    visit( p );
}

struct  ParTree tree={10, -1,0,1,1,3,3,3,0,7,7};

int main()
{
    PParTree t = &tree;
    postOrder(t, 0);
    putchar('n');
    return 0;
}

8.树的广度优先周游算法

#include
#include

#define MAXNUM 20
#define null -1


struct  ParTreeNode    
{
    
    int parent; 
};

struct ParTree 
{ 
    int n;                     
    struct ParTreeNode nodelist[MAXNUM];      
};

typedef struct ParTree *PParTree;             

int rightSibling_partree(PParTree t, int p) 
{
    int i;
if (p >= 0 && p < t->n) 
{
        for (i = p+1; i <= t->n; i++)
            if (t->nodelist[i].parent == t->nodelist[p].parent)
                return(i);
    }
    return null;
}



int leftChild_partree(PParTree t, int p) 
{ 
    if (t->nodelist[p+1].parent == p)
        return(p+1);
    else
        return null;
}

typedef int Node;

void visit(Node p) { printf("%d ",p); }


typedef Node DataType;
struct SeqQueue 
{       
    int f, r;
    DataType q[MAXNUM];
};

typedef struct SeqQueue *PSeqQueue;   


PSeqQueue  createEmptyQueue_seq( void ) 
{  
    PSeqQueue paqu;
    paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
    if (paqu == NULL)
        printf("Out of space!! n");
    else
        paqu->f = paqu->r = 0;
        return paqu;
}


int  isEmptyQueue_seq( PSeqQueue paqu ) 
{
    return (paqu->f == paqu->r);
}


void  enQueue_seq( PSeqQueue paqu, DataType x ) 
{
    if( (paqu->r + 1) % MAXNUM == paqu->f  )
        printf( "Full queue.n" );
    else {
        paqu->q[paqu->r] = x;
        paqu->r = (paqu->r + 1) % MAXNUM;
    }
}


void  deQueue_seq( PSeqQueue paqu ) 
{
    if( paqu->f == paqu->r )
        printf( "Empty Queue.n" );
    else
        paqu->f = (paqu->f + 1) % MAXNUM;
}


DataType  frontQueue_seq( PSeqQueue paqu ) 
{
    return paqu->q[paqu->f];
}

void levelOrder(PParTree t) 
{
    Node c;
    PSeqQueue q;       
    q = createEmptyQueue_seq();
    
    c = 0; 
    if (c == null)  return;
    enQueue_seq(q,c);
while (!isEmptyQueue_seq(q)) 
{
        c = frontQueue_seq(q);
        deQueue_seq(q);
        visit(c);
        c = leftChild_partree(t, c);
        while (c!=null) {
            enQueue_seq(q,c);
            c = rightSibling_partree(t, c);
        }
    }
}

struct ParTree tree = {10, -1,0,1,1,3,3,3,0,7,7};

int main()
{
    PParTree t = &tree;
    levelOrder(t);
    putchar('n');
    return 0;
}

9.二叉树的链接表示

#include
#include

typedef int DataType;

struct BinTreeNode;                            
typedef  struct BinTreeNode     *PBinTreeNode; 

struct BinTreeNode 
{ 
    DataType  info;                            
    PBinTreeNode llink;                     
    PBinTreeNode rlink;                     
};

typedef  struct BinTreeNode  *BinTree;

typedef  BinTree  *PBinTree;

PBinTreeNode root_btree(PBinTree t) 
{
    return *t;
}

PBinTreeNode leftChild_btree (PBinTreeNode p) 
{
    return p->llink;
}

PBinTreeNode rightChild_btree (PBinTreeNode p) 
{
    return p->rlink;
}




PBinTreeNode createRest_BTree() 
{ 
    PBinTreeNode  pbnode;
    char ch;
    scanf("%c", &ch);
    if(ch == '@') pbnode = NULL;
else 
{ 
        pbnode = (PBinTreeNode )malloc(sizeof(struct BinTreeNode));
        if( pbnode == NULL )         
{
            printf("Out of space!n");
            return pbnode;
        }
        pbnode->info = ch;
        pbnode->llink = createRest_BTree();   
        pbnode->rlink = createRest_BTree();   
    }
    return pbnode;
}



PBinTree  create_BTree( void ) 
{ 
    PBinTree pbtree;
    pbtree = (PBinTree)malloc(sizeof(BinTree));
    if (pbtree != NULL)
        *pbtree = createRest_BTree( );  
    return pbtree; 
}


int main()
{
        return 0;
}

10.二叉树的顺序表示

#define  MAXNODE    20
typedef int DataType;
struct SeqBTree 
{                      
    int       n;                      
    DataType  nodelist[MAXNODE];
};

typedef  struct SeqBTree  *PSeqBTree;

int root_seq(PSeqBTree t) 
{
    return t->nodelist[0];
}

int parent_seq(PSeqBTree t, int p) 
{
    return t-> nodelist[(p-1)/2];
}

int leftChild_seq(PSeqBTree t, int p) 
{
    return t-> nodelist[2*p+1];
}

int rightChild_seq(PSeqBTree t, int p) 
{
    return t-> nodelist[2*(p+1)];
}

int main() 
{
    return 0;
}

11.线索二叉树的定义,构造算法和中根周游算法

#include
#include
typedef int DataType;
struct ThrTreeNode;                         
typedef struct ThrTreeNode  *PThrTreeNode;    

struct ThrTreeNode 
{                        
    DataType      info;
    PThrTreeNode  llink, rlink;
    int           ltag, rtag;
};

typedef struct ThrTreeNode  *ThrTree;       
typedef ThrTree  *PThrTree;                 

#define  MAXNUM  100            
struct  SeqStack 
{              
    int          t; 
    PThrTreeNode s[MAXNUM];
};
typedef struct SeqStack *PSeqStack;           


PSeqStack  createEmptyStack_seq( void ) 
{
    PSeqStack pastack;
    pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
    if (pastack == NULL)
        printf("Out of space!! n");
    else
        pastack->t = -1;
    return pastack;
}


int  isEmptyStack_seq( PSeqStack pastack ) 
{
    return pastack->t == -1;
}


void  push_seq( PSeqStack pastack, PThrTreeNode x ) 
{
    if( pastack->t >= MAXNUM - 1  )
        printf( "Overflow! n" );
    else {
        pastack->t++;
        pastack->s[pastack->t] = x;
    }
}


void  pop_seq( PSeqStack pastack ) 
{
    if (pastack->t == -1 )
        printf( "Underflow!n" );
    else
        pastack->t--;
}


PThrTreeNode  top_seq( PSeqStack pastack ) 
{
    return pastack->s[pastack->t];
}

void thread(PThrTree t) 
{
    PSeqStack  st;                                    
    PThrTreeNode  p;                    
    PThrTreeNode  pr;                    
     
    if (t == NULL || *t == NULL) return ;
    st = createEmptyStack_seq();        
    p = *t;
    pr = NULL;
do 
{
        while (p != NULL) 
{             
            push_seq(st,p);
            p = p->llink;
        }
        
        while ( p == NULL && !isEmptyStack_seq(st) ) 
{ 
            p = top_seq(st);
            pop_seq(st);
            if (pr != NULL) 
{
                if (pr->rlink == NULL) 
{
                    pr->rlink = p;
                    pr->rtag = 1;
                }
                if (p->llink == NULL) 
{ 
                    p->llink = pr;
                    p->ltag = 1;
                }
            }
            pr = p;
            p = p->rlink;               
        }
    } while ( !isEmptyStack_seq(st) || p != NULL );
    free(st);                           
}

void visit(PThrTreeNode  p) { printf("%d ", p->info); }


void nInOrder( PThrTree t ) 
{
    PThrTreeNode  p;
    if (t == NULL || *t == NULL) return ;
    p = *t;
    while ( p->llink != NULL && p->ltag == 0 )    
        p = p->llink;
    while (p != NULL) { 
        visit(p);
        if( p->rlink != NULL && p->rtag == 0 )  
{    
            p = p->rlink;
            while( p->llink != NULL && p->ltag == 0 )
                p = p->llink;
        } 
        else
            p = p->rlink;                           
    }
}  

int main()
{
    return 0;
}

12.二叉树前根周游的递归算法

#include
#include

typedef char DataType;

struct BinTreeNode;                         
typedef struct BinTreeNode *PBinTreeNode;   

struct BinTreeNode 
{
    DataType  info;                         
    PBinTreeNode  llink;                    
    PBinTreeNode  rlink;                    
};

typedef struct BinTreeNode *BinTree;
typedef BinTree *PBinTree;

PBinTreeNode root_btree(PBinTree t) 
{
    return *t;
}

PBinTreeNode leftChild_btree (PBinTreeNode p)
{
    return p->llink;
}

PBinTreeNode rightChild_btree (PBinTreeNode p)
{
    return p->rlink;
}



PBinTreeNode createRest_BTree() 
{
    
    PBinTreeNode  pbnode;
    char ch;
    scanf(" %c",&ch);
    if ( ch == '@') pbnode = NULL;
    else {
        pbnode = (PBinTreeNode )malloc(sizeof(struct BinTreeNode));
        if (pbnode == NULL) 
{
            printf("Out of space!n");
            return pbnode;
        }
        pbnode->info = ch;
        pbnode->llink = createRest_BTree();   
        pbnode->rlink = createRest_BTree();   
    }
    return pbnode;
}

PBinTree  create_BTree( void ) 
{
    
    PBinTree pbtree = (PBinTree)malloc(sizeof(BinTree));
    if (pbtree != NULL)
        *pbtree = createRest_BTree( );  
    return pbtree; 
}

void visit(PBinTreeNode p) { printf("%c ",p->info); }

void preOrder(PBinTreeNode p) 
{
    if (p == NULL) return;
    visit(p);
    preOrder(leftChild_btree(p));
    preOrder(rightChild_btree(p));
}

int main(){
    PBinTree tree = create_BTree();
    preOrder(*tree);
    putchar('n');
    return 0;
}

13.二叉树对称根周游的递归算法

#include
#include

typedef char DataType;

struct BinTreeNode;                         
typedef struct BinTreeNode *PBinTreeNode;   

struct BinTreeNode 
{
    DataType  info;                         
    PBinTreeNode  llink;                    
    PBinTreeNode  rlink;                    
};

typedef struct BinTreeNode *BinTree;
typedef BinTree *PBinTree;
typedef PBinTreeNode BNode;

PBinTreeNode root_btree(PBinTree t) 
{
    return *t;
}

PBinTreeNode leftChild_btree (PBinTreeNode p)
{
    return p->llink;
}

PBinTreeNode rightChild_btree (PBinTreeNode p)
{
    return p->rlink;
}


PBinTreeNode createRest_BTree() 
{
    
    PBinTreeNode  pbnode;
    char ch;
    scanf("%c",&ch);
    if ( ch == '@') pbnode = NULL;
    else {
        pbnode = (PBinTreeNode )malloc(sizeof(struct BinTreeNode));
        if (pbnode == NULL) 
{
            printf("Out of space!n");
            return pbnode;
        }
        pbnode->info = ch;
        pbnode->llink = createRest_BTree();   
        pbnode->rlink = createRest_BTree();   
    }
    return pbnode;
}


PBinTree  create_BTree( void ) 
{
    
    PBinTree pbtree = (PBinTree)malloc(sizeof(BinTree));
    if (pbtree != NULL)
        *pbtree = createRest_BTree( );  
    return pbtree; 
}

void visit(BNode p) { printf("%c ",p->info); }

void inOrder(BNode p) 
{
    if (p == NULL) return;
    inOrder(leftChild_btree(p));
    visit(p);
    inOrder(rightChild_btree(p));
}


int main()
{
    PBinTree tree = create_BTree();
    inOrder(*tree);
    putchar('n');
    return 0;
}

14.二叉树后根周游的递归算法

#include
#include

typedef char DataType;

struct BinTreeNode;                         
typedef struct BinTreeNode *PBinTreeNode;   

struct BinTreeNode 
{
    DataType  info;                         
    PBinTreeNode  llink;                    
    PBinTreeNode  rlink;                    
};

typedef struct BinTreeNode *BinTree;
typedef BinTree *PBinTree;
typedef PBinTreeNode BNode;

PBinTreeNode root_btree(PBinTree t) 
{
    return *t;
}

PBinTreeNode leftChild_btree (PBinTreeNode p)
{
    return p->llink;
}

PBinTreeNode rightChild_btree (PBinTreeNode p)
{
    return p->rlink;
}



PBinTreeNode createRest_BTree() 
{
    
    PBinTreeNode  pbnode;
    char ch;
    scanf("%c",&ch);
    if ( ch == '@') pbnode = NULL;
else 
{
        pbnode = (PBinTreeNode )malloc(sizeof(struct BinTreeNode));
        if (pbnode == NULL) 
{
            printf("Out of space!n");
            return pbnode;
        }
        pbnode->info = ch;
        pbnode->llink = createRest_BTree();   
        pbnode->rlink = createRest_BTree();   
    }
    return pbnode;
}


PBinTree  create_BTree( void ) 
{
    
    PBinTree pbtree = (PBinTree)malloc(sizeof(BinTree));
    if (pbtree != NULL)
        *pbtree = createRest_BTree( );  
    return pbtree; 
}

void visit(BNode p) { printf("%c ", p->info); }

void postOrder(BNode p) 
{
    if (p==NULL) return;
    postOrder(leftChild_btree(p));
    postOrder(rightChild_btree(p));
    visit(p);
}

int main()
{
    PBinTree tree = create_BTree();
    postOrder(*tree); 
    putchar('n');
    return 0;
}

15. 二叉树后根周游的非递归算法

#include
#include

typedef char DataType;

struct BinTreeNode;                         
typedef struct BinTreeNode *PBinTreeNode;   

struct BinTreeNode 
{
    DataType  info;                         
    PBinTreeNode  llink;                    
    PBinTreeNode  rlink;                    
};

typedef struct BinTreeNode *BinTree;
typedef BinTree *PBinTree;
typedef PBinTreeNode BNode;

PBinTreeNode root_btree(PBinTree t) 
{
    return *t;
}

PBinTreeNode leftChild_btree (PBinTreeNode p)
{
    return p->llink;
}

PBinTreeNode rightChild_btree (PBinTreeNode p)
{
    return p->rlink;
}



PBinTreeNode createRest_BTree() 
{
    
    PBinTreeNode  pbnode;
    char ch;
    scanf("%c",&ch);
    if ( ch == '@') pbnode = NULL;
    else {
        pbnode = (PBinTreeNode )malloc(sizeof(struct BinTreeNode));
        if (pbnode == NULL) 
{
            printf("Out of space!n");
            return pbnode;
        }
        pbnode->info = ch;
        pbnode->llink = createRest_BTree();   
        pbnode->rlink = createRest_BTree();   
    }
    return pbnode;
}


PBinTree  create_BTree( void ) 
{
    
    PBinTree pbtree = (PBinTree)malloc(sizeof(BinTree));
    if (pbtree != NULL)
        *pbtree = createRest_BTree( );  
    return pbtree; 
}

void visit(BNode p) { printf("%c ",p->info); }

typedef struct 
{ 
    BNode ptr;          
    int   tag;          
} Elem;


#define MAXNUM 20       
struct  SeqStack 
{      
    int  t;             
    Elem s[MAXNUM];
};

typedef struct SeqStack *PSeqStack;    


PSeqStack  createEmptyStack_seq( void ) 
{
    PSeqStack pastack;
    pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
    if (pastack == NULL)
        printf("Out of space!! n");
    else
        pastack->t = -1;
    return pastack;
}


int isEmptyStack_seq( PSeqStack pastack ) 
{
    return pastack->t == -1;
}


void push_seq( PSeqStack pastack, Elem x ) 
{
    if( pastack->t >= MAXNUM - 1  )
        printf( "Overflow! n" );
    else {
        pastack->t++;
        pastack->s[pastack->t] = x;
    }
}


void  pop_seq( PSeqStack pastack ) 
{
    if (pastack->t == -1 )
        printf( "Underflow!n" );
    else
        pastack->t--;
}


Elem  top_seq( PSeqStack pastack ) 
{
    return (pastack->s[pastack->t]);
}

void nPostOrder(PBinTree t) 
{
    PSeqStack st;      
    Elem stnode;
    BNode  p;          
    char continueflag; 
    
    if (*t == NULL) return;
    st = createEmptyStack_seq( );     
    
    p = *t;                 
do 
{                                 
        while (p != NULL) 
{ 
            stnode.ptr = p;
            stnode.tag = 1;
            push_seq(st, stnode);
            p = leftChild_btree(p);
        }
        continueflag = 't';
        while ( continueflag == 't' && !isEmptyStack_seq(st) ) 
{
            stnode = top_seq(st);
            pop_seq(st);       
            p = stnode.ptr;                          
            if (stnode.tag == 1) 
{ 
            
                stnode.tag = 2;
                push_seq(st, stnode);
                continueflag = 'f';
                p = rightChild_btree(p);
            }
            else visit(p);
        }
    } while (!isEmptyStack_seq (st)); 
}

int main()
{
    PBinTree  tree = create_BTree();
    nPostOrder(tree);
    putchar('n');
    return 0;
}