二叉树的实现(遍历,复制,求深度,求结点)

实现效果:

测试用树:

#include<iostream>

using namespace std;

typedef struct BiTNode {//二叉树的二叉链表存储
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T);//先序创建二叉树
void PreOrderTraverse(BiTree T);//先序遍历 
void InOrderTraverse(BiTree T);//中序遍历
void PostOrderTraverse(BiTree T);//后序遍历
void Copy(BiTree T, BiTree &NewT);//复制二叉树 
int Depth(BiTree T);//计算二叉树的深度
int NodeCount(BiTree T);//统计二叉树的结点个数
int Countleaf(BiTree T);//统计二叉树的叶子结点个数
 
int main()
{
	BiTree T;
	BiTree A;

	cout << "先序创建二叉树,请输入二叉树各个结点:";
	CreateBiTree(T);
	cout << endl;

	cout << "先序遍历结果:";
	PreOrderTraverse(T);
	cout << endl;

	cout << "中序遍历结果:";
	InOrderTraverse(T);
	cout << endl;

	cout << "后序遍历结果:";
	PostOrderTraverse(T);
	cout << endl;

	cout << "复制二叉树T到A:";
	Copy(T, A);
	PreOrderTraverse(A);
	cout << endl;

	cout << "二叉树T的深度为：";
	cout << Depth(T) << endl;

	cout << "二叉树中结点的个数:";
	cout << NodeCount(T) << endl;

	cout<<"二叉树的叶子结点个数为："<<Countleaf(T) << endl << endl << endl; 
	system("Pause");
	return 0;
}
void CreateBiTree(BiTree &T)
{//先序创建二叉树
	char ch;
	cin >> ch;
	if (ch == '#')
	{
		T = NULL;
	}
	else
	{
		T = new BiTNode;
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}

void PreOrderTraverse(BiTree T)
{//先序遍历
	if (T == NULL)
	{
		return;
	}
	else
	{
		cout << T->data<<" ";
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}

void InOrderTraverse(BiTree T)
{//中序遍历
	if (T == NULL)
	{
		return;
	}
	else
	{
		InOrderTraverse(T->lchild);
		cout << T->data << " ";
		InOrderTraverse(T->rchild);
	}
}

void PostOrderTraverse(BiTree T)
{//后序遍历
	if (T == NULL)
	{
		return;
	}
	else
	{
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		cout << T->data << " ";
	}
}

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)
{//计算二叉树的深度
	if (T==NULL)
	{
		return 0;
	}
	else
	{
		int m = Depth(T->lchild);
		int n = Depth(T->rchild);
		if (m > n)
		{
			return m + 1;
		}
		else
		{
			return n + 1;	
		}
	}
}
int NodeCount(BiTree T)
{//统计二叉树结点个数
	if (T == NULL)
	{
		return 0;
	}
	else
	{
		return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
	}
}
int Countleaf(BiTree T)
{
    int hl,hr;
    if(T)
    {
   		hl=Countleaf(T->lchild);
   		hr=Countleaf(T->rchild);
	    if(hl==0 && hr==0)
	    {
			return (1);
		}
	    else
	    {
	    	return hl+hr;
		}    	
	}
	else
	{
	 return 0;		
	}
}