目录
一.问题描述：
（1）完成二叉树基本操作；
（2）完成如下二叉树应用；
???使用树结构存储如下图所示的医院楼房结构：
该结构应该是通过读取文件definition.txt文件创建，格式如“hospital 10 floor”，表示hospital有10层floor。
将树形结构创建后，可以读取queries.txt中的查询完成对应的操作。操作有两种：“whatis connecting_corridor”意思是查询connecting_corridor有几个子部件。比如在该图中，connecting_corridor含有5个 supply room，则打印出:
Part connecting_corridor subparts are:
??5 supply_room
“howmany floor hospital”是查询hospital有几个floor，那么打印:
Hospital has 10 floor
?文件definition.txt和queries.txt内容截图如下：
?
二.解决思路:
本实验的难点主要在于，如何按照文件中的给定的内容格式构建出二叉树结构，由于要求是二叉树结构，所以只能采用孩子兄弟结点表示法。
在这里我用了一种类似于双亲表示法的思路，也即利用每一个结点都只有一个双亲的特点。文件中每行第一个字符串是第三个字符串的双亲结点，故每次读入一行时，我先对当前的二叉数进行遍历，寻找与第一个字符串相同的结点，若其没有左孩子结点，则连到左孩子链域，否则判断左孩子有无右兄弟结点， 一直向后连。
另一个难点是如果按照其个数每个存储则要浪费过多空间，故而我在结点结构体中加入了两个数据域，一个用来存放双亲节点下自己的个数，另一个用来存放自己的总个数，这样也便于实现howmany的要求。
三.实现细节
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NAME_SIZE 20
#define OVERFLOW -1
#define ERROR 0
#define OK 1
typedef int Status;
typedef struct TNode {
struct TNode* firstchild;
struct TNode* nextsibling;
char word[NAME_SIZE];//房间名
int num; //房间数
int allnum; //房间总数
}TNode, * BTree;
首先创建结点结构体TNode,其中包含三个数据域，分别存放字符串类型的结点名，int类型的双亲结点下该节点数量和结点总数量。两个链域，分别指向左孩子，右兄弟。
/*遍历查找*/
Status Traverse_Search(BTree T,char name[],TNode**p) {
if (T) {
if (!strcmp(name,T->word))
{
*p = T;
}
if (Traverse_Search(T->firstchild, name,p))
if (Traverse_Search(T->nextsibling, name,p))return OK;
return ERROR;
}
else return OK;
}接着实现traverse_search函数。该函数有三个参数，分别为二叉树根节点，要搜索的节点名字符串，以及一个指针的地址。根据前序遍历的递归算法，每遍历一个结点，对他的节点名与待搜索字符串比较，若相同，则令输入的指针指向该结点，因为输入的是指针的地址，所以该指针会由此改变，指向要找的结点。
/*读入数据并存入二叉树中*/
void Creat_BTree(BTree T0) {
int num = 0;
char parent[NAME_SIZE] = {' '};
BTree T = T0->firstchild= (TNode*)malloc(sizeof(TNode));
if (!T) {
exit(OVERFLOW);
}
FILE* file = fopen("definitions.txt", "r");
fscanf(file, "%s", T->word);
T->num =T->allnum= 1;
T->firstchild = T->nextsibling = NULL;
rewind(file);
while (!feof(file)) {
TNode* p = NULL;
TNode* T1 = (TNode*)malloc(sizeof(TNode));//新节点
if (!T1) {
exit(OVERFLOW);
}
fscanf(file, "%s", parent);
fscanf(file, "%d", &num);
fscanf(file, "%s",T1->word);
T1->firstchild = T1->nextsibling = NULL;
T1->num = num;
Traverse_Search(T, parent, &p);//如果现有的树中存在parent，则将name连到树中该节点后
T1->allnum = num * p->allnum;
if (p) //p非空，树中已有parent，检查是否有firstchild,否则往sibling后面连
{
if (p->firstchild) { //p->first非空
while (p->nextsibling)//p->nextsibling非空，p后移，直至p->nextsibling为空
{
p = p->nextsibling;
}
p->nextsibling = T1;
}
else {
p->firstchild = T1;
}
}
else
{
exit(OVERFLOW);
}
}
fclose(file);
}? ? ? ?然后是实现Create_Tree函数。该函数有一个参数是一个结点指针，以此节点的firstchild指针作为根节点的指针，也即可以理解为加了一个头结点以便于操作。第一步是申请根节点空间并创建。打开文件并读取第一个字符串，这里我用的是fscanf方法，由于各个字段之间有空格，便于读取。将该字符串赋给头结点字符域，两个数字域设为1，链域设为NULL。
? ? ? ?注意，在完成初始化后要把文件内部指针rewind回文件头部，这样是为了之后规律读取，同时还便于eof的判断。完成根节点创建后就简单了，当文件没到EOF时，进入循环。循环中先申请空间构建新结点，将链域都设为NULL，三次fscanf依次读入当前结点的双亲结点，双亲结点下该节点个数，以及该节点的节点名。然后调用traverse_search函数，找到该节点双亲结点，并将该节点连到适当的位置。也即如果该双亲结点有左孩子，就找左孩子的右兄弟域，直到某一个为空指针，连到后面即可。将读到的数字赋给双亲结点下数量，将该上一结点的总个数域与之相乘，赋给总数量域。最后别忘了把文件fclose.如此就基本完成了二叉树的创建和数据的存储。
/*读入问题文件并根据二叉树中内容做出回答*/
void Answer(BTree T) {
FILE* file = fopen("queries.txt", "r");
while (!feof(file))
{
TNode* p = NULL;
char question[20] = { ' ' };
char name[NAME_SIZE] = { ' ' };
char parent[NAME_SIZE] = { ' ' };
fscanf(file, "%s", question);
fscanf(file, "%s", name);
if (!strcmp(question, "whatis"))
{
printf("Part %s subparts are:\n", name);
Traverse_Search(T->firstchild, name, &p);
if (p) {
if (p->firstchild) {
p = p->firstchild;
printf(" %d %s\n", p->num, p->word);
while (p->nextsibling) {
p = p->nextsibling;
printf(" %d %s\n", p->num, p->word);
}
}
else
{
printf(" none\n");
}
}
}
else if (!strcmp(question, "howmany"))
{
BTree q = NULL;
fscanf(file, "%s", parent);
Traverse_Search(T->firstchild, parent,&q);
Traverse_Search(T->firstchild, name, &p);
printf("%s has %d %s\n", parent, p->allnum/q->allnum, name);
}
else {
printf("Invlid input!");
}
}
}? ? ? ? 然后是实现answer函数。先打开文件，若未到文件结尾EOF（这里有一点小问题，后面会反应出来），就进循环。在循环中先读入一个字符串，由于两类问题字段数不同，所以读完第一个字符串进行判断，若为“whatis”,则再读一个字符串，并用traverse_research找到该结点，根据其孩子和孩子的兄弟结点，确定subpart及其个数。并按要求的格式输出。
? ? ? ? 若为“howmany”，则再读入两个字符串，一个是祖先节点，一个是子孙结点，分别找到这两个结点，并将其节点总数相除即可得到待求值，并按要求输出即可。循环结束后关闭文件流。有一个小问题是我在读到最后一行时总会多一个无效输入，个人猜测可能是由于文件结尾空行，或者一开始没有读入或输出操作而直接判断eof导致的问题。
/*释放二叉树*/
void freeTree(TNode* tree)
{
if (tree == NULL)
return;
if (tree->firstchild != NULL)
{
freeTree(tree->firstchild);
tree->firstchild = NULL;
}
if (tree->nextsibling != NULL)
{
freeTree(tree->nextsibling);
tree->nextsibling = NULL;
}
if (tree != NULL)
{
free(tree);
tree = NULL;
}
}后是实现free_Tree函数。用后序遍历的方法依次释放结点即可（好像只能用后序）。
int main()
{
BTree T=(TNode*)malloc(sizeof(TNode));
if (!T) {
exit(OVERFLOW);
}
T->num = 0;
Creat_BTree(T);
Answer(T);
freeTree(T->firstchild);
free(T);
return 0;
}最后只要在主函数中构造头结点并依次调用上述函数，最后释放头结点即可。
结果如下：
?新人创作，请多批评指教。