实验二 树形结构及其应用php
实验内容:树型结构的创建与遍历ios
树型结构的遍历是树型结构算法的基础,本实验要求编写程序演示二叉树的存储结构的创建和遍历过程。算法
实验要求:post
(1) 至少用两种方法,编写创建二叉树的二叉链表存储结构的程序,并用广义表的形式显示并保存二叉树;spa
(2) 采用二叉树的二叉链表存储结构,编写程序实现二叉树的先序、中序和后序遍历的递归和非递归算法以及层序遍历算法,并显示二叉树和相应的遍历序列;指针
(3) 在二叉树的二叉链表存储结构基础上,编写程序实现二叉树的先序、中序和后序线索链表存储结构创建的算法,并用广义表的形式显示和保存二叉树的线索链表;code
(4) 在二叉树的线索链表存储结构上,编写程序分别实现求一个结点的先序(中序、后序)的后继结点的算法;递归
(5) 在 (4) 基础上,编写程序实现对线索二叉树进行先序、中序和后序遍历的非递归算法,并显示线索二叉树和相应的遍历序列。队列
实验备注:ci
1、上传内容: 1. 实验报告 2. 实验程序源代码;打包为rar文件,提交到此处。
2、实验报告格式:见课件下载“实验报告样式.doc”
#include <iostream> #include<cstdlib> #include<cstdio> #include<cstring> #define maxlen 100 using namespace std; struct BTtree { char data; BTtree *lchild; BTtree *rchild; }; char genelist[100];//保存广义表 int i; BTtree* pre_creat_bt()//先序创建二叉树 { char ch; BTtree *T; cin >> ch; if(ch=='#') T=NULL; else { T=(BTtree*)malloc(sizeof(BTtree)); T->data=ch; printf("\n请输入%c结点的左子结点(若是没有那么输入#表明空):",T->data ); T->lchild=pre_creat_bt(); printf("\n请输入%c结点的右子结点(若是没有那么输入#表明空):",T->data ); T->rchild=pre_creat_bt(); } return T; } BTtree * level_create()//层次创建二叉链表 { BTtree* s[maxlen]; int j; char ch; BTtree *T,*p; while(cin >> i >> ch&&(i!=0||ch!='#')) { p=(BTtree*)malloc(sizeof(BTtree)); p->data=ch; p->lchild=NULL; p->rchild=NULL; s[i]=p; if(i==1)T=p; else { j=i/2; if(i%2==0)s[j]->lchild=p;//节点为偶数,i为j的左儿子 else s[j]->rchild=p;//节点为偶数,i为j的左儿子 } } return T; } void pre_order(BTtree *T)//递归先根遍历二叉树 { if(T!=NULL) { cout << T->data; pre_order(T->lchild); pre_order(T->rchild); } } void in_order(BTtree *T)//递归中序遍历二叉树 { if(T!=NULL) { in_order(T->lchild); cout << T->data; in_order(T->rchild); } } void post_order(BTtree *T)//递归后根遍历二叉树 { if(T!=NULL) { post_order(T->lchild); post_order(T->rchild); cout << T->data; } } void npre_order(BTtree *T)//非递归先根遍历二叉树 { BTtree* STACK[maxlen]; int top=maxlen; while(T!=NULL||top!=maxlen) { while(T!=NULL) { cout << T->data; STACK[--top]=T; T=T->lchild; } if(top!=maxlen) { T=STACK[top++]; T=T->rchild; } } } /* 当树非空那么循环,访问,左走 若S不空,取栈顶右走 */ void nin_order(BTtree *T)//非递归中序遍历二叉树 { BTtree* STACK[maxlen]; int top=maxlen; while(T!=NULL||top!=maxlen) { if(T!=NULL) { STACK[--top]=T; T=T->lchild; } else { T=STACK[top++]; cout << T->data ; T=T->rchild; } } } /* 树不空,左走一步不访问 若栈不空,取出栈顶访问 再访问父亲,再右走 */ void npost_order(BTtree *T)//非递归后根遍历二叉树 { struct STACK { BTtree* tree; int flag; } S[maxlen]; int top=maxlen; BTtree * temp; temp=T; while(temp!=NULL||top!=maxlen) { if(temp!=NULL) { S[--top].tree=temp; S[top].flag=1; temp=temp->lchild; } else { if(S[top].flag==2) { T=S[top++].tree; cout << T->data; } else { S[top].flag=2; temp=S[top].tree->rchild; } } } } void lev_order(BTtree* T) { BTtree* Q[maxlen],*q=NULL; int front=0,rear=0;//创建一个空的队列 if(T==NULL)return; Q[rear++]=T;//将根指针入队 while(front!=rear) { q=Q[front]; cout << q->data; if(q->lchild!=NULL) { Q[rear]=q->lchild;//左儿子不是空,将它入队列 rear++; } if(q->rchild!=NULL) { Q[rear]=q->rchild;//右边儿子不是空,将它入队列 rear++; } front++;//完成上面以后将队首元素就能够出队进行下一次循环操做 } } void order(BTtree * T)//遍历二叉链表 { printf("********递归遍历二叉链表***********\n"); printf("\n先序递归遍历二叉链表:"); pre_order(T); printf("\n中序递归遍历二叉链表:"); in_order(T); printf("\n后序递归遍历二叉链表:"); post_order(T); printf("\n********非递归遍历二叉链表***********\n"); printf("\n先序非递归遍历二叉链表:"); npre_order(T); printf("\n中序非递归遍历二叉链表:"); nin_order(T); printf("\n后序非递归遍历二叉链表:"); npost_order(T); printf("\n**********层次遍历二叉链表***********:\n"); lev_order(T); } void print_tree(BTtree *T) /*按广义表方式打印*/ { if(T!=NULL) { if(T->lchild==NULL&&T->rchild==NULL) { genelist[i]=T->data; i++; } else { genelist[i]=T->data; i++; genelist[i]='('; i++; print_tree(T->lchild); genelist[i]=','; i++; print_tree(T->rchild); genelist[i]=')'; i++; } } } void print(BTtree *T) { BTtree *t=T; i=0; genelist[i]='('; i++; print_tree(t); genelist[i]=')'; i++; genelist[i]='\0'; } int main() { BTtree *pre_t=NULL,*lev_t=NULL; int N; printf("********输入1先序创建二叉链表***********\n********输入2层次创建二叉链表***********\n********输入0退出***********\n"); while(cin >> N) { switch(N) { case 1: printf("********先序创建二叉链表***********\n输入根节点(若是没有那么输入#表明空):"); pre_t=pre_creat_bt(); order(pre_t);//遍历二叉链表 printf("\n********二叉树用广义表表示为********:\n"); print(pre_t); for(i=0; genelist[i]!='\0'; i++) cout << genelist[i]; printf("\n"); break; case 2: printf("********层次创建二叉链表***********\n输入节点次序和元素:"); lev_t=level_create(); order(lev_t);//遍历二叉链表*/ printf("\n********二叉树用广义表表示为********:\n"); print(lev_t); for(i=0; genelist[i]!='\0'; i++)cout << genelist[i]; printf("\n"); break; case 0: break ; default : break; } memset(genelist,' ',sizeof(genelist)); printf("********输入1先序创建二叉链表***********\n********输入2层次创建二叉链表***********\n********输入0退出***********\n"); } return 0; } /*1A 2B 3C 4D 5E 6F 7G 8H 9I 10J 0#*/