树的双亲表示法转换为长子兄弟表示法

缘起

我们知道树有4种表示方法. 参见【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
#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 PTree // 双亲表示法
{
	struct PTreeNode
	{
		int parent;
		char data;
		PTreeNode(){}
		PTreeNode(int parent, char data):parent(parent),data(data){}
	};

	PTreeNode nodes[MAX_NODES];
	int root, n;
	PTree()
	{
		ptree.n = 7;
		ptree.root = 0;
		ptree.nodes[0] = PTreeNode(-1,'A');
		ptree.nodes[1] = PTreeNode(0, 'B');
		ptree.nodes[2] = PTreeNode(0, 'C');
		ptree.nodes[3] = PTreeNode(0, 'D');
		ptree.nodes[4] = PTreeNode(2, 'E');
		ptree.nodes[5] = PTreeNode(2, 'F');
		ptree.nodes[6] = PTreeNode(2, 'G');
	}

	BTree change() // 双亲表示法表示的树转换为长子兄弟法表示
	{
		return gao(root); // 注意, 为什么要这样一言堂的设计, 因为这样暴露给调用者比较舒服, 如果写成 BTree change(int root)的话, 调用就变成了 ptree.change(ptree.root), 这不是很奇怪吗?
	}

private:

	BTree gao(int r) // r是根节点
	{
		BTree root = new BTreeNode(nodes[r].data);
		for (int i = 0, j =0; i<n;i++)
		{
			if (nodes[i].parent == r) // 如果是root的直接儿子
			{
				BTree child = gao(i);
				if (!j) // 长子
				{
					root->firstchild = child;
				}
				else // 长子的兄弟
				{
					child->sibling = root->firstchild->sibling; // 头插法到兄弟链表上去
					root->firstchild->sibling = child;
				}
				j++;
			}
		}
		return root;
	}
	

} ptree;

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

参考

【1】https://yfsyfs.github.io/2019/05/22/%E6%A0%91%E7%9A%84%E5%9B%9B%E7%A7%8D%E8%A1%A8%E7%A4%BA%E6%96%B9%E6%B3%95/