c++ 实现二叉树的拷贝

 1 #include<iostream>
 2 using namespace std;
 3 
 4 //二叉树节点
 5 struct BinaryNode
 6 {
 7     char ch;
 8     BinaryNode* lchild;
 9     BinaryNode* rchild;
10 };
11 BinaryNode* CopyTree(BinaryNode* root);
12 void TreeFree(BinaryNode* root);
13 void Recursion(BinaryNode* root) {
14     if (!root) return;
15     cout << root->ch << " ";
16     Recursion(root->lchild);
17     Recursion(root->rchild);
18 }
19 
20 //初始化二叉树
21 void CreateBinaryTree() {
22     BinaryNode node1 = { 'A',NULL,NULL };
23     BinaryNode node2 = { 'B',NULL,NULL };
24     BinaryNode node3 = { 'C',NULL,NULL };
25     BinaryNode node4 = { 'D',NULL,NULL };
26     BinaryNode node5 = { 'E',NULL,NULL };
27     BinaryNode node6 = { 'F',NULL,NULL };
28     BinaryNode node7 = { 'G',NULL,NULL };
29     BinaryNode node8 = { 'H',NULL,NULL };
30     //建立节点关系
31     node1.lchild = &node2;
32     node1.rchild = &node6;
33     node2.rchild = &node3;
34     node3.lchild = &node4;
35     node3.rchild = &node5;
36     node6.rchild = &node7;
37     node7.lchild = &node8;
38     cout << "原二叉树：n";
39     Recursion(&node1);
40     BinaryNode* p = CopyTree(&node1);
41     cout << "n拷贝后二叉树：n";
42     Recursion(p);
43     //释放拷贝二叉树的内存
44     TreeFree(p);
45 
46 }
47 //二叉树拷贝
48 BinaryNode* CopyTree(BinaryNode* root) {
49     if (!root) return NULL;
50     BinaryNode* ltree= CopyTree(root->lchild);
51     BinaryNode* rtree= CopyTree(root->rchild);
52     
53     BinaryNode* newtree = new BinaryNode;
54     newtree->ch = root->ch;
55     newtree->lchild = ltree;
56     newtree->rchild = rtree;
57     return newtree;
58 }
59 void TreeFree(BinaryNode* root) {
60     if (!root)    return;
61     TreeFree(root->lchild);
62     TreeFree(root->rchild);
63     delete root;
64 }
65 
66 
67 int main() {
68     CreateBinaryTree();
69     return 0;
70 }