树：二叉树的内存拷贝和内存释放

秒速五厘米 2022-05-31 10:28 204阅读 0赞

**同样是利用递归思想进行拷贝和释放，大家把递归思想领悟就ok了**。

# 二叉树的内存拷贝算法 #

//拷贝二叉树 前序递归拷贝
    void Copy_PreOrderTraverse(BiTree* dest,BiTree src)
    {
    	if (NULL != src)
    	{
    		*dest = malloc(sizeof(BiTNode));
    		(*dest)->data = src->data;
    		Copy_PreOrderTraverse(&(*dest)->lchild,src->lchild);
    		Copy_PreOrderTraverse(&(*dest)->rchild,src->rchild);
    	}
    	else
    	{
    		*dest = NULL;
    	}
    }

# 二叉树的内存释放算法 #

//二叉树内存释放 前序递归释放内存
    void Free_PreOrderTraverse(BiTree tree)
    {
    	if (NULL != tree)
    	{
    		BiTree lchild = tree->lchild;
    		BiTree rchild = tree->rchild;
    		free(tree);
    		Free_PreOrderTraverse(lchild);
    		Free_PreOrderTraverse(rchild);
    	}
    }

# 完整代码 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    typedef char EleType;
    typedef struct BiTNode
    {
    	EleType data;//数据结点数据域
    	struct BiTNode	*lchild, *rchild;//左孩子，右孩子结点指针域
    }BiTNode,*BiTree;
    
    //约定通过前序遍历创建结点
    //每个结点都有左右孩子，孩子不存在为NULL
    void CreatBiTree(BiTree* tree)
    {
    	char c;
    	scanf("%c",&c);
    	if (' '== c)
    	{
    		*tree = NULL;
    	}
    	else
    	{
    		*tree = (BiTNode*)malloc(sizeof(BiTNode));
    		(*tree)->data = c;
    		CreatBiTree(&(*tree)->lchild);//创建左子树
    		CreatBiTree(&(*tree)->rchild);//创建右子树
    	}
    }
    void VisitNode(EleType data)
    {
    	printf("%c ", data);
    	return;
    }
    //前序遍历
    void PreOrderTraverse(BiTree tree)
    {
    	if (NULL != tree)
    	{
    		VisitNode(tree->data);
    		PreOrderTraverse(tree->lchild);
    		PreOrderTraverse(tree->rchild);
    	}
    }
    
    //拷贝二叉树 前序递归拷贝
    void Copy_PreOrderTraverse(BiTree* dest,BiTree src)
    {
    	if (NULL != src)
    	{
    		*dest = malloc(sizeof(BiTNode));
    		(*dest)->data = src->data;
    		Copy_PreOrderTraverse(&(*dest)->lchild,src->lchild);
    		Copy_PreOrderTraverse(&(*dest)->rchild,src->rchild);
    	}
    	else
    	{
    		*dest = NULL;
    	}
    }
    //二叉树内存释放 前序递归释放内存
    void Free_PreOrderTraverse(BiTree tree)
    {
    	if (NULL != tree)
    	{
    		BiTree lchild = tree->lchild;
    		BiTree rchild = tree->rchild;
    		free(tree);
    		Free_PreOrderTraverse(lchild);
    		Free_PreOrderTraverse(rchild);
    	}
    }
    
    int main(int argc, char *argv[])
    {
    	BiTree tree = NULL,newTree = NULL;
    	printf("请按前序遍历的方式输入结点数据，孩子结点为NULL用空格代替：");
    	CreatBiTree(&tree);
    	Copy_PreOrderTraverse(&newTree, tree);
    	printf("源二叉树的前序遍历：");
    	PreOrderTraverse(tree);
    	printf("\n新二叉树的前序遍历：");
    	PreOrderTraverse(newTree);
    	printf("\n");
    	//释放二叉树内存
    	Free_PreOrderTraverse(newTree);
    	return 0;
    }

# 代码运行测试 #

我们下图的二叉树进行测试。  
![Center][]  
  
运行结果如下，注意：我们创建结点时的前序输入:ABC\_\_D\_\_EF\_\_G\_\_，**一个\_表示一个空格哟**。

![Center 1][]

[Center]: /images/20220531/7075c2481e404e348c04be07fd2098cf.png
[Center 1]: /images/20220531/a3c4fa049f76422da58d4b3fd4e4c76b.png