数据结构实验(二叉树的建立、遍历和应用) |
您所在的位置：网站首页 › 数据结构树及其应用实验报告 › 数据结构实验(二叉树的建立、遍历和应用) |
数据结构实验(二叉树的建立、遍历和应用)
|
实验名称：二叉树的建立、遍历和应用
实验目的：
掌握二叉树这种抽象数据类型的特点；熟练掌握二叉树的链式存储结构的描述方法和具体实现。 实验要求：基于二叉树的二叉链表存储结构实现以下操作： 用先序遍历方法创建二叉树对二叉树进行后序递归遍历和中序非递归遍历求二叉树的所有结点个数、叶子结点个数求二叉树的深度交换二叉树的左右子树（交换后可再次遍历） 实验说明：用菜单调用实现各个功能 按照先序遍历次序递归建立二叉树 参见教材P131算法6.4二叉树后序遍历递归算法二叉树中序非递归遍历算法 参见教材P131算法6.3遍历二叉树的递归应用相关算法 实验内容： 代码： #include #include #include #define OVERFLOW -1 #define num 100 #define OK 1 typedef int Status; typedef char ElemType; typedef struct node{ ElemType data; struct node *lchild,*rchild; }BinTNode,*BinTree; Status CreateTree(BinTree &bt) {//按照先序遍历次序地柜建立二叉树， //ABC@@DE@G@@F@@@ char s; scanf("%c",&s); //如果想要依次输入，就要加getchar(); if(s=='@') bt=NULL; else { if(!(bt=(BinTree )malloc(sizeof(BinTNode)))) exit(OVERFLOW); bt->data=s; CreateTree(bt->lchild); CreateTree(bt->rchild); } return OK; }//CreateTree Status PreOrder(BinTree bt) {//前序遍历非递归算法 BinTree ptr[20];int top=-1; while(bt||top!=-1){ while(bt){ printf("%c",bt->data); ptr[++top]=bt; bt=bt->lchild; } if(top!=-1){ bt=ptr[top--]; bt=bt->rchild; } } return OK; } Status InOrder(BinTree bt) { //二叉树中序遍历递归算法 /* if(bt){ InOrder(bt->lchild); printf("%c",bt->data); InOrder(bt->rchild); } return OK; */ //二叉树中序遍历非递归算法(利用堆栈实现) /* Stack s; InitStack(s); BinTree p=bt; SElemType temp; while(p||!StackEmpty(s)){ if(p){ temp.ptr=p; Push(s,temp);p=p->lchild; } else { if(!StackEmpty(s)) { Pop(s,temp); p=temp.ptr; printf("%c",p->data); p=p->rchild; } } } return OK; */ //二叉树中序遍历非递归算法(利用数组辅助实现) BinTree ptr[20];int top=-1; while(bt||top!=-1){ while(bt){ ptr[++top]=bt; bt=bt->lchild; } if(top!=-1){ bt=ptr[top--]; printf("%c",bt->data); bt=bt->rchild; } } return OK; }//InOrder Status PostOrder(BinTree bt) {//二叉树后序遍历递归算法 /* if(bt){ PostOrder(bt->lchild); PostOrder(bt->rchild); printf("%c",bt->data); } return OK; */ //二叉树后序遍历非递归算法（利用数组模拟栈辅助实现） if(!bt) return OK; BinTree s[num]; BinTree pre; int top=-1; while(bt||top!=-1){ if(bt){//先将左边元素全部入栈 s[++top]=bt; bt=bt->lchild; } else { bt=s[top];//取出栈顶元素 if(bt->rchild==NULL||bt->rchild==pre) { printf("%c",bt->data); top--; pre=bt; bt=NULL;//当有一个元素被访问时，栈顶应该为他的双亲结点，当bt为NULL时下一次被取出来的结点恰好就是双亲 } else { bt=bt->rchild; } } } return OK; }//PostOrder Status LevelOrder(BinTree bt) {//二叉树层序遍历非递归算法（利用数组模拟队列辅助实现） if (bt== NULL) return OK; BinTree s[num]; int front, rear; front = rear = 0; s[rear++] = bt; // 根结点入队 while (front != rear) // 当队列非空时 { printf("%c",s[front]->data); // 输出队头元素结点信息 if (s[front]->lchild) { s[rear++] = s[front]->lchild; // 若结点q存在左孩子，则将左孩子入队； } if (s[front]->rchild) { s[rear++] = s[front]->rchild; // 若结点q存在右孩子，则将右孩子入队； } front++; } return OK; }//LevelOrder int size(BinTree bt) {//统计二叉树中所有结点个数 if(bt==NULL) { return 0; } return size(bt->lchild)+size(bt->rchild)+1; }//size int LeafCount(BinTree BT) {//统计二叉树中叶子结点个数 if(BT==NULL)return 0; else if(!BT->lchild&&!BT->rchild) { return 1; } return LeafCount(BT->lchild)+LeafCount(BT->rchild); }//LeafCount int Depth(BinTree bt) {//求二叉树深度 int right,left,h; if(!bt) return 0; else { left=Depth(bt->lchild); right=Depth(bt->rchild); if(left>=right) h=left+1; else h=right+1; } return h; }// Depth Status Exchange(BinTree bt) {//交换二叉树左右子树 if(!bt||(!(bt->rchild)&&!(bt->lchild))) return OK; else { BinTree temp=bt->lchild; bt->lchild=bt->rchild; bt->rchild=temp; Exchange(bt->lchild); Exchange(bt->rchild); } return OK; }// Exchange /*图示： A A / \ B Exchange B / \ -------> / \ c D D C / \ / \ E F F E \ / G G */ void main() { BinTree bt;int xz=1; int yz,sd; printf("二叉树的建立及其基本操作 \n"); printf("==================================\n"); printf("1.建立二叉树的存储结构 \n"); printf("2.二叉树的基本操作 \n"); printf("3.交换二叉树的左右 \n"); printf("0.退出系统 \n"); printf("============================\n"); while(xz) { printf("请选择: (0-3) \n"); scanf("%d",&xz); getchar(); switch(xz) {//输入：ABC@@DE@G@@F@@@ 输出： CBEGDFA case 1:printf("输入二叉树的先序遍历序列节点值： \n"); CreateTree(bt); printf("二叉树的链式存储结构建立完成！\n"); printf("\n");break; case 2: printf("该二叉树的前序序列是："); PreOrder(bt);printf("\n"); printf("该二叉树的中序遍历序列是："); InOrder(bt);printf("\n"); printf("该二叉树的后序遍历序列是："); PostOrder(bt);printf("\n"); printf("该二叉树的层序遍历序列是："); LevelOrder(bt); printf("\n"); printf("该二叉树的结点的个数是: %4d\n",size(bt)); yz=LeafCount(bt);printf("叶子结点个数是:%4d\n",yz); sd=Depth(bt);printf("该二叉树的深度是:%4d\n",sd); printf("\n");break; case 3: Exchange(bt); printf("该二叉树已交换左右子树！\n"); printf("交换后该二叉树的前序序列是："); PreOrder(bt);printf("\n"); printf("交换后该二叉树的中序遍历序列是："); InOrder(bt);printf("\n"); printf("交换后该二叉树的后序遍历序列是："); PostOrder(bt);printf("\n"); printf("交换后该二叉树的层序遍历序列是："); LevelOrder(bt); printf("\n"); printf("交换后该二叉树的结点的个数是: %4d\n",size(bt)); yz=LeafCount(bt);printf("交换后叶子结点个数是:%4d\n",yz); sd=Depth(bt);printf("交换后该二叉树的深度是:%4d\n",sd); printf("\n");break; case 0: break; default:printf("输入错误！不在(0-3)范围内\n");break; } } }运行结果： to be continued how 2020/1/19 |
【本文地址】
今日新闻 |
推荐新闻 |