loxt.zip_数值算法/人工智能

#include"stdio.h" #include"malloc.h" #define NULL 0 #define MAX 100 #include<iostream.h> //---------------------------------------------------------- struct bitnode{ int data; struct bitnode *lchild,*rchild; }bitnode; //---------------------------------------------------------- struct bitnode * search(struct bitnode *t,int key)//查找关键字 { if((!t)||key==t->data)return (t); else if(key<(t->data)) return(search(t->lchild,key)); else return(search(t->rchild,key)); } //----------------------------------------------------------- struct bitnode * searchbst(struct bitnode *t,int key,struct bitnode *f,struct bitnode *&p) { if(!t){p=f; return (t);} else if(key==t->data) {p=t; return (p); } else if(key<t->data) return searchbst(t->lchild,key,t,p); else return searchbst(t->rchild,key,t,p); } //--------------------------------------------------------- struct bitnode * insertbst(struct bitnode *t,int e,struct bitnode *p)//生成二叉排序树 { struct bitnode *s; if(!(searchbst(t,e,NULL,p))) {s=(struct bitnode *)malloc(sizeof(struct bitnode)); s->data=e; s->lchild=NULL; s->rchild=NULL; if(!p)t=s; else if(e<p->data) p->lchild=s; else p->rchild=s; return (t); }else return (NULL); } //------------------------------------------------------------ void visit(struct bitnode *t)//输出遍历的元素 {printf("%d\n",t->data);} //----------------------------------------------------------- void middlesearch(struct bitnode *t)//中序遍历二叉树 { if(t) { if(t->lchild) middlesearch(t->lchild); if(t)visit(t); if(t->rchild) middlesearch(t->rchild); } } //---------------------------------------------------------- void foresearch(struct bitnode *t)//先序遍历二叉树 { if(t) { if(t)visit(t); if(t->lchild) foresearch(t->lchild); if(t->rchild) foresearch(t->rchild); } } //------------------------------------------------------------ void backsearch(struct bitnode *t)//后序遍历二叉树 { if(t) { if(t->lchild) backsearch(t->lchild); if(t->rchild) backsearch(t->rchild); if(t)visit(t); } } //------------------------------------------------------------ void level(struct bitnode *b)//利用队列层次遍历二叉树 { int rear=0,front=0; struct bitnode *qu[MAX],*p; if(b) { rear++; qu[rear]=b; while(front!=rear) { front=(front+1)%MAX; p=qu[front]; printf("%d\n",p->data); if(p->lchild!=NULL) { rear=(rear+1)%MAX; qu[rear]=p->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%MAX; qu[rear]=p->rchild; } } } } //------------------------------------------------------------ void inorder(struct bitnode *t)//中序非递归遍历二叉树 { int i=0; struct bitnode *p,*s[MAX]; if(t) { p=t; do { while(p!=NULL) { s[i++]=p; //模拟栈 p=p->lchild; } if(i>0) { p=s[--i]; printf("%d\n",p->data); p=p->rchild; } }while(i>0||p!=NULL); } } //------------------------------------------------------------ void change(struct bitnode *t)//交换左右子树 { struct bitnode *p; if(t) { if(t->lchild||t->rchild) { p=t->lchild; t->lchild=t->rchild; t->rchild=p; } if(t->lchild)change(t->lchild); if(t->rchild)change(t->rchild); } } //------------------------------------------------------------- int treedepth(struct bitnode *b)//递归求树的深度 { int lchilddep,rchilddep; if(b==NULL) return (0); else { lchilddep=treedepth(b->lchild); rchilddep=treedepth(b->rchild); if(lchilddep>rchilddep) return (lchilddep+1); else return (rchilddep+1); } } //-------------------------------------------------------------- int leafsum(struct bitnode *t)//递归求叶子结点数（我当时点想出来架，厉害） { int n=0; if(t==NULL) return (0); else { if(t->lchild||t->rchild) n=leafsum(t->lchild)+leafsum(t->rchild); return (n+1); } } //---------------------------------------------------------------- void main() { struct bitnode *t=NULL,*m,*p=NULL; int c; int e; printf("1--插入生成二叉排序树\n2--先序遍历二叉树\n3--中序遍历二叉树\n4--后序遍历二叉树\n5--利用队列层次遍历二叉树\n6--中序非递归遍历二叉树\n7--查找关键字\n8--交换左右子树\n9--递归求树的深度\n10--递归求叶子结点数\n0--结束！\n\n\n"); while(1) { printf("请选择(1-10)：\n"); scanf("%d",&c); if(c==0)break; else if(c<1||c>10) {printf("输入有误!!\n\n");continue;} else switch(c) { case 1:printf("请输入结点值：\n"); while(1) { scanf("%d",&e); if(e==0)break; t=insertbst(t,e,p);//插入生成二叉排序树 }break; case 2:foresearch(t);break;//先序遍历二叉树 case 3:middlesearch(t);break;//中序遍历二叉树 case 4:backsearch(t);break;//后序遍历二叉树 case 5:level(t);break;//利用队列层次遍历二叉树 case 6:inorder(t);break;//中序非递归遍历二叉树 case 7:printf("请输入要查找的关键字：\n"); scanf("%d",&e);//输入关键字 if(m=search(t,e))//查找关键字 printf("查找成功:%d\n",m->data); else printf("查找不成功!!\n\n"); break; case 8:change(t);break;//交换左右子树 case 9:printf("%d\n",treedepth(t));break;//递归求树的深度 case 10:printf("%d\n",leafsum(t)-1);break;//递归求叶子结点数 } } }