一、二叉树的复制

已经创建好的二叉树，首先我们对它进行判空操作，再创建新的根结点 NewT，把根结点T 赋给 NewT，递归复制左(右)子树。

// 一、复制二叉树
void Copy(BiTree T, BiTree &NewT)
{
	if(T==NULL ){   //如果是空树，递归结束
		NewT=NULL;
		return;
	}
	else{
		NewT = new BiTNode;
		NewT->data = T->data;			//复制根结点
		Copy(T->lchild, NewT->lchild);  //递归复制左子树
		Copy(T->rchild, NewT->rchild);  //递归复制右子树
	}
}

---

二、计算二叉树的深度

【分析】：1、树为空则深度为0；2、否则递归计算左(右)子树的深度；3、取子树最大的深度，再加1。

// 二、计算二叉树的深度
int Depth(BiTree T){
	int m,n;
	if(T== NULL)
        return 0;  //如果是空树，深度为0，递归结束
	else {
            m=Depth(T->lchild);	  //递归计算左子树的深度记为m
            n=Depth(T->rchild);	  //递归计算右子树的深度记为n
            if(m>n)
                return(m+1);  //二叉树的深度为m 与n的较大者加1
            else
                return (n+1);
	}
}

---

三、计算二叉树的结点

开始也是判空，否则结点个数为左子树的结点个数+右子树的结点个数+1。

// 三、计算二叉树的结点
int NodeCount(BiTree T){
     if(T==NULL) return 0;  			// 如果是空树，则结点个数为0，递归结束
     else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;
     //否则结点个数为左子树的结点个数+右子树的结点个数+1
}

---

完整代码如下：

#include<iostream>
using namespace std;

// 二叉树的二叉链表存储表示
typedef struct BiNode{
	char data;						//结点数据域
	struct BiNode *lchild, *rchild;	//左右孩子指针
}BiTNode, *BiTree;

// 先序建立二叉链表
void CreateBiTree(BiTree &T){
	// 按先序次序输入二叉树中结点的值(一个字符)，创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;      //输入先序序列
	if(ch=='#')
        T=NULL;		//递归结束，建空树
	else{
		T=new BiTNode;
		CreateBiTree(T->lchild);	//递归创建左子树
		T->data=ch;					//生成根结点
		CreateBiTree(T->rchild);	//递归创建右子树
	}
}

/*
T->data=ch;					//生成根结点
CreateBiTree(T->lchild);	//递归创建左子树
CreateBiTree(T->rchild);	//递归创建右子树

可以把根左右顺序换成，中序：左根右；后序：左右根，来输入
*/								//CreateBiTree

// 一、复制二叉树
void Copy(BiTree T, BiTree &NewT)
{
	if(T==NULL ){   //如果是空树，递归结束
		NewT=NULL;
		return;
	}
	else{
		NewT = new BiTNode;
		NewT->data = T->data;			//复制根结点
		Copy(T->lchild, NewT->lchild);  //递归复制左子树
		Copy(T->rchild, NewT->rchild);  //递归复制右子树
	}
}

// 二、计算二叉树的深度
int Depth(BiTree T){
	int m,n;
	if(T== NULL)
        return 0;  //如果是空树，深度为0，递归结束
	else {
            m=Depth(T->lchild);	  //递归计算左子树的深度记为m
            n=Depth(T->rchild);	  //递归计算右子树的深度记为n
            if(m>n)
                return(m+1);  //二叉树的深度为m 与n的较大者加1
            else
                return (n+1);
	}
}

// 三、计算二叉树的结点
int NodeCount(BiTree T){
     if(T==NULL) return 0;  			// 如果是空树，则结点个数为0，递归结束
     else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;
     //否则结点个数为左子树的结点个数+右子树的结点个数+1
}

// 中序遍历的递归算法
void InOrderTraverse(BiTree T){
	if(T){
		InOrderTraverse(T->lchild);
		cout << T->data;
		InOrderTraverse(T->rchild);
	}
}

int main()
{
	BiTree tree,new_tree;
	cout<<"二叉链表的序列(先序输入) 例如：ABD##E##CF###：\n";
	CreateBiTree(tree);
	Copy(tree,new_tree);
	cout<<"复制得到的新树的中序序列：";
	InOrderTraverse(new_tree);
	cout<<endl;
	
	cout<<"二叉树的深度为："<<Depth(tree)<<endl;
	cout<<"二叉树的结点数为："<<NodeCount(tree)<<endl;
}