孩子兄弟表示法

目录

孩子兄弟表示法

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 1n");
			return;
		}
		if (CS->data == b) {
			int sum = 1;
			while (CS->parent) {
				sum = sum * CS->value;
				if (CS->parent->data == a) {
					printf("The number is %dn", 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
#include
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 1n");
			return;
		}
		if (CS->data == b) {
			int sum = 1;
			while (CS->parent) {
				sum = sum * CS->value;
				if (CS->parent->data == a) {
					printf("The number is %dn", 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:%sn", 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 hospitaln");
			break;
		case'B':printf("10 floorn");
			break;
		case'C':printf("1 central_lobbyn");
			break;
		case 'D':printf("4 wingn");
			break;
		case'E':printf("1 televisionn");
			break;
		case'F':printf("2 couchn");
			break;
		case'G':printf("2 long_corridorn");
			break;
		case'H':printf("1 connecting_corridorn");
			break;
		case'I':printf("21 patient_roomn");
			break;
		case'J':printf("5 supply_roomn");
			break;
		case'K':printf(" 1 bathroomn");
			break;
		case'L':printf(" 4 outletn");
			break;
		case'M':printf("1 bedroomn");
			break;
		case'N':printf("1 sinkn");
			break;
		case'O':printf("2 socketn");
			break;
		case'P':printf("1 faceplaten");
			break;
		case'Q':printf("2 small_rubber_washern");
			break;
		case'R':printf("1 large_rubber_washern");
			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;
}