数据结构C++——二叉树的实现

男娘i 2024-04-01 11:30 65阅读 0赞

**目录**

二叉树的实现（出错版）

但是VS出现错误

全部代码：

运行结果：

补充计算叶子结点的个数方法后：

结果：

补充计算二叉树深度方法：

运行结果：

补充计算二叉树结点个数方法：（R+L+D=结点个数）

运行结果：

二叉树相关方法大实现：

运行结果：

--------------------

> ## 二叉树的实现（出错版） ##

/*
    *    二叉树的使用
    */
    
    /*
    *    二叉树的结点结构
    */
    struct BiNode {
    	char data;
    	BiNode* lchid,*rchid;
    };
    
    /*
    *  二叉链表的实现
    */
    
    class BiTree {
    private:
    	BiNode* Creat();
    	void Release(BiNode* bt);
    	void PreOrder(BiNode* bt);
    	void InOrder(BiNode* bt);
    	void PostOrder(BiNode* bt);
    	BiNode* root;//指向根结点的头指针
    public:
    	BiTree(){}
    	BiTree() {
    		root = Creat();
    	}
    	~BiTree() {
    		Release(root);
    	}
    
    	//前序遍历二叉树
    	void PreOrder() {
    		PreOrder(root);
    	}
    
    	//中序遍历二叉树
    	void InOrder() {
    		InOrder(root);
    	}
    
    	//后序遍历二叉树
    	void PostOrder() {
    		PostOrder(root);
    	}
    	//层序二叉树
    	void LevelOrder();
    };
    
    //层序遍历二叉树
    void BiTree::LevelOrder() {
    	BiNode* Q[100], * q = nullptr;
    	int font = -1, rear = -1;//队列初始化
    	if (root == nullptr)
    		return;
    	Q[++rear] = root;//根指针入队
    	while (font!=rear)
    	{
    		q = Q[++font];//出队
    		cout << q->data<<"\t";
    		if (q->lchid != nullptr)
    			Q[++rear] = q->lchid;
    		if (q->rchid != nullptr)
    			Q[++rear] = q->rchid;
    	}
    }
    
    //前序遍历
    void BiTree::PreOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		cout << bt->data;
    		cout << endl;          //访问根结点bt的数据域
    		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    	}
    }
    
    //中序遍历
    void BiTree::InOrder(BiNode*bt) {
    	if (bt == nullptr)
    		return;
    	else
    	{
    		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    		cout << bt->data;    //访问根结点bt的数据域
    		InOrder(bt->rchid); //中序递归遍历bt的右子树
    	}
    }
    
    //后序遍历
    void BiTree::PostOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else{
    		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    		cout << bt->data;     //访问根结点bt的数据域
    	}
    }
    
    //建立二叉树
    BiNode* BiTree::Creat() {
    	BiNode* bt;
    	char ch;
    	cin >> ch;        //输入结点的数据信息，假设为字符
    	if (ch == '#')   //建立一个空树
    		bt = nullptr;
    	else{
    		bt = new BiNode;
    		bt->data = ch;
    		bt->lchid = Creat();//递归建立左子树
    		bt->rchid = Creat();//递归建立右子树
    	}
    	return bt;
    }
    #include<iostream>
    using namespace std;
    int mian() {
    	BiTree T{};//定义对象变量 T
    	cout << "该二叉树的前序遍历序列为：";
    	T.PreOrder();
    	cout << endl;
    
    	cout << "该二叉树的中序遍历序列为：";
    	T.InOrder();
    	cout << endl;
    
    	cout << "该二叉树的后序遍历序列为：";
    	T.PostOrder();
    	cout << endl;
    
    	cout << "该二叉树的层序遍历序列为：";
    	T.LevelOrder();
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

> ### 但是VS出现错误 ###

> ## 全部代码： ##

> 更改后：

/*
    *    二叉树的使用
    */
    
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    /*
    *    二叉树的结点结构
    */
    struct BiNode {
    	char data;
    	BiNode* lchid,*rchid;
    };
    
    /*
    *  二叉链表的实现
    */
    class BiTree {
    private:
    	BiNode* Creat();
    	void Release(BiNode* bt);
    	void PreOrder(BiNode* bt);
    	void InOrder(BiNode* bt);
    	void PostOrder(BiNode* bt);
    	BiNode* root;//指向根结点的头指针
    public:
    	BiTree() {
    		root = Creat();
    	}
    	~BiTree() {
    		Release(root);
    	}
    
    	//前序遍历二叉树
    	void PreOrder() {
    		PreOrder(root);
    	}
    
    	//中序遍历二叉树
    	void InOrder() {
    		InOrder(root);
    	}
    
    	//后序遍历二叉树
    	void PostOrder() {
    		PostOrder(root);
    	}
    	//层序二叉树
    	void LevelOrder();
    };
    
    //建立二叉树
    BiNode* BiTree::Creat()
    {
    	BiNode* bt;
    	cout << "请依次输入二叉树序列：" << endl;
    	char ch;
    	cin >> ch;        //输入结点的数据信息，假设为字符
    	if (ch == '#')   //建立一个空树
    		bt = nullptr;
    	else {
    		bt = new BiNode;
    		bt->data = ch;
    		bt->lchid = Creat();//递归建立左子树
    		bt->rchid = Creat();//递归建立右子树
    	}
    	return bt;
    }
    
    //销毁二叉树
    void BiTree::Release(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		Release(bt->lchid);  //释放左子树
    		Release(bt->rchid); //释放右子树
    		delete bt;         //释放根结点
    	}
    }
    //层序遍历二叉树
    void BiTree::LevelOrder() {
    	BiNode* Q[100], * q = nullptr;
    	int font = -1, rear = -1;//队列初始化
    	if (root == nullptr)
    		return;
    	Q[++rear] = root;//根指针入队
    	while (font!=rear)
    	{
    		q = Q[++font];//出队
    		cout << q->data<<"\t";
    		if (q->lchid != nullptr)
    			Q[++rear] = q->lchid;
    		if (q->rchid != nullptr)
    			Q[++rear] = q->rchid;
    	}
    }
    
    //前序遍历
    void BiTree::PreOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		std::cout << bt->data; //访问根结点bt的数据域
    		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    	}
    }
    
    //中序遍历
    void BiTree::InOrder(BiNode*bt) {
    	if (bt == nullptr)
    		return;
    	else
    	{
    		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    		cout << bt->data;    //访问根结点bt的数据域
    		InOrder(bt->rchid); //中序递归遍历bt的右子树
    	}
    }
    
    //后序遍历
    void BiTree::PostOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else{
    		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    		cout << bt->data;     //访问根结点bt的数据域
    	}
    }
    
    int main() {
    	BiTree T{};//定义对象变量 T
    	std::cout << "该二叉树的前序遍历序列为：";
    	T.PreOrder();
    	std::cout << endl;
    
    	std::cout << "该二叉树的中序遍历序列为：";
    	T.InOrder();
    	std::cout << endl;
    
    	std::cout << "该二叉树的后序遍历序列为：";
    	T.PostOrder();
    	std::cout << endl;
    
    	std::cout << "该二叉树的层序遍历序列为：";
    	T.LevelOrder();
    	std::cout << endl;
    
    	system("pause");
    	return 0;
    }

