数据结构树与二叉树的转换（二叉树的创建与查询）

针对下图给出的信电学院专业结构关系，选用二叉链作为存储结构，编写程序完成以下操作：

（1）按专业大类进行分类，输出信电学院各专业大类的下属专业名称；

（2）输入任一专业大类的编号，查找并输出该专业大类下属的所有专业名称及统计其所包含的专业总个数。

解题分析

1.先将信电学院专业结构图转换为对应的二叉树

二叉树中每个数据元素，其类型可定义为：

typedef char ElemType;

typedef struct node

{ ElemType data; //每个专业名称用其对应编号表示，输出时再将编号转换为字符串

struct node *lchild,*rchild;

} BTNode;

2.用括号表示法表示出上述二叉树的层次结构

A(B(F(,G(,H(,I))),C(J(,K),D(L(,M(,N)),E(O)))))

3.调用创建二叉树（CreateBTree），先序遍历二叉树（PreOrder）和查找二叉树中指定节点（FindNode）的算法完成题目指定的各功能。

#include<stdio.h> #include<stdlib.h> #include<string.h> typedef char ElemType; typedef struct node { ElemType data; struct node *lchild,*rchild; } BTNode; void CreateBTree(BTNode *&b,char *str); BTNode *FindNode(BTNode *b,ElemType x); void search(BTNode *b,ElemType x); void info(char ch); void PreOrder(BTNode *b); void CreateBTree(BTNode *&b,char *str) { BTNode *St[100],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; //建立的二叉树初始时为空 ch=str[j]; while (ch!='\0') //str未扫描完时循环 { 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) //p为二叉树的根节点 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) { 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); } } void search(BTNode *b,ElemType x) { BTNode *p,*q; int n=0; p=FindNode(b,x); if(p!=NULL) { q=p->lchild; if(q!=NULL) { printf("\n该专业大类包含以下专业：\n"); info(q->data); n ; q=q->rchild; while(q!=NULL) { info(q->data); n ; q=q->rchild; } printf("\n该专业大类共包含%d个专业。\n",n); } else printf("\n编号%c为专业名称，不是专业大类名称，不存在该专业大类！",x); } else printf("\n不存在该专业大类！"); } void info(char ch) { switch(ch) { case 'A':printf("\n%s\n","信电学院(A)");break; case 'B':printf("\n\n%s\n","计算机类(B)");break; case 'C':printf("\n\n%s\n","数学类(C)");break; case 'D':printf("\n\n%s\n","电子类(D)");break; case 'E':printf("\n\n%s\n","物理类(E)");break; case 'F':printf("%s ","软件工程(F)");break; case 'G':printf("%s ","物联网工程(G)");break; case 'H':printf("%s ","数字媒体技术(H)");break; case 'I':printf("%s ","计算机科学与技术(I)");break; case 'J':printf("%s ","数学与应用数学(J)");break; case 'K':printf("%s ","信息与计算科学(K)");break; case 'L':printf("%s ","通信工程(L)");break; case 'M':printf("%s ","电子科学与技术(M)");break; case 'N':printf("%s ","电子与信息工程(N)"); break; case 'O':printf("%s ","应用物理学(O)"); break; } } void PreOrder(BTNode *b) { if (b!=NULL) { info(b->data); //访问根节点 PreOrder(b->lchild); PreOrder(b->rchild); } } void main() { BTNode *b=NULL; ElemType str[100],name; printf("请输入括号表示法所表示的二叉树："); gets(str); CreateBTree(b,str); printf("\n\n信电学院的专业结构如下：\n"); PreOrder(b); printf("\n\n请输入要查找的专业大类的编号："); name=getchar(); search(b,name); }

运行结果

请输入括号表示法所表示的二叉树：A(B(F(,G(,H(,I))),C(J(,K),D(L(,M(,N)),E(O))))) 信电学院的专业结构如下： 信电学院(A) 计算机类(B) 软件工程(F) 物联网工程(G) 数字媒体技术(H) 计算机科学与技术(I) 数学类(C) 数学与应用数学(J) 信息与计算科学(K) 电子类(D) 通信工程(L) 电子科学与技术(M) 电子与信息工程(N) 物理类(E) 应用物理学(O) 请输入要查找的专业大类的编号：E 该专业大类包含以下专业： 应用物理学(O) 该专业大类共包含1个专业。