学生成绩管理系统 - 数据结构上机实验报告Yangtze(8)

}

Push(S,T); Tree p=T;

while(S.base!=S.top) { while(Get(S,p)&&p)Push(S,p->lchild); Pop(S,p); if(S.base!=S.top)Get(S,p); else exit; if(p->rchild)Push(S,p->rchild); // if(!p->rchild) else { Pop(S,p); cout<data<<\ Tree a; a=p; //用一个临时指针就可以不让他走回原路 if(S.base!=S.top)Get(S,p); else break; //我用错了 用的exit，这样程序直接就出去了 if(p->lchild==a){p->lchild=NULL;} if(p->rchild==a){p->rchild=NULL;} //free(p); 这样直接删除不了，还必须让他的双亲节点指向NULL p=p->rchild; Push(S,p); } }

5、 实验程序：

#include #include #include

typedef struct TNode { char data; struct TNode *lchild,*rchild;

}TNode,*Tree;

#define stack_init_size 500; typedef struct Stack { TNode **base,**top;

int stacksize; }Stack;

void Init(Stack &S) { S.base=new Tree[500]; S.top=S.base; S.stacksize=stack_init_size; }

int Push(Stack &S,Tree e) { *S.top++=e; return 1; }

int Pop(Stack &S,Tree &e) { if(S.base!=S.top){ e=*(--S.top); return 1; } return 0; }

int Get(Stack S,Tree &e) { if(S.base!=S.top) {e=*(S.top-1); return 1;} else return 0; }

int Create(Tree &T) { char ch; cin>>ch; if(ch=='#')T=NULL; else{ T=(Tree)malloc(sizeof(TNode)); //给二叉链表分配一个结点的内存 if(!T) return 0; T->data=ch; Create(T->lchild); //递归函数的调用 Create(T->rchild);

} return 1; }

int PrintElement(char e) { cout<

int PreOrder(Tree T,int(* visit)(char e)) //先序遍历 { if(T) { if(visit(T->data)) if(PreOrder(T->lchild,PrintElement)) if(PreOrder(T->rchild,PrintElement)) return 1; return 0; } else return 1; }

int InOrder(Tree T,int(* visit)(char e)) { Stack S; Init(S); Push(S,T); Tree p=T; while(S.base!=S.top) { while(Get(S,p)&&p)Push(S,p->lchild); //向左走到尽头 Pop(S,p); //空指针出栈 if(S.base!=S.top) { Pop(S,p); PrintElement(p->data); //得到第一个元素 Push(S,p->rchild); //用循环代替递归函数 } } return 1; }

void PostOrder(Tree T) { Stack S; Init (S); Push(S,T); Tree p=T; while(S.base!=S.top) { while(Get(S,p)&&p)Push(S,p->lchild); Pop(S,p); if(S.base!=S.top)Get(S,p); else exit; if(p->rchild)Push(S,p->rchild); else { Pop(S,p); cout<data<<\ Tree a; a=p; //用一个临时指针就可以不让他走回原路 if(S.base!=S.top)Get(S,p); else break; //我用错了 用的exit，这样程序直接就出去了 if(p->lchild==a){p->lchild=NULL;} if(p->rchild==a){p->rchild=NULL;} //free(p); 这样直接删除不了，还必须让他的双亲节点指向NULL p=p->rchild; Push(S,p); } } }

void main() { Tree T; cout<<\*************\ cout<<\ 请选择操作 *************************\ cout<<\ 1、创建二叉树 *************************\ cout<<\ 2、先序输出 *************************\空格的地方不能用tab键

cout<<\ 3、中序输出 *************************\键占得字节不一样 cout<<\ 4、后序输出 *************************\ cout<<\*************\ char m;int l; do { cout<<\请输入欲行操作的相应编号：\ cin>>l; if(l==1) {cout<<\请按次序输入二叉树中结点的数值（一个字符），按空格表示空树\ Create(T);} if(l==2){PreOrder(T,PrintElement);} if(l==3){InOrder(T,PrintElement);} if(l==4){PostOrder(T);} cout<<\是否继续(y/n)：\ }while(m=='y'); }

实验结果：