> #### 运行结果： ####

![48ba6cd7f8ff4d6fbcadd1dda915f2b1.png][]

> ### 补充计算叶子结点的个数方法后： ###

/*
    *    二叉树的使用
    */
    
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    /*
    *    二叉树的结点结构
    */
    struct BiNode {
    	char data;
    	BiNode* lchid, * rchid;
    };
    
    /*
    *  二叉链表的实现
    */
    class BiTree {
    private:
    	BiNode* Creat();
    	void Release(BiNode* bt);
    	void PreOrder(BiNode* bt);
    	void InOrder(BiNode* bt);
    	void PostOrder(BiNode* bt);
    
    	int LeafCount(BiNode* bt);
    	BiNode* root;//指向根结点的头指针
    public:
    	BiTree() {
    		root = Creat();
    	}
    	~BiTree() {
    		Release(root);
    	}
    
    	//前序遍历二叉树
    	void PreOrder() {
    		PreOrder(root);
    	}
    
    	//中序遍历二叉树
    	void InOrder() {
    		InOrder(root);
    	}
    
    	//后序遍历二叉树
    	void PostOrder() {
    		PostOrder(root);
    	}
    	//层序二叉树
    	void LevelOrder();
    
    	//计算二叉树叶子结点个数
    	void LeafCount() {
    		cout<<LeafCount(root);
    
    	}
    };
    
    //建立二叉树
    BiNode* BiTree::Creat()
    {
    	BiNode* bt;
    	//cout << "请依次输入二叉树序列：" << endl;
    	char ch;
    	cin >> ch;        //输入结点的数据信息，假设为字符
    	if (ch == '#')   //建立一个空树
    		bt = nullptr;
    	else {
    		bt = new BiNode;//开辟空间
    		bt->data = ch;  //树根
    		bt->lchid = Creat();//递归建立左子树
    		bt->rchid = Creat();//递归建立右子树
    	}
    	return bt;
    }
    
    //销毁二叉树(后序消除法)
    void BiTree::Release(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		Release(bt->lchid);  //释放左子树
    		Release(bt->rchid); //释放右子树
    		delete bt;         //释放根结点
    	}
    }
    //层序遍历二叉树
    void BiTree::LevelOrder() {
    	BiNode* Q[100], * q = nullptr;
    	int font = -1, rear = -1;//队列初始化
    	if (root == nullptr)
    		return;
    	Q[++rear] = root;//根指针入队
    	while (font != rear)
    	{
    		q = Q[++font];//出队
    		cout << q->data << "\t";
    		if (q->lchid != nullptr)
    			Q[++rear] = q->lchid;
    		if (q->rchid != nullptr)
    			Q[++rear] = q->rchid;
    	}
    }
    
    //前序遍历
    void BiTree::PreOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		std::cout << bt->data; //访问根结点bt的数据域
    		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    	}
    }
    
    //中序遍历
    void BiTree::InOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else
    	{
    		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    		cout << bt->data;    //访问根结点bt的数据域
    		InOrder(bt->rchid); //中序递归遍历bt的右子树
    	}
    }
    
    //后序遍历
    void BiTree::PostOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    		cout << bt->data;     //访问根结点bt的数据域
    	}
    }
    
    //计算该二叉树的叶子结点个数
    int BiTree::LeafCount(BiNode* bt) {
    	if (bt == nullptr)
    		return 0;
    	if (bt->lchid == nullptr && bt->rchid == nullptr) {
    		return 1;
    	}
    	else
    	{
    		return LeafCount(bt->lchid) + LeafCount(bt->rchid);
    	}
    }
    
    int main() {
    
    	//试验：输入A B # D # # C # #
    	cout << "请依次输入二叉树序列：" << endl;
    	BiTree T{};//定义对象变量 T
    	std::cout << "该二叉树的前序遍历序列为：";
    	T.PreOrder();
    	std::cout << endl;
    	std::cout << "叶子结点的个数为：";
    	T.LeafCount();
    	cout << endl;
    	system("pause");
    	return 0;
    }

