C++实现二叉树

1.目的：

        1.1 实现二叉树的创建

        1.2 实现二叉树的访问 --- 先中后序访问、层序访问

        1.3 计算树的深度、节点数、复制树

2.案例测试

        2.1 首先创建出一棵二叉树

根据提示依次将要创建的二叉树的 先序遍历结点 输入 ，详细地，如有这样一颗二叉树(#表示空结点)：

则创建二叉树时应输入其先序遍历序列是 ABDECFG ,更具体地，按如下输入：

接下来，你将看到，输出先序、层序遍历结果等内容，如下：（注：中序后序，操作类似于前序遍历，没有实现）

3.完整代码如下：

/*
	这里要实现的是：
		1.二叉树的创建
		2.树的访问---先中后序访问、再加一个层序访问
	以及一些应用
		1.得到树的深度
		2.得到树的节点数
		3.复制一棵树
	这些都需要用到递归的思想
*/
 
#include<iostream>
using namespace std;
#include<queue>
 
 
// 定义二叉树的数据结构
typedef struct treeNode {
	string data;
	struct treeNode* lChild, * rChild;
}treeNode, * treeLink;
 
// 根据用户输入，创建一棵二叉树  // 递归的方式创建  // 按照先根遍历的访问顺序，输入数据
void createTree(treeLink& t)
{
	string data;
 
	cout << "是否设置为空节点？y -- n" << endl;
	string userInput;
	cin >> userInput;
	if (userInput == "y" || userInput == "Y")
	{
		t = NULL;
		return;
	}
	else if (userInput == "n" || userInput == "N")
	{
		
		cout << "请输入 内容：" << endl;
		cin >> data;
	}
 
	// 核心代码：
	t = new treeNode;
	t->data = data;
	createTree(t->lChild);
	createTree(t->rChild);
 
}
 
// 设置访问规则 
void visit(const treeLink& t)
{
	// 这里做打印输出
	cout << t->data << endl;
 
}
// 访问 -- 根左右 先序顺序
void preOrder(const treeLink& t)
{
	if (t == NULL)
		return;
	visit(t);
	preOrder(t->lChild);
	preOrder(t->rChild);
}
// 访问 -- 左根右 中序顺序
void midOrder(const treeLink& t)
{
	if (t == NULL)
		return;
	preOrder(t->lChild);
	visit(t);
	preOrder(t->rChild);
}
// 访问 -- 左右根 后序顺序
void postOrder(const treeLink& t)
{
	if (t == NULL)
		return;
	preOrder(t->lChild);
	visit(t);
	preOrder(t->rChild);
}
// 访问 -- 树的层序遍历
void floorOrder(const treeLink& t)
{
	queue<treeLink> qT;
 
	if (t == NULL)
		return;
	visit(t);
	if (t->lChild != NULL)
		qT.push(t->lChild);
	if (t->rChild != NULL)
		qT.push(t->rChild);
 
 
	while (!qT.empty())
	{
		treeLink frontEle = qT.front();
		visit(frontEle);
		if (frontEle->lChild != NULL)
			qT.push(frontEle->lChild);
		if (frontEle->rChild != NULL)
			qT.push(frontEle->rChild);
		qT.pop();
	}
 
}
 
 
// 树的深度的计算  // 树的深度等于 左子树、右子树 深度较大者  再加一 ；； 对于左右子树，亦是如此
// 递归的关键是---找出退出循环的条件
int treeDepth(const treeLink& t)
{
	if (t->lChild == NULL && t->rChild == NULL)
	{
		return 1;
	}
	
	// 左右子树 深度
	int lDepth = treeDepth(t->lChild);
	int rDepth = treeDepth(t->rChild);
 
	return lDepth > rDepth ? lDepth + 1 : rDepth + 1;
 
}
 
// 树的结点个数的计算  //   树的节点个数 等于 左子树节点个数 + 右子树 节点个数 再加一 ；；对于左右子树亦是如此
int totalNodes(const treeLink& t)
{
	if (t == NULL)
	{
		return 0;
	}
 
	// 左右子树 深度
	int lNodes = totalNodes(t->lChild);
	int rNodes = totalNodes(t->rChild);
 
	return lNodes + rNodes + 1;
}
 
// 复制一棵树
void copyTree(const treeLink& t, treeLink& newTNode)
{
	if (t == NULL)  // 节点为空时，返回
	{
		newTNode = NULL;
		return;
	}
	newTNode = new treeNode;
	newTNode->data = t->data;
 
	// 对于左右子节点 亦是如此
	copyTree(t->lChild, newTNode->lChild);
	copyTree(t->rChild, newTNode->rChild);
 
}
 
// 测试案例
void test()
{
	treeLink t;
	createTree(t);
 
	cout << "先序遍历结果是：" << endl;
	preOrder(t);
	cout << "--------------------------------" << endl;
	cout << "层序遍历结果是" << endl;
	floorOrder(t);
	cout << "--------------------------------" << endl;
	cout << "树的深度是：" << treeDepth(t) << endl;
	cout << "树的节点总个数是：" << totalNodes(t) << endl;
 
	cout << "------------- copy -------------------" << endl;
 
	treeLink treeCopied;
	copyTree(t, treeCopied);
	preOrder(treeCopied);
	cout << "复制出来的树的深度是：" << treeDepth(treeCopied) << endl;
	cout << "复制出来的树的节点总个数是：" << totalNodes(treeCopied) << endl;
 
 
 
}
 
int main()
{
	test();
 
	system("pause");
	return 0;
}