使用C++创建二叉树和其基本操作

目录

1.创建二叉树节点

2.使用前序遍历创建二叉树

3.遍历二叉树 

3.1 前序遍历二叉树

3.2 中序遍历二叉树

3.3 后序遍历二叉树

4. 二叉树是否为空

5. 求二叉树的节点数

6.求二叉树的深度

完整代码

运行测试用例及截图

---

1.创建二叉树节点

typedef struct TreeNode {
	char data;//数据域
	TreeNode* Lchild;//左孩子
	TreeNode* Rchild;//右孩子
}*Tree, TreeNode;

2.使用前序遍历创建二叉树

void CreateTree(Tree& T) {
	char x;
	cin >> x;
	if (x =='*') {
		T = NULL; return;
	}
	else {
		T = new TreeNode;
		T->data = x;
		CreateTree(T->Lchild);
		CreateTree(T->Rchild);
	}
}

3.遍历二叉树 

3.1 前序遍历二叉树

void Pre_Traversal(const Tree& T) {
	if (T) {
		cout << T->data<<" ";
		Pre_Traversal(T->Lchild);
		Pre_Traversal(T->Rchild);
	}
}

3.2 中序遍历二叉树

void Ino_Traversal(const Tree& T) {
	if (T) {
		Ino_Traversal(T->Lchild);
		cout << T->data<<" ";
		Ino_Traversal(T->Rchild);
	}
}

3.3 后序遍历二叉树

void Pos_Traversal(const Tree& T) {
	if (T) {
		Pos_Traversal(T->Lchild);
		Pos_Traversal(T->Rchild);
		cout << T->data << " ";
		
	}
}

4. 二叉树是否为空

bool TreeEmpty(const Tree& T) {
	if (T == NULL)
	{
		cout << "该二叉树为空！"<<endl; 
		return true;
	}
	else
	{
		cout << "该二叉树为不为空！"<<endl;
		return false;
	}
}

5. 求二叉树的节点数

int TreeNodeCount(const Tree& T) {
	if (T == NULL)
		return 0;
	else if (T->Lchild == NULL && T->Rchild == NULL)
		return 1;
	else
		return TreeNodeCount(T->Lchild) + TreeNodeCount(T->Rchild)+1;
 
}

6.求二叉树的深度

int TreeDepth(const Tree& T) {
	if (T == NULL) return 0;
	else {
		int i = TreeDepth(T->Lchild);
		int j = TreeDepth(T->Rchild);
		return i > j ? i + 1 : j + 1;
	}
 
}

完整代码

#include<iostream>
 
 
using namespace std;
 
typedef struct TreeNode {
	char data;//数据域
	TreeNode* Lchild;//左孩子
	TreeNode* Rchild;//右孩子
}*Tree, TreeNode;
 
//前序创建二叉树
void CreateTree(Tree& T) {
	char x;
	cin >> x;
	if (x =='*') {
		T = NULL; return;
	}
	else {
		T = new TreeNode;
		T->data = x;
		CreateTree(T->Lchild);
		CreateTree(T->Rchild);
	}
}
//先序遍历
void Pre_Traversal(const Tree& T) {
	if (T) {
		cout << T->data<<" ";
		Pre_Traversal(T->Lchild);
		Pre_Traversal(T->Rchild);
	}
}
//中序遍历
void Ino_Traversal(const Tree& T) {
	if (T) {
		Ino_Traversal(T->Lchild);
		cout << T->data<<" ";
		Ino_Traversal(T->Rchild);
	}
}
//后序遍历
void Pos_Traversal(const Tree& T) {
	if (T) {
		Pos_Traversal(T->Lchild);
		Pos_Traversal(T->Rchild);
		cout << T->data << " ";
		
	}
}
//二叉树是否为空
bool TreeEmpty(const Tree& T) {
	if (T == NULL)
	{
		cout << "该二叉树为空！"<<endl; 
		return true;
	}
	else
	{
		cout << "该二叉树为不为空！"<<endl;
		return false;
	}
}
//求二叉树的节点数
int TreeNodeCount(const Tree& T) {
	if (T == NULL)
		return 0;
	else if (T->Lchild == NULL && T->Rchild == NULL)
		return 1;
	else
		return TreeNodeCount(T->Lchild) + TreeNodeCount(T->Rchild)+1;
 
}
//求二叉树的深度
int TreeDepth(const Tree& T) {
	if (T == NULL) return 0;
	else {
		int i = TreeDepth(T->Lchild);
		int j = TreeDepth(T->Rchild);
		return i > j ? i + 1 : j + 1;
	}
 
}
 
int main(){
	Tree T;
	cout << "请按先序遍历的顺序创建二叉树，若其节点的左孩子或右孩子不存在则使用*代替！如：（ABD**E**CF**G**）" << endl;
	CreateTree(T);
	TreeEmpty(T);
	cout << "先序遍历的结果为：";
	Pre_Traversal(T) ;
	cout<< endl;
	cout << "中序遍历的结果为：";
	Ino_Traversal(T);
	cout << endl;
	cout << "后序遍历的结果为：";
	Pos_Traversal(T);
	cout << endl;
	cout << "该树的深度为："<< TreeDepth(T)<< endl;
	cout << "该树的节点数为：" << TreeNodeCount(T) << endl;
	system("pause");
}
 

运行测试用例及截图

下图为测试用例： (ABD**E**CF**G**)

                        ​​​​​​​

前序遍历：A B D E C F G

中序遍历：D B E A F C G

后序遍历：D E B F G C A

总节点数 ：7

树的深度：3 

运行截图如下：