> #### 结果： ####

![56b5bb7b66224ae5909d66ce73943807.png][]

> ### 补充计算二叉树深度方法： ###

/*
    *    二叉树的使用
    */
    
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    /*
    *    二叉树的结点结构
    */
    struct BiNode {
    	char data;
    	BiNode* lchid, * rchid;
    };
    
    /*
    *  二叉链表的实现
    */
    class BiTree {
    private:
    	BiNode* Creat();
    	void Release(BiNode* bt);
    	void PreOrder(BiNode* bt);
    	void InOrder(BiNode* bt);
    	void PostOrder(BiNode* bt);
    	int Depth(BiNode* bt);
    	int LeafCount(BiNode* bt);
    	BiNode* root;//指向根结点的头指针
    public:
    	BiTree() {
    		root = Creat();
    	}
    	~BiTree() {
    		Release(root);
    	}
    
    	//前序遍历二叉树
    	void PreOrder() {
    		PreOrder(root);
    	}
    
    	//中序遍历二叉树
    	void InOrder() {
    		InOrder(root);
    	}
    
    	//后序遍历二叉树
    	void PostOrder() {
    		PostOrder(root);
    	}
    	//层序二叉树
    	void LevelOrder();
    
    	//计算树的深度
    	void Depth() {
    		cout << Depth(root);
    	}
    
    	//计算二叉树叶子结点个数
    	void LeafCount() {
    		cout<<LeafCount(root);
    
    	}
    };
    
    //建立二叉树
    BiNode* BiTree::Creat()
    {
    	BiNode* bt;
    	//cout << "请依次输入二叉树序列：" << endl;
    	char ch;
    	cin >> ch;        //输入结点的数据信息，假设为字符
    	if (ch == '#')   //建立一个空树
    		bt = nullptr;
    	else {
    		bt = new BiNode;//开辟空间
    		bt->data = ch;  //树根
    		bt->lchid = Creat();//递归建立左子树
    		bt->rchid = Creat();//递归建立右子树
    	}
    	return bt;
    }
    
    //销毁二叉树(后序消除法)
    void BiTree::Release(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		Release(bt->lchid);  //释放左子树
    		Release(bt->rchid); //释放右子树
    		delete bt;         //释放根结点
    	}
    }
    //层序遍历二叉树
    void BiTree::LevelOrder() {
    	BiNode* Q[100], * q = nullptr;
    	int font = -1, rear = -1;//队列初始化
    	if (root == nullptr)
    		return;
    	Q[++rear] = root;//根指针入队
    	while (font != rear)
    	{
    		q = Q[++font];//出队
    		cout << q->data << "\t";
    		if (q->lchid != nullptr)
    			Q[++rear] = q->lchid;
    		if (q->rchid != nullptr)
    			Q[++rear] = q->rchid;
    	}
    }
    
    //前序遍历
    void BiTree::PreOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		std::cout << bt->data; //访问根结点bt的数据域
    		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    	}
    }
    
    //中序遍历
    void BiTree::InOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else
    	{
    		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    		cout << bt->data;    //访问根结点bt的数据域
    		InOrder(bt->rchid); //中序递归遍历bt的右子树
    	}
    }
    
    //后序遍历
    void BiTree::PostOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    		cout << bt->data;     //访问根结点bt的数据域
    	}
    }
    
    //计算该二叉树的叶子结点个数
    int BiTree::LeafCount(BiNode* bt) {
    	if (bt == nullptr)
    		return 0;
    	if (bt->lchid == nullptr && bt->rchid == nullptr) {
    		return 1;
    	}
    	else
    	{
    		return LeafCount(bt->lchid) + LeafCount(bt->rchid);
    	}
    }
    
    //	//计算二叉树的深度
    int BiTree::Depth(BiNode *bt){
    	if (bt == nullptr)
    		return 0;
    	else {
    		int n, m;
    		m = Depth(bt->lchid);
    		n = Depth(bt->rchid);
    		if (m > n)
    			return m + 1;
    		else
    			return n + 1;
    	}
    }
    
    int main() {
    
    	//试验：输入A B # D # # C # #
    	cout << "请依次输入二叉树序列：" << endl;
    	BiTree T{};//定义对象变量 T
    	std::cout << "该二叉树的前序遍历序列为：";
    	T.PreOrder();
    	std::cout << endl;
    
    	std::cout << "叶子结点的个数为：";
    	T.LeafCount();
    	cout << endl;
    	
    	cout << "树的深度为：";
    	T.Depth();
    	cout << endl;
    	system("pause");
    	return 0;
    }

