思路：先通过递归一直找到叶子（即最后一层结点）,再回溯，拷贝叶子的左子树，再右子树，然后重复往上面根结点回溯，直到最上层的根结点
释放：释放在堆区创建的结点
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
//二叉树的递归遍历
struct BinaryNode
{
//数据域
char ch;
//指针域
BinaryNode* lchild; //指向左孩子的指针
BinaryNode* rchild; //指向右孩子的指针
};
//二叉树拷贝:返回新拷贝的二叉树根
//拷贝注意深拷贝和浅拷贝
BinaryNode* copyTree(BinaryNode* root)
{
if (root == NULL)
return NULL;
//先拷贝左子树下面的所有结点
BinaryNode* lchild = copyTree(root->lchild);
//再拷贝右子树下面的所有结点
BinaryNode* rchild = copyTree(root->rchild);
//拷贝根结点:每一次递归都要在堆区开辟一块空间来存储当前的结点
BinaryNode* newNode = (BinaryNode*)malloc(sizeof(BinaryNode));
//把值拷贝到新的根
newNode->ch = root->ch;
//每次递归，把当前结点根下的左子树和右子树拷贝过来
newNode->lchild = lchild;
newNode->rchild = rchild;
//每一次递归返回当前根结点
return newNode;
}
//递归遍历
void output_node(BinaryNode* root)
{
//如果当前根为空，说明1：传入的根结点为空
//2：递归到叶子结点下一层，为空结点，返回上一层的根结点函数内部
if (root == NULL)
return;
//先序遍历
printf("%c ", root->ch);
//每次递归查看左子树下面有没有结点可以打印
output_node(root->lchild);
//每次递归查看右子树下面有没有结点可以打印
output_node(root->rchild);
}
//求叶子数量:如果一个根结点的左右子树都为空，说明是叶子
int getLeafNum(BinaryNode* root)
{
if (root == NULL)
return NULL;
//叶子的数量:静态变量只会初始化一次
static int num;
//获取左子树
BinaryNode *lchild = root->lchild;
//获取右子树
BinaryNode* rchild = root->rchild;
//找到一个叶子
if (lchild == NULL && rchild == NULL)
{
num ;
}
//递归:查看当前根的左子树和右子树是否是叶子
getLeafNum(root->lchild);
getLeafNum(root->rchild);
return num;
}
//求二叉树的高度（深度）:一个根结点中左右子树中最大层数加一
int getTreeHeight(BinaryNode* root)
{
//如果当前结点为空，1.传入根结点为空，说明当前二叉树的层数为0
//2.为叶子的下一层：层数为0
if (root == NULL)
return 0;
//获取当前根结点左子树高度
int lheight = getTreeHeight(root->lchild);
//获取当前根结点右子树高度
int rheight = getTreeHeight(root->rchild);
//判断左右子树谁大，取大加一
return lheight > rheight ? lheight 1 : rheight 1;
}
//二叉树的释放
void freeTree(BinaryNode* root)
{
//如果根结点为空：1.传入的根结点为空或
//2.为叶子结点下一层
if (root == NULL)
{
return;
}
//先通过递归找到叶子层，再往上一层层释放根节点，直到最上层根结点
//先释放左子树的所有结点
freeTree(root->lchild);
//再释放右子树所有的结点
freeTree(root->rchild);
//释放过程演示
printf("%c结点被释放n", root->ch);
//释放
free(root);
}
void output()
{
BinaryNode Anode = { 'A',NULL,NULL };
BinaryNode Bnode = { 'B',NULL,NULL };
BinaryNode Cnode = { 'C',NULL,NULL };
BinaryNode Dnode = { 'D',NULL,NULL };
BinaryNode Enode = { 'E',NULL,NULL };
BinaryNode Fnode = { 'F',NULL,NULL };
BinaryNode Hnode = { 'H',NULL,NULL };
BinaryNode Gnode = { 'G',NULL,NULL };
//建立关系
Anode.lchild = &Bnode;
Anode.rchild = &Fnode;
Bnode.rchild = &Cnode;
Cnode.lchild = &Dnode;
Cnode.rchild = &Enode;
Fnode.rchild = &Gnode;
Gnode.lchild =&Hnode;
//二叉树的拷贝:传入最上层的根结点，通过根结点一层层往下找到叶子，再往上面进行回溯
BinaryNode* newNode =copyTree(&Anode);
//打印
output_node(newNode);
//叶子
printf("n叶子数量:%dn", getLeafNum(newNode));
//树高
printf("树的高度:%dn", getTreeHeight(newNode));
//释放二叉树：释放在堆区创建的二叉树
freeTree(newNode);
}
int main()
{
output();
return 0;
}
拷贝函数简化版
代码语言：javascript复制//二叉树拷贝:返回新拷贝的二叉树根
//拷贝注意深拷贝和浅拷贝
BinaryNode* copyTree(BinaryNode* root)
{
if (root == NULL)
return NULL;
//拷贝根结点:每一次递归都要在堆区开辟一块空间来存储当前的结点
BinaryNode* newNode = (BinaryNode*)malloc(sizeof(BinaryNode));
//每次递归，把当前结点根下的左子树和右子树拷贝过来
newNode->lchild = copyTree(root->lchild);
newNode->rchild = copyTree(root->rchild);
//把值拷贝到新的根
newNode->ch = root->ch;
//每一次递归返回当前根结点或者
代码语言：javascript复制//二叉树拷贝:返回新拷贝的二叉树根
//拷贝注意深拷贝和浅拷贝
BinaryNode* copyTree(BinaryNode* root)
{
if (root == NULL)
return NULL;
//拷贝根结点:每一次递归都要在堆区开辟一块空间来存储当前的结点
BinaryNode* newNode = (BinaryNode*)malloc(sizeof(BinaryNode));
//把值拷贝到新的根
newNode->ch = root->ch;
//每次递归，把当前结点根下的左子树和右子树拷贝过来
newNode->lchild = copyTree(root->lchild);
newNode->rchild = copyTree(root->rchild);
//每一次递归返回当前根结点
