《数据结构课程设计》二叉树基本操作实验程序（10种基本操作）

#include"head.h" void creatbtnode(btnode *&b,char *str)//非递归方法构造二叉树 { btnode *s[20],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case '(': top++; s[top]=p; k=1; break; case ')': top--; break; case ',': k=2; break; default: p=(btnode*)malloc(sizeof(btnode)); p->data=ch; p->lchild=p->rchild=NULL; if(b==NULL) b=p; else { switch(k) { case 1: s[top]->lchild=p; break; case 2: s[top]->rchild =p; break; } } } ch=str[++j]; } printf("构造二叉树成功\n"); } void creat(btnode *&b) { elemtype x; printf("请输入要建立的结点元素:"); scanf("%c",&x); getchar(); if(x==' ') b=NULL; else { b=(btnode *)malloc(sizeof(btnode)); b->data =x; creat(b->lchild); creat(b->rchild); } } btnode * findnode(btnode *b,elemtype x)//查找某个结点 { btnode *p; if(b==NULL) return NULL; else if(b->data==x) return b; else { p=findnode(b->lchild,x); if(p!=NULL) return p; else { return findnode(b->rchild,x); } } } int nodes(btnode *p)//求二叉树中结点的个数 { int lnum=0,rnum=0; if(p==NULL) return 0; else if(p->lchild==NULL&&p->rchild==NULL) return 1; else { lnum=nodes(p->lchild); rnum=nodes(p->rchild); return (lnum+rnum+1); } } int btnodedepth(btnode *b)//求二叉树的深度 { int ldep,rdep; if(b==NULL) return 0; else { ldep=btnodedepth(b->lchild); rdep=btnodedepth(b->rchild); return (ldep>rdep)?(ldep+1):(rdep+1); } } void dispbtnode(btnode *b)//输出二叉树 { if(b!=NULL) { printf("%c",b->data ); if(b->lchild!=NULL||b->rchild!=NULL) { printf("("); if(b->lchild!=NULL) dispbtnode(b->lchild); if(b->rchild!=NULL) { printf(","); dispbtnode(b->rchild); } printf(")"); } } } void lchildnode(btnode * b)//求左孩子结点 { if(b->lchild ==NULL) printf("该结点没有左孩子!\n"); else printf("该结点的左孩子为%c\n",b->lchild ->data ); } void rchildnode(btnode * b)//求右孩子结点 { if(b->rchild ==NULL) printf("该结点没有右孩子!\n"); else printf("该结点的右孩子为%c\n",b->rchild->data); } int btwidth(btnode *b)//求二叉树的宽度 { struct { int lno;//保存结点的层数 btnode * p; }Q[MAXSIZE];//建立队列 int front,rear; int lnum,max,i,n; front=rear=0; if(b!=NULL) { rear++; Q[rear].p=b; Q[rear].lno=1; while(rear!=front) { front++; b=Q[front].p; lnum=Q[front].lno; if(b->lchild!=NULL) { rear++; Q[rear].p=b->lchild; Q[rear].lno=lnum+1; } if(b->rchild!=NULL) { rear++; Q[rear].p=b->rchild ; Q[rear].lno=lnum+1; } } max=0; lnum=1; i=1; while(i<=rear)//此时rear等于二叉树结点的个数 { n=0; while(i<=rear&&Q[i].lno==lnum) { n++; i++; } lnum=Q[i].lno; if(n>max)//求结点数最多的一层结点的个数 max=n; } return max; } else return 0; } int leafnodes(btnode *b)//求叶子结点的个数 { int lnum=0,rnum=0; if(b==NULL) return 0; else if (b->lchild==NULL&&b->rchild ==NULL) return 1; else { lnum=leafnodes(b->lchild); rnum=leafnodes(b->rchild); return (lnum+rnum); } } int childnum(btnode *p)//求某接点的子孙个数 { int i,j; i=nodes(p->lchild); j=nodes(p->rchild); return (i+j); }