数据结构实验报告(全)安工大(6)

p=p->rchild; } } }

void InOrder(BTree t) { if(t) { InOrder(t->lchild); printf(\ InOrder(t->rchild); } }

void PostOrder(BTree t) { if(t) { PostOrder(t->lchild); PostOrder(t->rchild); printf(\ } }

void PostOrder1(BTree t) { PSeqStack S1; PSeqStack S2; BTree p; p=t; S1=Init(); S2=Init(); while(p||!Empty(S2)) { if(p) { Push(S1,p); Push(S2,p); p-p->rchild; } else { Pop(S2,&p); p=p->lchild;

} } while(!Empty(S1)) { Pop(S1,&p); printf(\ } } */

//后序遍历第二种

void PostOrder2(BTree t) { PSeqStack S; Data Sq; BTree p=t; S=Init(); while(p||!Empty(S)) { if(p) { Sq.flag=0;Sq.node=p; Push(S,Sq); p=p->lchild; } else { Pop(S,&Sq); p=Sq.node; if(Sq.flag==0) { Sq.flag=1; Push(S,Sq); p=p->rchild; } else { printf(\ p=NULL; } } } }

BTree create() { BTree T; char c;

scanf(\ if('#' == c)

T=NULL; else {

T =(BTree)malloc(sizeof(BNode)); T->data = c;

T->lchild=create(T->lchild); T->rchild=create(T->rchild); } return T; }

void HBiTree(BTree t) { Pseqqueue q; q=init_seqqueue(); if(t==NULL) return; BTree p=t; printf(\ if(p->lchild) in_seqqueue(q,p->lchild); if(p->rchild) in_seqqueue(q,p->rchild); while(!empty_seqqueue(q)) { out_seqqueue(q,&p); printf(\ if(p->lchild) in_seqqueue(q,p->lchild); if(p->rchild) in_seqqueue(q,p->rchild); } destory_seqqueue(&q); return; }

int leaf(BTree T) {

if (T == NULL) return 0;

if (T->lchild == NULL && T->rchild == NULL) return 1;

return leaf(T->lchild) + leaf(T->rchild);

}

//求叶子的个数 int Height(BTree t) { int h1,h2; if(t==NULL) return 0; else { h1=Height(t->lchild); h2=Height(t->rchild); if(h1>h2) return h1+1; else return h2+1; } }

int main() { BTree T; int a=0; int b=0; T=create(); //PreOrder(T); //InOrder(T); //PostOrder(T); //PreOrder1(T); //InOrder1(T); PostOrder2(T); printf(\ HBiTree(T); printf(\ a=Height(T); printf(\深度为:%d\\n\ b=leaf(T);

printf(\叶子数:%d\\n\ return 0; }

实验心得：这次实验加深了我对二叉树的印象，尤其是对二叉树的各种遍历操作有了一定的了解，从非递归的遍历算法中可以更好的理解先序，中序和后序遍历算法的理解，同时认识到，在设计程序时辅以图形化的描述是非常有用的。