二叉树的拷贝

二叉树拷贝也相对简单,我们只需要在遍历的过程中,将每一个有效的节点依次给传递进来的新树的节点衔接起来就可以了。大致的思路我们可以总结一下。

  • malloc一个新节点
  • 拷贝左侧子树、拷贝右侧子树、链接左侧和右侧子树
  • 如果左侧和右侧子树非叶子节点,重复1、2步骤

【实现代码】

TirTNode* copyTree(TirTNode* tree)
{
	// 判断节点是否有效
	if (NULL == tree) return NULL;

	// 生成新的节点
	TirTNode* newTree = (TirTNode*)malloc(sizeof(TirTNode));
	
	// 拷贝值
	newTree->data = tree->data;

	// 递归拷贝左侧子节点
	newTree->leftChild = copyTree(tree->leftChild);
	// 递归拷贝右侧子节点
	newTree->rightChild = copyTree(tree->rightChild);

	// 返回树的指针
	return newTree;
}

调用的时候,只需要将原来树的地址传递给函数作为参数,并找一个树类型的指针接收返回值就可以了。如下:

TirTNode* newTree;
newTree = copyTree(&treeA);
// 打印下树的内容测试结果
showTree(newTree);

发表评论