数据结构实验程序参考

printf(\ break; case 0:break;

default:printf(\

} }while(c!=0); }

4.二叉树基本操作

#include \#define MAX 20 typedef struct btnode { char data;

struct btnode *lchild, *rchild; } Bitnode,*Bitree;

Bitnode* CreatBitree_pre()/*先序建立二叉树*/ { Bitnode *t; char ch; ch=getchar(); if (ch==' ') t=NULL;

else { t=(Bitnode*)malloc(sizeof(Bitnode)); t->data=ch;

t->lchild=CreatBitree_pre();

t->rchild=CreatBitree_pre(); } return t; }

Bitnode *CreatBitree_level()/*按层次顺序建立二叉树*/ /*此算法可修改得更完善些*/

{ Bitnode *Q[100];

int front=1,rear=0; /*队列指针如此设定，便于操作*/ char ch;

Bitnode *root=NULL,*s;

while((ch=getchar())!='#') /* '#'为输入结束标志*/ { if(ch==' ') s=NULL; /* 输入空格为虚结点*/ else

{ s=(Bitnode *)malloc(sizeof(Bitnode));/*建立新结点*/ s->data=ch; s->lchild=NULL; s->rchild=NULL; }

Q[++rear]=s; /*虚结点指针NULL或新结点地址入队*/ if(rear==1) root=s; /*第一个结点为根结点*/ else

{ if(s&&Q[front]) /* 孩子和双亲结点都不是虚结点*/ if(rear%2==0)

Q[front]->lchild=s;/* 新结点为左孩子*/ else Q[front]->rchild=s;/*新结点为右孩子*/

if(rear%2==1) front++; /*左右孩子都已处理结点出队*/ }

}

return root; }

preorder(Bitnode *t) { if(t)

{ printf(\ preorder(t->lchild); preorder(t->rchild); } }

inorder(Bitnode *t) { if (t)

{ inorder(t->lchild); printf(\ inorder(t->rchild); } }

inorder2(Bitnode *t) /*中序遍历非递归算法*/ { Bitnode *p, *stack[MAX]; int top=-1; p=t; do { while(p)

{ stack[++top]=p; p=p->lchild;} if(top>=0)

{ p=stack[top--]; printf(\ p=p->rchild; }

}while( p||(top>=0)); }

postorder(Bitnode *t) { if(t)

{ postorder(t->lchild); postorder(t->rchild); printf(\ } }

void leveltraversing(Bitnode *t) /*按层次遍历*/ { Bitnode *Q[100], *p ;

int front=-1,rear=-1; /*辅设一个简易队列*/ p=t;

if(p) printf(\访问根结点并将其指针入队列*/ while( front!=rear)

{ p=Q[++front]; /*出队*/ if(p->lchild)

{ printf(\ /*访问左孩子并将其指针入队*/ Q[++rear]=p->lchild; } if(p->rchild)