看看这棵二叉树：

给定根节点，怎样将这棵二叉树拷贝出一棵新的二叉树？

不多逼逼，看代码：

先看二叉树节点结构体和实现代码：

typedef struct BinaryTreeNode
{char data;  //数据struct BinaryTreeNode *left;  //左孩子struct BinaryTreeNode *right;  //右孩子
}Node;

//拷贝二叉树
Node * copyBinaryTree(Node *root)
{if (NULL == root){return NULL;}Node *leftNode = copyBinaryTree(root->left);Node *rlghtNode = copyBinaryTree(root->right);Node *newTree = (Node*)malloc(sizeof(Node));if (NULL == newTree){printf("空间分配失败\n");return NULL;}newTree->left = leftNode;  //拷贝左子树newTree->right = rlghtNode;  //拷贝右子树newTree->data = root->data;  //拷贝数据return newTree;  //返回新树
}

二叉树的节点空间是开辟在堆区的，所以应该手动释放。

看下释放的代码：

//释放二叉树
void freeTree(Node *root)
{if (NULL == root){return;}freeTree(root->left);  //释放左子树freeTree(root->right);  //释放右子树free(root);  //释放根节点root = NULL;
}

测试下代码是否正确：（完整代码）

#include<iostream>
using namespace std;typedef struct BinaryTreeNode
{char data;  //数据struct BinaryTreeNode *left;  //左孩子struct BinaryTreeNode *right;  //右孩子
}Node;//中序遍历二叉树
void inOrder(Node *root)
{if (NULL == root){return;}inOrder(root->left);printf("%c ",root->data);inOrder(root->right);
}//拷贝二叉树
Node * copyBinaryTree(Node *root)
{if (NULL == root){return NULL;}Node *leftNode = copyBinaryTree(root->left);Node *rlghtNode = copyBinaryTree(root->right);Node *newTree = (Node*)malloc(sizeof(Node));if (NULL == newTree){printf("空间分配失败\n");return NULL;}newTree->left = leftNode;  //拷贝左子树newTree->right = rlghtNode;  //拷贝右子树newTree->data = root->data;  //拷贝数据return newTree;  //返回新树
}//释放二叉树
void freeTree(Node *root)
{if (NULL == root){return;}freeTree(root->left);  //释放左子树freeTree(root->right);  //释放右子树free(root);  //释放根节点root = NULL;
}int main()
{//准备数据Node nodeA = { 'A',NULL,NULL };Node nodeB = { 'B',NULL,NULL };Node nodeC = { 'C',NULL,NULL };Node nodeD = { 'D',NULL,NULL };Node nodeE = { 'E',NULL,NULL };Node nodeF = { 'F',NULL,NULL };Node nodeG = { 'G',NULL,NULL };Node nodeH = { 'H',NULL,NULL };Node nodeI = { 'I',NULL,NULL };//建立关系nodeA.left = &nodeB;nodeA.right = &nodeC;nodeB.left = &nodeD;nodeB.right = &nodeE;nodeC.left = &nodeF;nodeC.right = &nodeG;nodeF.left = &nodeH;nodeF.right = &nodeI;//调用函数printf("中序遍历源二叉树结果为：\n");inOrder(&nodeA); printf("\n");printf("中序遍历拷贝二叉树：");Node *copyRoot = copyBinaryTree(&nodeA);inOrder(copyRoot);printf("\n");freeTree(copyRoot);system("pause");return 0;
}

测试结果：