child兄弟法将树转化为二叉树+parent指针（C语言）

转化为二叉树+parent指针（C语言）"/>

child兄弟法将树转化为二叉树+parent指针（C语言）

孩子兄弟表示法

目录

孩子兄弟表示法

1.孩子兄弟表示法介绍 

2.孩子兄弟表示法特点

3.parent指针

4.实验案例+核心代码+源码（写得有点繁琐，而且里面包括对文件的处理，应用场景不同）

 核心代码：

源码（存在不足，主要还是想突出一下孩子兄弟法）：

---

1.孩子兄弟表示法介绍 

孩子兄弟法可以将一般的树转化为二叉树处理。

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

结点结构图如下表所示：

  其中，data是数据域；firstchild为指针域，指向该结点的第一个孩子；rightsib是指针域，指向该结点的右兄弟。

这样说太抽象了，举个栗子：

我们从根结点来判断，还记得孩子兄弟法怎么表示的了吗？我们一一对应就好了。

 

所以根结点的firstchild指向 A结点 ，rightsib为null：                        

    

 好，第一步完成之后，我们再来看看A

 

 

 然后就是C和B依次判断，由于C和B的第一个孩子和右兄弟都不存在，都为null，所以之前的树用孩子兄弟法表示为：

 

2.孩子兄弟表示法特点

我们再来看看，这是一般的树：

 孩子兄弟法表示树的结构图

好了，大家现在已经对孩子兄弟法有了基本的了解，你会发现它很容易找到一个结点的所有孩子结点 ，比如找到了结点F，看图你会发现F的下一层G、H、K都是F的孩子，所以我只需要遍历一下F的下一层就可以找到F结点的所有孩子结点。

但是，你会发现结点的双亲寻找起来变得困难，举个例子，如图，G指向H，那H的双亲结点是G吗，回到一般的树你会发现，这个G其实是虚假的双亲结点，H的真正双亲结点其实是F，是H结点的上一层中的某个结点，而不是上一个。

3.parent指针

为了解决上述问题，完全可以再增加一个parent指针域来解决快速查找双亲的问题，思路就是将这一层的所有结点的parent指针都指向上一层那个结点，即第一个孩子的双亲结点，举个栗子，我完全可以将G、H、K这一层的parent指针都指向G的双亲结点，即F。

4.实验案例+核心代码+源码（写得有点繁琐，而且里面包括对文件的处理，应用场景不同）

实验要求：

（1）完成二叉树基本操作；（2）完成如下二叉树应用；

   使用树结构存储如下图所示的医院楼房结构：

Figure 1   医院楼房树形结构

  该结构通过读取文件definition.txt文件创建，格式如“hospital 10 floor”，表示hospital有10层floor。将树形结构创建后，可以读取queries.txt中的查询完成对应的操作。

  操作有两种：“what is connecting_corridor”意思是查询connecting_corridor有几个子部件。比如在该图中，connecting_corridor含有5个 supply room，则打印出:

Part connecting_corridor subparts are:      5 supply room

  如果输入：“what is connecting_corridor”，则打印出：Part floor subparts are:4 wing 1 central_lobby

“how many floor hospital”是查询hospital有几个floor，那么打印: Hospital has 10 floor

 核心代码：

//定义结构体
typedef struct CSNode
{char data;//名称int value;//值（对应的数量）struct CSNode* firstchild, * rightsib,*parent;//第一个孩子、右兄弟、双亲指针
}CSNode, * CSTree;

//创建二叉树
void CreateCSTree(CSTree& CS)
{char ch;int value;scanf("%c", &ch);if (ch == '#')CS = NULL;else{scanf("%d", &value);CS = (CSNode*)malloc(sizeof(CSNode));CS->data = ch;CS->value = value;CS->parent = NULL;CreateCSTree(CS->firstchild);CreateCSTree(CS->rightsib);}
}

//连接双亲结点
void CreateFather(CSTree& CS) {if (CS) {CSTree p = CS->firstchild;if (p) {p->parent = CS;while (p->rightsib){p->rightsib->parent = CS;p = p->rightsib;}}CreateFather(CS->firstchild);CreateFather(CS->rightsib);}
}

//先序遍历
void PreOrderTraverse(CSTree CS)
{if (CS){printf("符号是：%c ", CS->data);printf("数值是：%d", CS->value);if (CS->parent) {printf("父亲结点是：%c", CS->parent->data);}printf("\n");PreOrderTraverse(CS->firstchild);PreOrderTraverse(CS->rightsib);}}

//找子结点
void FindChild(char a,CSTree CS)
{if (CS){if (CS->data ==a) {if (CS->firstchild) {CSTree p = CS->firstchild;match(p->data);while (p->rightsib) {match(p->rightsib->data);p = p->rightsib;}}}else {FindChild(a, CS->firstchild);FindChild(a, CS->rightsib);}}
}

//找父结点
void FindFather(char a,char b, CSTree CS) {if (CS) {if (a == b) {printf("The number is 1\n");return;}if (CS->data == b) {int sum = 1;while (CS->parent) {sum = sum * CS->value;if (CS->parent->data == a) {printf("The number is %d\n", sum);}CS = CS->parent;}}else {FindFather(a, b, CS->firstchild);FindFather(a, b, CS->rightsib);}}
}

