求树的应用实现树与二叉树的转换的实现
求树的应用:实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法,层次序的非递归算法的实现,应包含建树的实现,实习报告和代码!!!求树的应用:实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法,层次序的非递归算法的实现,应包含建树的实现,实习报告和代码!!!
#include
#include
#define M 100
#define Null 0
typedef struct node
{
int data;
struct node *lchild,*rchild;
}bitree;bitree *que[M];
int front=0,rear=0;bitree *create(){
bitree * t;
int x;
scanf("%d",&x);
if (x==0) t=Null;
else {
t= (bitree *) malloc (sizeof(bitree));
t->data=x;
t->lchild=create();
t->rchild=create();
}
return t;
}void prvorder(bitree * t){ //前序遍历
if (t!=Null){
printf("M",t->data);
prvorder(t->lchild);
prvorder(t->rchild);
}
}
void PreOrderUnrec(bitree *t) //先序遍历非递归算法;
{
bitree *p = t,*Stack[M];
int top = -1;
while (p != Null || top != -1)
{
while (p!=Null) //遍历左子树;
{
printf("M",p->data);
Stack[ top] = p;
p=p->lchild;
}
if (top != -1) //下次while内循环中实现右子树遍历;
{
p = Stack[top--];
p=p->rchild;
}
}
}
void inorder(bitree * t){ //中序遍历
if (t!=Null){
inorder(t->lchild);
printf("M",t->data);
inorder(t->rchild);
}
}void InOrderUnrec(bitree *t) //中序遍历非递归算法;
{
bitree *p = t,*Stack[M];
int top = -1;
while (p != Null || top != -1)
{
while (p!=Null) //遍历左子树;
{
Stack[ top] = p;
p=p->lchild;
}
if (top != -1) //下次while内循环中实现右子树遍历;
{
p = Stack[top--];
printf("M",p->data);
p=p->rchild;
}
}
}
void postorder(bitree * t){ //后序遍历
if (t!=Null){
postorder(t->lchild);
postorder(t->rchild);
printf("M",t->data);
}
}
void PostOrderUnrec(bitree *t) //后序遍历非递归算法;
{
bitree *p = t,*Stack[M];
int top = -1;
char flag[M];//标识,若为'R'则说明左右孩子均已遍历,防止再次走过,形成死循环;
while(p != Null || top != -1)
{
while(p != Null)
{
Stack[ top] = p;
flag[top] = 'L';
p = p->lchild;
}
while(top != -1 && flag[top] == 'R')
{
printf("M",Stack[top--]->data); //flag='R',在此退栈;
}
if(top != -1) {flag[top] = 'R'; p = Stack[top]->rchild;}
}
}void enqueue(bitree *t){
if (front!=((rear 1)%M))
{
rear=(rear 1)%M;
que[rear]=t;
}
}
bitree *delqueue(){
if(front==rear) return Null;
front=(front 1)%M;
return que[front];
}
void levorder(bitree *t){
bitree *p;
if(t!=Null){
enqueue(t);
while (front!=rear)
{
p=delqueue();
printf("M",p->data);
if (p->lchild!=Null) enqueue(p->lchild);
if (p->rchild!=Null) enqueue(p->rchild);
}
}
}
void LevelOrderUnrec(bitree *t) //层次遍历非递归算法;
{
bitree *p,*Queue[M]; //定义队列,存储树结点指针;
int front,rear; //定义队首和队尾指针;
front = rear = 0; //初始化置0,空队列;
if(t != NULL)
{
rear = (rear 1)%M; //队尾指针后移;
Queue[rear] = t; //树根结点入队;
}
while (front != rear) //队列非空时;
{
front = (front 1)%M; //队首指针后移;
p = Queue[front]; //删除队首结点;
printf("%c ",p->data); //输出队首结点的值;
if(p->lchild != NULL) //若存在左孩子,则左孩子指针入队;
{
rear = (rear 1)%M;
Queue[rear] = p->lchild;
}
if(p->rchild != NULL) //若存在右孩子,则右孩子指针入队;
{
rear = (rear 1)%M;
Queue[rear] = p->rchild;
}
}
}
int main(){
bitree *root;
printf(" ");
root=create();
inorder(root);
printf(" ");
InOrderUnrec(root);
printf(" ");
prvorder(root);
printf(" ");
PreOrderUnrec(root);
printf(" ");
postorder(root);
printf(" ");
PostOrderUnrec(root);
printf(" ");
levorder(root);
return 0;
} 下面是马踏棋盘(另外给你的·):一、实验目的1、加深对图的理解,培养解决实际问题的编程能力。
2、根据数据对象的特性,学会数据组织的方法,把现实世界中的实际问题在计算机内部表示出来。3、培养基本的、良好的程序设计技能。
二、实验内容,1) 给出马从任意一个位置出发遍历整个棋盘的一条路径。2) 在1)的基础上给出从该位置出发的所有遍历路径 三、使用仪器,材料电脑,windowx XP Visual Studio C 6。
0 四、实验方法与步骤1、设计思想:整个棋盘可表示为一个M×N的二维数组。假若马目前在位置(i,j)则马下一步可移动的位置0、1、……、7可分别表示为(i-2,j 1),(i-1,j 2),(i 1,j 2),(i 2,j 1),(i 2,j-1),(i 1,j-2), (i-1,j-2), (i-2,j-1)。
当然,这些位置一定在棋盘边界以内(保证下一步移动位置坐标(i,j),有0#include "conio。h"using namespace std;#define edgetype int#define vextype int#define MAX 8typedef struct node{ int vextex;//序号 struct node *next;}edgenode; typedef struct { int vextex; int x,y; edgenode *link;}vexnode; const int px[8]={1,2,2,1,-1,-2,-2,-1};const int py[8]={2,1,-1,-2,-2,-1,1,2}; const int L=8,H=8; vexnode ga[L*H]; //图int visited[L*H]={0}; //全局地图标志是否走过 typedef struct /*顺序栈的结构体类型定义*/ { int stack[L*H]; int top; }seqstack; seqstack s; //全局栈 void setnull(seqstack *s) {s->top=-1;} /*置空栈-由于c语言的数组下标是从0开始的,所以置空栈操作时将栈顶指针放在下标为0之前,即-1处。
*/ int empty(seqstack *s) /*判断当前栈是否为空栈*/ { if(s->toptop>L*H-1) { printf("stack overflow! "); /*发生上溢*/ return 0; } else { s->stack[ s->top] = x; /*栈顶指针上移,数据元素入栈*/ return 1; } } int pop(seqstack *s) /*弹出当前栈s的栈顶元素*/ { if(s->toptop--; return(s->stack[s->top 1]); }/*由于return语句的特点,必须先使top减1,然后再执行return语句。
而此时栈顶元素的表示应该为s->top 1。*/ } void init(){ int n; for (int i=0;i=L||ty>=H) continue; //出界了 else //采用前插法 { p=(edgenode*)malloc(sizeof(edgenode)); p->vextex=ty*L tx; p->next=ga[i]。
link; ga[i]。link=p; // printf("%d ",ga[i]。link->vextex); } } }}void show() //打印邻接表{ int i; printf(" "); for (i=0;i",ga[i]。
vextex); edgenode *p; p=(edgenode*)malloc(sizeof(edgenode)); p=ga[i]。link; while (p!=NULL) { printf("%d ",p->vextex); p=p->next; } printf(" "); }} void showanswer() //打印路径矩形图{ int rank[L*H]; int tag=s。
top; for (int i=L*H-1;i>=0;i--) { rank[s。stack[tag--]]=i; //rank[pop(&s)]=i; } for (i=0;i",n); push(&s,ga[n]。
vextex); //结点入栈 p=ga[n]。link; visited[n]=1; while (p!=NULL) { if (!visited[p->vextex]) { //printf("%d,",p->vextex); //if(HFS(p->vextex)) return 1; HFS(p->vextex); } p=p->next; } if (s。
top==L*H-1) //找到路径 { printf("answer %d: ",sum ); //统计有一点出发的路径个数 showanswer(); printf(" "); //return 1; } visited[s。
stack[s。top]]=0; pop(&s); if (empty(&s)) //没有 { return 0; } return 0; } int main(){ int n; for (n=0;n3、结果分析:程序由于算法的不足,只能计算出从第0格子出发的路径,其他格子出发的路径无法算出来…… 六、总结:通过本次综合实验,我加强了对以往学习的知识的巩固,如栈、链表等。加深了对图的理解,培养解决实际问题的编程能力。根据数据对象的特性,学会了数据组织的方法,把现实世界中的实际问题在计算机内部表示出来。
培养了基本的、良好的程序设计技能。同时体会到算法的高效性永远是程序设计的难点和重点,只有高效的算法才能更好更快的得到满意的答案。
答:#include #include typedef struct Binnode{//二叉树结点结构体 char data; struct Binnode *l...详情>>
问:2014科普知识竞赛答案,在哪里可以找到啊,求分享资源哦。
答:科普知识是可以从网上查找的,可以多学习下的,如果是参加比赛可以多搜集一些资料的,应该会对复习有一定的帮助的,也可以去书店看看相关的书籍。详情>>
答:弄个局域网就行了。 希望对你有帮助。 麻烦好评,谢谢详情>>