《数据结构》课件第6章.ppt

【实训要求】1.设计一个程序实现上述过程。2.采用二叉链表存储结构。【算法分析】1.可采用输入二叉树的先序遍历序列的方式来建立二叉树。2.采用递归方式进行二叉树的遍历。3.判断叶子结点的条件是其左右孩子均为空。4.层次遍历中，如果A在B之前被访问，则A的孩子必在B的孩子之前被访问。利用这一特性，借助一个先入先出的循环队列，先将根结点入队，只要队伍不为空，则反复执行如下操作：(1)将队首元素输出并出队。(2)将出队元素的左右孩子入队。【程序清单】#includestdlib.h#includestdio.h#definequeuesize100typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}btnode; /*定义二叉链表结点结构*/typedefbtnode*btree; /*定义二叉链表指针类型*/typedefstruct{intfront,rear;btreedata[queuesize]; /*循环队列元素类型为二叉链表结点指针*/intcount;}cirqueue; /*循环队列结构定义*/createbtree(btree*t){ /*输入二叉树的先序遍历序列，创建二叉链表*/charch;if((ch=getchar())==)/*如果读入空格字符，则创建空树*/*t=NULL;else{*t=(btnode*)malloc(sizeof(btnode)); /*申请根结点*t空间*/(*t)-data=ch; /*将结点数据ch放入根结点的数据域*/createbtree((*t)-lchild);/*建立左子树*/createbtree((*t)-rchild);/*建立右子树*/}}preorder(btreet){/*对二叉树进行先序遍历*/if(t){printf(%c,t-data);preorder(t-lchild);preorder(t-rchild);}}inorder(btreet){/*对二叉树进行中序遍历*/if(t){inorder(t-lchild);printf(%c,t-data);inorder(t-rchild);}}postorder(btreet){/*对二叉树进行后序遍历*/if(t){postorder(t-lchild);postorder(t-rchild);printf(%c,t-data);}}error(char*message){/*出错时，调用的返回出错信息，终止程序运行的函数*/fprintf(stderr,error：%s\n,message);exit(1);}leverorder(btreet){cirqueue*q;btreep;q=(cirqueue*)malloc(sizeof(cirqueue)); /*申请循环队列空间*/q-rear=q-front=q-count=0; /*将循环队列初始化为空*/q-data[q-rear]=t;q-count++;q-rear=(q-rear+1)%queuesize; /*将根结点入队*/while(q-count) /*若队列不为空，做以下操作*/if(q-data[q-front]){/*当队首元素不为空指针，做以下操作*/p=q-data[q-front]; /*取队首元素*p*/printf(%c,p-data); /*打印*p结点的数据域信息*/q-front=(q-front+1)%qu