> #### 运行结果： ####

![c7e8a66301dc47d0a48aba47bb54b590.png][]

> ### 补充计算二叉树结点个数方法：（R+L+D=结点个数） ###

/*
    *    二叉树的使用
    */
    
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    /*
    *    二叉树的结点结构
    */
    struct BiNode {
    	char data;
    	BiNode* lchid, * rchid;
    };
    
    /*
    *  二叉链表的实现
    */
    class BiTree {
    private:
    	BiNode* Creat();				   //建树
    	void Release(BiNode* bt);         //销毁
    	void PreOrder(BiNode* bt);	     //前序
    	void InOrder(BiNode* bt);	    //中序
    	void PostOrder(BiNode* bt);    //后序
    	int NodeCount(BiNode* bt);	  //计算二叉树结点个数
    	int Depth(BiNode* bt);		 //计算二叉树深度
    	int LeafCount(BiNode* bt);	//计算二叉树叶子结点个数
    	BiNode* root;			   //指向根结点的头指针
    public:
    	BiTree() {
    		root = Creat();
    	}
    	~BiTree() {
    		Release(root);
    	}
    
    	//前序遍历二叉树
    	void PreOrder() {
    		PreOrder(root);
    	}
    
    	//中序遍历二叉树
    	void InOrder() {
    		InOrder(root);
    	}
    
    	//后序遍历二叉树
    	void PostOrder() {
    		PostOrder(root);
    	}
    	//层序二叉树
    	void LevelOrder();
    
    	//计算二叉树结点个数
    	void NodeCount() {
    		cout << NodeCount(root);
    	}
    
    	//计算树的深度
    	void Depth() {
    		cout << Depth(root);
    	}
    
    	//计算二叉树叶子结点个数
    	void LeafCount() {
    		cout<<LeafCount(root);
    
    	}
    };
    
    //建立二叉树
    BiNode* BiTree::Creat()
    {
    	BiNode* bt;
    	//cout << "请依次输入二叉树序列：" << endl;
    	char ch;
    	cin >> ch;        //输入结点的数据信息，假设为字符
    	if (ch == '#')   //建立一个空树
    		bt = nullptr;
    	else {
    		bt = new BiNode;//开辟空间
    		bt->data = ch;  //树根
    		bt->lchid = Creat();//递归建立左子树
    		bt->rchid = Creat();//递归建立右子树
    	}
    	return bt;
    }
    
    //销毁二叉树(后序消除法)
    void BiTree::Release(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		Release(bt->lchid);  //释放左子树
    		Release(bt->rchid); //释放右子树
    		delete bt;         //释放根结点
    	}
    }
    //层序遍历二叉树
    void BiTree::LevelOrder() {
    	BiNode* Q[100], * q = nullptr;
    	int font = -1, rear = -1;//队列初始化
    	if (root == nullptr)
    		return;
    	Q[++rear] = root;//根指针入队
    	while (font != rear)
    	{
    		q = Q[++font];//出队
    		cout << q->data << "\t";
    		if (q->lchid != nullptr)
    			Q[++rear] = q->lchid;
    		if (q->rchid != nullptr)
    			Q[++rear] = q->rchid;
    	}
    }
    
    //前序遍历
    void BiTree::PreOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		std::cout << bt->data; //访问根结点bt的数据域
    		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    	}
    }
    
    //中序遍历
    void BiTree::InOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else
    	{
    		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    		cout << bt->data;    //访问根结点bt的数据域
    		InOrder(bt->rchid); //中序递归遍历bt的右子树
    	}
    }
    
    //后序遍历
    void BiTree::PostOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    		cout << bt->data;     //访问根结点bt的数据域
    	}
    }
    
    //计算二叉树结点个数
    int BiTree::NodeCount(BiNode* bt) {
    	if (bt == nullptr)
    		return 0;
    	else {
    		return NodeCount(bt->lchid) + NodeCount(bt->rchid)+1;
    	}
    }
    
    //计算该二叉树的叶子结点个数
    int BiTree::LeafCount(BiNode* bt) {
    	if (bt == nullptr)
    		return 0;
    	if (bt->lchid == nullptr && bt->rchid == nullptr) {
    		return 1;
    	}
    	else
    	{
    		return LeafCount(bt->lchid) + LeafCount(bt->rchid);
    	}
    }
    
    //	//计算二叉树的深度
    int BiTree::Depth(BiNode *bt){
    	if (bt == nullptr)
    		return 0;
    	else {
    		int n, m;
    		m = Depth(bt->lchid);
    		n = Depth(bt->rchid);
    		if (m > n)
    			return m + 1;
    		else
    			return n + 1;
    	}
    }
    
    int main() {
    
    	//试验：输入A B # D # # C # #
    	cout << "请依次输入二叉树序列：" << endl;
    	BiTree T{};//定义对象变量 T
    	std::cout << "该二叉树的前序遍历序列为：";
    	T.PreOrder();
    	std::cout << endl;
    
    	//二叉树结点个数
    	cout << "二叉树结点个数为：";
    	T.NodeCount();
    	cout << endl;
    	
    	//叶子结点的个数
    	std::cout << "叶子结点的个数为：";
    	T.LeafCount();
    	cout << endl;
    	
    	//树的深度
    	cout << "树的深度为：";
    	T.Depth();
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

> #### 运行结果： ####

![4a9888ee67b84a9a9025eba033968f78.png][]

> ## 二叉树相关方法大实现： ##

*  计算二叉树深度方法
 *  计算二叉树结点个数方法：（R+L+D=结点个数）
 *  计算叶子结点的个数方法

/*
    *    二叉树的使用
    */
    
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    /*
    *    二叉树的结点结构
    */
    struct BiNode {
    	char data;
    	BiNode* lchid, * rchid;
    };
    
    /*
    *  二叉链表的实现
    */
    class BiTree {
    private:
    	BiNode* Creat();				   //建树
    	void Release(BiNode* bt);         //销毁
    	void PreOrder(BiNode* bt);	     //前序
    	void InOrder(BiNode* bt);	    //中序
    	void PostOrder(BiNode* bt);    //后序
    	int NodeCount(BiNode* bt);	  //计算二叉树结点个数
    	int Depth(BiNode* bt);		 //计算二叉树深度
    	int LeafCount(BiNode* bt);	//计算二叉树叶子结点个数
    	BiNode* root;			   //指向根结点的头指针
    public:
    	BiTree() {
    		root = Creat();
    	}
    	~BiTree() {
    		Release(root);
    	}
    
    	//前序遍历二叉树
    	void PreOrder() {
    		PreOrder(root);
    	}
    
    	//中序遍历二叉树
    	void InOrder() {
    		InOrder(root);
    	}
    
    	//后序遍历二叉树
    	void PostOrder() {
    		PostOrder(root);
    	}
    	//层序二叉树
    	void LevelOrder();
    
    	//计算二叉树结点个数
    	void NodeCount() {
    		cout << NodeCount(root);
    	}
    
    	//计算树的深度
    	void Depth() {
    		cout << Depth(root);
    	}
    
    	//计算二叉树叶子结点个数
    	void LeafCount() {
    		cout<<LeafCount(root);
    
    	}
    };
    
    //建立二叉树
    BiNode* BiTree::Creat()
    {
    	BiNode* bt;
    	//cout << "请依次输入二叉树序列：" << endl;
    	char ch;
    	cin >> ch;        //输入结点的数据信息，假设为字符
    	if (ch == '#')   //建立一个空树
    		bt = nullptr;
    	else {
    		bt = new BiNode;//开辟空间
    		bt->data = ch;  //树根
    		bt->lchid = Creat();//递归建立左子树
    		bt->rchid = Creat();//递归建立右子树
    	}
    	return bt;
    }
    
    //销毁二叉树(后序消除法)
    void BiTree::Release(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		Release(bt->lchid);  //释放左子树
    		Release(bt->rchid); //释放右子树
    		delete bt;         //释放根结点
    	}
    }
    //层序遍历二叉树
    void BiTree::LevelOrder() {
    	BiNode* Q[100], * q = nullptr;
    	int font = -1, rear = -1;//队列初始化
    	if (root == nullptr)
    		return;
    	Q[++rear] = root;//根指针入队
    	while (font != rear)
    	{
    		q = Q[++font];//出队
    		cout << q->data << "\t";
    		if (q->lchid != nullptr)
    			Q[++rear] = q->lchid;
    		if (q->rchid != nullptr)
    			Q[++rear] = q->rchid;
    	}
    }
    
    //前序遍历
    void BiTree::PreOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		std::cout << bt->data; //访问根结点bt的数据域
    		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    	}
    }
    
    //中序遍历
    void BiTree::InOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else
    	{
    		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    		cout << bt->data;    //访问根结点bt的数据域
    		InOrder(bt->rchid); //中序递归遍历bt的右子树
    	}
    }
    
    //后序遍历
    void BiTree::PostOrder(BiNode* bt) {
    	if (bt == nullptr)
    		return;
    	else {
    		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    		cout << bt->data;     //访问根结点bt的数据域
    	}
    }
    
    //计算二叉树结点个数
    int BiTree::NodeCount(BiNode* bt) {
    	if (bt == nullptr)
    		return 0;
    	else {
    		return NodeCount(bt->lchid) + NodeCount(bt->rchid)+1;
    	}
    }
    
    //计算该二叉树的叶子结点个数
    int BiTree::LeafCount(BiNode* bt) {
    	if (bt == nullptr)
    		return 0;
    	if (bt->lchid == nullptr && bt->rchid == nullptr) {
    		return 1;
    	}
    	else
    	{
    		return LeafCount(bt->lchid) + LeafCount(bt->rchid);
    	}
    }
    
    //	//计算二叉树的深度
    int BiTree::Depth(BiNode *bt){
    	if (bt == nullptr)
    		return 0;
    	else {
    		int n, m;
    		m = Depth(bt->lchid);
    		n = Depth(bt->rchid);
    		if (m > n)
    			return m + 1;
    		else
    			return n + 1;
    	}
    }
    
    int main() {
    
    	//试验：输入A B # D # # C # #
    	cout << "请依次输入二叉树序列：" << endl;
    	BiTree T{};//定义对象变量 T
    	std::cout << "该二叉树的前序遍历序列为：";
    	T.PreOrder();
    	std::cout << endl;
    
    	//二叉树结点个数
    	cout << "二叉树结点个数为：";
    	T.NodeCount();
    	cout << endl;
    	
    	//叶子结点的个数
    	std::cout << "叶子结点的个数为：";
    	T.LeafCount();
    	cout << endl;
    	
    	//树的深度
    	cout << "树的深度为：";
    	T.Depth();
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

> ### 运行结果： ###

![4a9888ee67b84a9a9025eba033968f78.png][]

[48ba6cd7f8ff4d6fbcadd1dda915f2b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/71603ce543d9415baf189d6bc0bce0f4.png
[56b5bb7b66224ae5909d66ce73943807.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/34ff859e545c4477a0bdcd7dcd29ea66.png
[c7e8a66301dc47d0a48aba47bb54b590.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3036e08ebe9e44219c2bdfdcda4057b0.png
[4a9888ee67b84a9a9025eba033968f78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/49c34d768c234b2bacb4cea41b13cedc.png