int main()
{CSTree CS;printf("请输入结点数据(#为空):");	//测试用例://A1B10C1E1#F2##D4G2I21K1N1Q2#R1###L4O2#P1##M2###H1J5######//创建孩子兄弟二叉树CreateCSTree(CS);//创建父亲结点CreateFather(CS);//先序遍历printf("先序遍历:\n");PreOrderTraverse(CS);//menu(CS);printf("请输入你的选择：\n");int choice;scanf("%d", &choice);while (choice != 0) {choose(choice,CS);printf("请输入你的选择：\n");scanf("%d", &choice);}return 0;
}

源码（存在不足，主要还是想突出一下孩子兄弟法）：

#include<stdio.h>
#include<stdlib.h>
void match(char a);
//定义结构体
typedef struct CSNode
{char data;//名称int value;//值（对应的数量）struct CSNode* firstchild, * rightsib,*parent;//第一个孩子、右兄弟、双亲指针
}CSNode, * CSTree;
//创建二叉树
void CreateCSTree(CSTree& CS)
{char ch;int value;scanf("%c", &ch);if (ch == '#')CS = NULL;else{scanf("%d", &value);CS = (CSNode*)malloc(sizeof(CSNode));CS->data = ch;CS->value = value;CS->parent = NULL;CreateCSTree(CS->firstchild);CreateCSTree(CS->rightsib);}
}
//先序遍历
void PreOrderTraverse(CSTree CS)
{if (CS){printf("符号是：%c ", CS->data);printf("数值是：%d", CS->value);if (CS->parent) {printf("父亲结点是：%c", CS->parent->data);}printf("\n");PreOrderTraverse(CS->firstchild);PreOrderTraverse(CS->rightsib);}}
//连接双亲结点
void CreateFather(CSTree& CS) {if (CS) {CSTree p = CS->firstchild;if (p) {p->parent = CS;while (p->rightsib){p->rightsib->parent = CS;p = p->rightsib;}}CreateFather(CS->firstchild);CreateFather(CS->rightsib);}
}
//找子结点
void FindChild(char a,CSTree CS)
{if (CS){if (CS->data ==a) {if (CS->firstchild) {CSTree p = CS->firstchild;match(p->data);while (p->rightsib) {match(p->rightsib->data);p = p->rightsib;}}}else {FindChild(a, CS->firstchild);FindChild(a, CS->rightsib);}}
}
//找父结点
void FindFather(char a,char b, CSTree CS) {if (CS) {if (a == b) {printf("The number is 1\n");return;}if (CS->data == b) {int sum = 1;while (CS->parent) {sum = sum * CS->value;if (CS->parent->data == a) {printf("The number is %d\n", sum);}CS = CS->parent;}}else {FindFather(a, b, CS->firstchild);FindFather(a, b, CS->rightsib);}}
}
//打印相关信息
void menu(CSTree CS) {char buff[255];FILE* p = fopen("C:\\Users\\95270\\source\\repos\\TestRoom3\\queries.txt", "r");if (p == NULL){printf("open error!\n");return;}int i = 1;printf("查询面板，请输入你所要查询的编号：\n");while (!feof(p)) {fgets(buff, 255, p);printf("%d:%s\n", i, buff);i++;}fclose(p);}
//操作选择
void choose(int number, CSTree CS) {switch (number){case 1:FindChild('H', CS);break;case 2:FindChild('I', CS);break;case 3:FindChild('Q', CS);break;case 4:FindChild('K', CS);break;case 5:FindChild('B', CS);break;case 6:FindFather('A', 'B', CS);break;case 7:FindFather('A', 'D', CS);break;case 8:FindFather('A', 'I', CS);break;case 9:FindFather('A', 'M', CS);break;case 10:FindFather('B', 'F', CS);break;case 11:FindFather('A', 'F', CS);break;case 12:FindFather('C', 'C', CS);break;case 13:FindFather('B', 'Q', CS);break;default:break;}
}
//单个字符对应信息
void match(char a) {switch (a){case 'A':printf("1 hospital\n");break;case'B':printf("10 floor\n");break;case'C':printf("1 central_lobby\n");break;case 'D':printf("4 wing\n");break;case'E':printf("1 television\n");break;case'F':printf("2 couch\n");break;case'G':printf("2 long_corridor\n");break;case'H':printf("1 connecting_corridor\n");break;case'I':printf("21 patient_room\n");break;case'J':printf("5 supply_room\n");break;case'K':printf(" 1 bathroom\n");break;case'L':printf(" 4 outlet\n");break;case'M':printf("1 bedroom\n");break;case'N':printf("1 sink\n");break;case'O':printf("2 socket\n");break;case'P':printf("1 faceplate\n");break;case'Q':printf("2 small_rubber_washer\n");break;case'R':printf("1 large_rubber_washer\n");break;default:break;}}
int main()
{CSTree CS;printf("请输入结点数据(#为空):");	//测试用例://A1B10C1E1#F2##D4G2I21K1N1Q2#R1###L4O2#P1##M2###H1J5######//创建孩子兄弟二叉树CreateCSTree(CS);//创建父亲结点CreateFather(CS);//先序遍历printf("先序遍历:\n");PreOrderTraverse(CS);//menu(CS);printf("请输入你的选择：\n");int choice;scanf("%d", &choice);while (choice != 0) {choose(choice,CS);printf("请输入你的选择：\n");scanf("%d", &choice);}return 0;
}