实验二 二叉树的前序遍历程序的实现.doc

实验二 二叉树的前序遍历程序的实现 实验报告 姓名： 日期： （以下内容用五号字书写，本页空白不够可续页） 一、实验程序 ………………………………… #includestdio.h #includemalloc.h #define max 22 struct node { int data; struct node *llink; struct node *rlink; } *tree=NULL; struct node *createtree(struct node *tree); void preorder(struct node *t); void main() { printf(请输入二叉树\n); tree=createtree(tree); printf(前序遍历：\n); preorder(tree); printf(\n); } void preorder(struct node *tree) { struct node*p; struct node*s[max]; int top; top=-1; p=tree; do { while(p!=NULL) { printf( %c,p-data); if(p-rlink!=NULL) { top=top+1; s[top]=p-rlink; } p=p-llink; } if(top!=-1) { p=s[top]; top=top-1; } }while(p!=NULL || top!=-1); } struct node *createtree(struct node *tree) { struct node *a,*b,*c,*d,*e; tree=NULL; tree=(struct node *)malloc(sizeof(struct node)); a=(struct node *)malloc(sizeof(struct node)); b=(struct node *)malloc(sizeof(struct node)); c=(struct node *)malloc(sizeof(struct node)); d=(struct node *)malloc(sizeof(struct node)); e=(struct node *)malloc(sizeof(struct node)); tree-data=x; a-data=y; b-data=z; c-data=p; d-data=q; e-data=r; tree-llink=a; tree-rlink=b; a-llink=c; a-rlink=d; c-llink=e; c-rlink=NULL; b-llink=NULL; b-rlink=NULL; d-llink=NULL; d-rlink=NULL; e-llink=NULL; e-rlink=NULL; return(tree); } 实验过程 程序自定义一个二叉树，主程序调用前序遍历子程序实现二叉树的前序遍历。 三、实验分析 定义一个指针变量p，p初值为树根，当p非空则打印当前根节点，如果有字数非空，则将又子树入棧，访问左子树，重复上述循环直至左子树为空。栈满后最右子树进行出栈操作，直至栈空。 实验结论 前序遍历结果