二叉树基本问题 | 顾建伟个人博客
现在的位置: 首页 > Code > 正文
二叉树基本问题
2014年04月21日 Code, 电脑相关 ⁄ 共 3218字 暂无评论

分享到:


以验证复制可以运行

基本函数 [code] #include<stdio.h> #include<malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; }BTNode; void CreateBTNode(BTNode *&b,char *str) { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case'(':top++;St[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:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; } } BTNode *FindNode(BTNode *b,ElemType x) //返回data域为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); } } BTNode *LchildNode(BTNode *p) //返回*p结点的左孩子结点指针 { return p->lchild; } BTNode *RchildNode(BTNode *p) //返回*p结点的右孩子结点指针 { return p->rchild; } int BTNodeDepth(BTNode *b) //求二叉树b的深度 { int ;childdep,rchilddep; if(b==NULL) return(0); else { lchilddep=BTNodeDepth(b->lchild); //左子数的高度 rchilddep=BTNodeDepth(b->rchild); //右子树的高度 return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); } } void DispBTNode(BTNode *b) //广义表输出二叉树 { if(b!=BULL) { printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) { printf("("); DispBTNode(b->lchild); if(b->rchild!=NULL) printf(","); DispBTNode(b->rchild); printf(")"); } } } int BTWidth(BTNode *b) //求二叉树宽度 { struct { int lno; //结点的层次编号 BTNode *p; //结点指针 }Qu[MaxSize]; //定义顺序非循环队列 int front,rear; //定义队首和队尾指针 int lnum,max,i,n; front=rear=0; //置队列为空 if(b!=NULL) { rear++; Qu[rear].p=b; //根结点指针入队 Qu[rear].lno=1; //根结点的层次编号为1 while(rear!=front) //队列不为空 { front++; b=Qu[front].p; //队头出队 lnum=Qu[front].lno; if(b->lchild!=NULL) //左孩子入队 { rear++; Qu[rear].p=b->lchild; Qu[rear].lno=lnum+1; } if(b->rchild!=NULL) //右孩子入队 { rear++; Qu[rear].p=b->rchild; Qu[rear].lno=lnum+1; } } max=0;lnum=1;i=1; while(i<=rear) { n=0; while(i<=rear&&Qu[i].lno==lnum) { n++;i++; //求每层的结点数 } lnum=Qu[i].lno; if(n>max) max=n; } return max; } else return 0; } int Nodes(BTNode *b) //求二叉树的结点个数 { int num1,num2; if(b==NULL) return 0; else if(b->lchild==NULL&&b->rchild==NULL) return 1; else { num1=Nodes(b->lchild); num2=Nodes(b->rchild); return(num1+num2+1); } } int LeafNodes(BTNode *b) //求二叉树的叶子结点个数 { int num1,num2; if(b==NULL) return 0; else if(b->lchild==NULL&&b->rchild==NULL) return 1; else { num1=LeafNodes(b->lchild); num2=LeafNodes(b->rchild); return(num1+num2); } } [/code] 主函数 [code] #include<stdio.h> type char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; }BTNode; extern void CreateBTNode(BTNode *&b,char *str); extern BTNode *FindNode(BTNode *b,ElemType x); extern BTNode *LchildNode(BTNode *p); extern BYNode *RchildNode(BTNode *p); extern int BTNodeDepth(BTNode *b); extern void DispBTNode(BTNode *b); extern int BTWidth(BTNode *b); extern int Nodes(BTNode *b); extern int LeafNodes(BTNode *b); void main() { BTNode *b,*p,*lp,*rp; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); Printf("\n"); printf("(1)输出二叉树:"); DispBTNode(b);printf("\n"); printf("(2)'H'结点:"); p=FindNode(b,'H'); if(p!=NULL) { lp=LchildNode(p); if(lp!=NULL) printf("左孩子为%c",lp->data); else printf("无左孩子"); rp=RchildNode(p); if(rp!=NULL) printf("右孩子为%c",rp->data); else printf("无右孩子"); } printf("\n"); printf("(3)二叉树的深度:%d\n",BTNodeDepth(b)); printf("(4)二叉树的宽度:%d\n",BTWidth(b)); printf("(5)二叉树的结点个数:%d\n",Nodes(b)); printf("(6)二叉树的叶子结点个数:%d\n",LeafNode(b)); printf("\n";) } [/code]

说出你的想法!
有事加我的QQ:932404999(微博ID:顾建伟个人博客网)
×