5-4-3.c

2005软件工程师考试下午编程题源代码

/*中国系统分析员顾问团，http://www.csai.cn*/
/*程序员下午考试指南书籍源码*/

#include <stdio.h>
#include <malloc.h>
typedef struct node{
     	char data;
       	struct node *left;
       	struct node *right;
}BTREE;


void SortTreelnsert(BTREE **tree,BTREE *S){
if (*tree == NULL)  *tree = S;
else if (S->data < (*tree)->data)
SortTreelnsert(&((*tree)->left),S);
else if (S->data > (*tree)->data)
SortTreelnsert(&((*tree)->right), S);
}

void TraversalTree(BTREE *tree) {
BTREE *stack[1000],*p;
int tag[1000],top = 0;
p = tree;
do {
while(p != NULL) {
stack[++top] = p;
p = p->left;
tag[top] = 0;  /*标志栈顶结点的左子树已进行过后序遍历*/
} 
while(top>0 &&tag[top] == 1 ){  /* 栈顶结点的右子树是否被后序遍历过*/
p = stack[top--];
putchar(p->data);
} 
if (top>0) {    /*对栈顶结点的右子树进行后序遍历*/
p = stack[top]->right;  
tag[top] = 1;
}
}while(top>0);
}

main()
{ BTREE *mytree,*node;
  char a[]={'2','8','9','7','6','5'};
  int i;
  mytree=NULL;
  for(i=0;i<6;i++)
  {
  node=(BTREE *)malloc(sizeof(BTREE));
  node->data=a[i];
  node->left=node->right=NULL;
  SortTreelnsert(&mytree,node);
  }
  TraversalTree(mytree);
}