孩子(双亲)表示法转换为长子兄弟法

缘起

接《树的双亲表示法转换为长子兄弟表示法》一文【1】， 我们继续将孩子表示法转化为长子兄弟法.

分析

较双亲表示法而言, 孩子表示法转换为长子兄弟法更为简单. 因为只需要遍历每个节点的孩子节点链表即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错

//#define LOCAL
using namespace std;
const int MAX_NODES = 100;

typedef struct BTreeNode // 长子兄弟表示法
{
	char data;
	BTreeNode *firstchild, *sibling; // 长子、兄弟
	BTreeNode(char data):data(data),firstchild(NULL),sibling(NULL){}
} *BTree;

struct CTree
{
	struct CTreeNode
	{
		char data;
		int index; // 该节点对应的CTBox在nodes中的索引
		CTreeNode *next;
		CTreeNode(char data, int index):data(data),next(NULL),index(index){}
	};

	struct CTBox
	{
		char data;
		CTreeNode *first;
		CTBox(char data):data(data),first(NULL){}
		CTBox(){}
	};

	CTBox nodes[MAX_NODES];

	int root, n;

	CTree()
	{
		root = 0;
		n = 7;
		nodes[0] = CTBox('A');
		nodes[1] = CTBox('B');
		nodes[2] = CTBox('C');
		nodes[3] = CTBox('D');
		nodes[4] = CTBox('E');
		nodes[5] = CTBox('F');
		nodes[6] = CTBox('G');

		CTreeNode *b = new CTreeNode('B', 1);
		CTreeNode *c = new CTreeNode('C', 2);
		CTreeNode *d = new CTreeNode('D', 3);
		CTreeNode *e = new CTreeNode('E', 4);
		CTreeNode *f = new CTreeNode('F', 5);
		CTreeNode *g = new CTreeNode('G', 6);

		nodes[0].first = b;
		b->next = c;
		c->next = d;

		nodes[2].first = e;
		e->next = f;
		f->next = g;
	}

	BTree change() // 孩子表示法转换为长子兄弟法
	{
		return gao(root);
	}

private:

	BTree gao(int r) // r是当前节点
	{
		BTree root = new BTreeNode(nodes[r].data);
		CTreeNode *p = nodes[r].first;
		bool flag = 0;
		while(p)
		{
			BTree child = gao(p->index);
			if (!flag)
			{
				root->firstchild = child;
				flag = true;
			} else{
				child->sibling = root->firstchild->sibling;
				root->firstchild->sibling = child;
			}
			p = p->next;
		}
		return root;
	}

}ctree;


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	BTree root = ctree.change();
	return 0;
}

可以看出, 基本和双亲表示法转长子兄弟法算法一致

参考

【1】https://yfsyfs.github.io/2019/05/22/%E6%A0%91%E7%9A%84%E5%8F%8C%E4%BA%B2%E8%A1%A8%E7%A4%BA%E6%B3%95%E8%BD%AC%E6%8D%A2%E4%B8%BA%E9%95%BF%E5%AD%90%E5%85%84%E5%BC%9F%E8%A1%A8%E7%A4%BA%E6%B3%95/