树和森林之间的转换

缘起

需求: 实现 树木 和 森林之间的转换

分析

在【1】和【2】中我们知道了如何将双亲表示法和孩子（双亲）表示法的树转换为长子兄弟法. 所以本文的树采用的统一的数据结构就是长子兄弟法（即树都是二叉树，而且这棵二叉树的特点是根节点没有右子树）

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
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错

//#define LOCAL
using namespace std;

const int MAX_TREE_NUM = 100; // 森林里面最多100棵树

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

BTree* convert(BTree root) // 将二叉树拆成森林, 思想也是沿着右子树不断地拆, 卸胳膊卸腿
{
	BTree *trees = new BTree[MAX_TREE_NUM];
	int top = 0;
	BTree p = root->sibling, q = root;
	while(q)
	{
		trees[top++] = q;
		q->sibling = NULL;
		q = p;
		if (p) p = p->sibling;
	}
	return trees;
}

struct Forest // 森林
{
	BTree trees[MAX_TREE_NUM]; // 数组每个元素都是各棵子树的根节点
	int n; // 实际的树的棵数

	Forest(int n):n(n)
	{
		trees[0] = new BTreeNode('A');
		trees[1] = new BTreeNode('E');
		trees[2] = new BTreeNode('G');

		BTree B = new BTreeNode('B'); // 注意, 这里不能写 BTreeNode('B')， 因为这样的话, 就是在栈上分配内存, 构造器执行完毕之后会被释放掉的. 必须要手动开辟内存
		BTree C = new BTreeNode('C');
		BTree D = new BTreeNode('D');
		BTree F = new BTreeNode('F');

		BTree H = new BTreeNode('H');
		BTree I = new BTreeNode('I');
		BTree J = new BTreeNode('J');

		trees[0]->firstchild = B;
		trees[1]->firstchild = F;
		trees[2]->firstchild = H;
		
		B->sibling = C;
		C->sibling = D;

		H->sibling = I;
		I->sibling = J;
	}

	BTree change() // 森林转换为(二叉)树, 思想就是不断的接到右子树即可
	{
		BTree p = trees[0];
		for (int i =1; i<n;i++)
		{
			p->sibling = trees[i];
			p = trees[i];
		}
		return trees[0];
	}

};

void freeit(BTree root) // 释放整棵树
{
	if (root)
	{
		BTree firstchild = root->firstchild;
		BTree sibling = root->sibling;
		delete root;
		root = NULL;
		freeit(firstchild);
		freeit(sibling);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	BTree root = Forest(3).change();
	BTree *index =  convert(root);
	freeit(root);
	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/

【2】https://yfsyfs.github.io/2019/05/23/%E5%AD%A9%E5%AD%90-%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%E6%B3%95/