C++数据结构X篇_16_二叉树的拷贝和释放（采用递归的方法）

在上篇的基础上，本篇介绍如何进行二叉树的拷贝和释放。从代码中可以看到采用递归方式进行的拷贝、释放操作，基本套路都是一样的。

1. 二叉树的拷贝

#include 
using namespace std;

//定义二叉树节点
class binarynode
{
public:
	char data;			 //节点数据域
	binarynode* lchild;  //左孩子
	binarynode* rchild;  //右孩子
};

//先序遍历二叉树，对原二叉树和拷贝二叉树进行打印
void Recursion(binarynode* root)
{
	if (root == nullptr)
	{
		return;
	}

	cout << root->data << endl;

	//遍历左子树
	Recursion(root->lchild);
	//遍历右子树
	Recursion(root->rchild);
}

//拷贝二叉树
binarynode* CopyBinaryTree(binarynode* root)
{
	if (root == nullptr)
	{
		return NULL;
	}
	//拷贝左子树
	binarynode* lchild = CopyBinaryTree(root->lchild);

	//拷贝右子树
	binarynode* rchild = CopyBinaryTree(root->rchild);

	//创建节点
	binarynode* newnode = new binarynode;

	newnode->data = root->data;
	newnode->lchild = lchild;
	newnode->rchild = rchild;

	return newnode;
}


//创建二叉树
void createtree()
{
	//创建节点
	binarynode node1 = { 'A',NULL,NULL };
	binarynode node2 = { 'B',NULL,NULL };
	binarynode node3 = { 'C',NULL,NULL };
	binarynode node4 = { 'D',NULL,NULL };
	binarynode node5 = { 'E',NULL,NULL };
	binarynode node6 = { 'F',NULL,NULL };
	binarynode node7 = { 'G',NULL,NULL };
	binarynode node8 = { 'H',NULL,NULL };
	//建立节点关系
	node1.lchild = &node2;
	node1.rchild = &node6;
	node2.rchild = &node3;
	node3.lchild = &node4;
	node3.rchild = &node5;
	node6.rchild = &node7;
	node7.lchild = &node8;

	binarynode* root = CopyBinaryTree(&node1);
	Recursion(root);

}

int main()
{
	createtree();
	system("pause");
	return 0;
}
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

运行结果：

2. 二叉树的释放

#include 
using namespace std;

//定义二叉树节点
class binarynode
{
public:
	char data;			 //节点数据域
	binarynode* lchild;  //左孩子
	binarynode* rchild;  //右孩子
};

//遍历二叉树，对原二叉树和拷贝二叉树进行打印
void Recursion(binarynode* root)
{
	if (root == nullptr)
	{
		return;
	}

	cout << root->data << endl;

	//遍历左子树
	Recursion(root->lchild);
	//遍历右子树
	Recursion(root->rchild);
}

//拷贝二叉树
binarynode* CopyBinaryTree(binarynode* root)
{
	if (root == nullptr)
	{
		return NULL;
	}
	//拷贝左子树
	binarynode* lchild = CopyBinaryTree(root->lchild);

	//拷贝右子树
	binarynode* rchild = CopyBinaryTree(root->rchild);

	//创建节点
	binarynode* newnode = new binarynode;

	newnode->data = root->data;
	newnode->lchild = lchild;
	newnode->rchild = rchild;

	return newnode;
}

//释放二叉树内存，进行递归释放
void FreeSpaceBinaryTree(binarynode* root)
{
	if (root == nullptr)
	{
		return;
	}
	//释放左子树
	FreeSpaceBinaryTree(root->lchild);
	//释放右子树
	FreeSpaceBinaryTree(root->rchild);

	//释放当前节点
	delete root;
}

//创建二叉树
void createtree()
{
	//创建节点
	binarynode node1 = { 'A',NULL,NULL };
	binarynode node2 = { 'B',NULL,NULL };
	binarynode node3 = { 'C',NULL,NULL };
	binarynode node4 = { 'D',NULL,NULL };
	binarynode node5 = { 'E',NULL,NULL };
	binarynode node6 = { 'F',NULL,NULL };
	binarynode node7 = { 'G',NULL,NULL };
	binarynode node8 = { 'H',NULL,NULL };
	//建立节点关系
	node1.lchild = &node2;
	node1.rchild = &node6;
	node2.rchild = &node3;
	node3.lchild = &node4;
	node3.rchild = &node5;
	node6.rchild = &node7;
	node7.lchild = &node8;

	binarynode* root = CopyBinaryTree(&node1);
	Recursion(root);
	FreeSpaceBinaryTree(root);

}



int main()
{
	createtree();
	system("pause");
	return 0;
}

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

运行结果：

3. 二叉树的拷贝和释放