C++二叉树（青岛大学王卓视频）

文章目录

• 前言
• 一、建立节点类和二叉树类
• 二、 成员函数的实现
• • isEmpty:判断二叉树是否为空
  • preOrder:前序遍历
  • inOrder:中序遍历
  • postOrder:后序遍历
  • nodeNum1:计算节点数
  • leavesNum:计算叶子节点数
  • depth1:计算二叉树的深度
  • construct1:根据输入构建二叉树，"#"表示空节点
  • copyTree:二叉树的复制
  • destory:二叉树的销毁
  • 构造函数与析构函数
  • =运算符重载
  • 递归函数的公有化:调用对应的私有函数，并传入根节点
  • noRecurTraver:中序非递归遍历,用STL的stack实现
  • layerTraverse:层次遍历,用STL的queue实现
• 三、全部代码
• • biTree.h
  • test.cpp
• 四、测试结果

---

前言

本人还在学习阶段，如果有什么错误，欢迎在评论区留言。

本文是我在看完青岛大学王卓老师视频之后，对二叉树部分的算法用C++进行实现，函数功能和视频中的是一样的，不同的是采用的是C++面向对象的编程思路，用到了模板，存储结构用的是链式存储。另外本文对基本原理不再赘述，只对代码中一些技巧进行注释。

---

一、建立节点类和二叉树类

节点类：成员变量为数据，左孩子和右孩子。

template
struct node
{
	T data;
	node* lChild;
	node* rChild;
};

二叉树类：成员变量为根节点，将有递归操作的函数分成了两个函数，分别放在私有区和公共区，私有区的函数有输入，因为这些递归函数的实现必须要有输入，但是输入的又是往往又是节点类型的指针，调用的时候都是把二叉树的根节点作为输入参数，但是成员变量一般是私有的，外部无法调用，这样一来便又要重新写一个成员函数来获取根节点，这样在使用的时候就会变得很麻烦。而我们在外部调用函数的时候往往希望越简单越好甚至能够做到无输入参数更好，所以就在公有区又写了一个函数作为外部使用。

template
class biTree
{
public:
	bool isEmpty()const;
	void preTraverse()const;
	void inTraverse()const;
	void postTraverse()const;
	int nodeNum()const;
	int leavesNum()const;
	int depth()const;
	void destroyTree();
	biTree();
	biTree(const biTree& otherTree);
	~biTree();
	const biTree& operator=(const biTree& otherTree);
	void construct();
	void noRecurTraver();
	void layerTraverse();
protected:
	node* root;
private://私有区函数，用于递归的实现
	void preOrder(node* p)const;
	void inOrder(node* p)const;
	void postOrder(node* p)const;
	int nodeNum1(node* p)const;
	int leavesNum1(node* p)const;
	int depth1(node* p)const;
	void copyTree(node* & root, node* otherRoot);
	void destroy(node* &root);
	void construct1(node*& p);
};

---

二、 成员函数的实现 isEmpty:判断二叉树是否为空

template
bool biTree::isEmpty()const
{
	return root==nullptr;
}

preOrder:前序遍历

template
void biTree::preOrder(node* p)const
{
	if (p)
	{
		cout << p->data << " ";
		preOrder(p->lChild);
		preOrder(p->rChild);
	}
}

inOrder:中序遍历

template
void biTree::inOrder(node* p)const
{
	if (p)
	{
		inOrder(p->lChild);
		cout << p->data << " ";
		inOrder(p->rChild);
	}
}

postOrder:后序遍历

template
void biTree::postOrder(node* p)const
{
	if (p)
	{
		postOrder(p->lChild);
		postOrder(p->rChild);
		cout << p->data << " ";
	}
}

nodeNum1:计算节点数

template
int biTree::nodeNum1(node* p)const
{
	if (p == nullptr)return 0;
	else
	{
		return nodeNum1(p->lChild) + nodeNum1(p->rChild) + 1;
	}
}

template
int biTree::leavesNum1(node* p)const
{
	if (p == nullptr)return 0;
	if (p->lChild == nullptr && p->rChild == nullptr)return 1;
	else
	{
		return leavesNum1(p->lChild) + leavesNum1(p->rChild);
	}
}

leavesNum:计算叶子节点数

template
int biTree::leavesNum1(node* p)const
{
	if (p == nullptr)return 0;
	if (p->lChild == nullptr && p->rChild == nullptr)return 1;
	else
	{
		return leavesNum1(p->lChild) + leavesNum1(p->rChild);
	}
}

depth1:计算二叉树的深度

template
int biTree::depth1(node* p)const
{
	if (p == nullptr)return 0;
	else
	{
		int m, n;
		m = depth1(p->lChild);
		n = depth1(p->rChild);
		if (m > n)
			return m + 1;
		else
			return n + 1;
	}
}

construct1:根据输入构建二叉树，"#"表示空节点

template
void biTree::construct1(node*& p)//构建二叉树，带参才能实现递归，但是如果直接给外面使用传参就太麻烦
{
	T temp;
	cin >> temp;
	if (temp == "#")
		p = nullptr;
	else
	{
		p = new node;
		p->data = temp;
		construct1(p->lChild);
		construct1(p->rChild);
	}
}

copyTree:二叉树的复制

template
void biTree::copyTree(node*& root, node* otherRoot) //注意第一个参数的引用是必须要的，复制完之后该树的根节点不会改变
{
	if (otherRoot == nullptr)
		root = nullptr;
	else
	{
		root = new node;
		root->data = otherRoot->data;
		copyTree(root->lChild, otherRoot->lChild);
		copyTree(root->rChild, otherRoot->rChild);
	}
}

destory:二叉树的销毁

template
void biTree::destroy(node*& root)  //注意这里必须要对root进行引用
{
	if (root)
	{
		destroy(root->lChild);//注意这里必须先调用递归再去删除节点，否则删掉了节点信息就没有了
		destroy(root->rChild);
		delete root;
		root = nullptr;

	}
}

构造函数与析构函数

template
biTree::biTree()  //默认构造函数
{
	root = nullptr;
}

template
biTree::~biTree() //析构函数
{
	destroy(root);
}

template
biTree::biTree(const biTree& otherTree)  //拷贝构造函数
{
	copyTree(root, otherTree.root);
}

=运算符重载

template
const biTree& biTree::operator=(const biTree& otherTree)
{
	if (this != &otherTree)
	{
		if (root)
		{
			destroy(root);
		}
		copyTree(root, otherTree.root);
	}
	return *this;
}

递归函数的公有化:调用对应的私有函数，并传入根节点

template
void biTree::preTraverse()const
{
	preOrder(root);
	cout << endl;
}

template
void biTree::inTraverse()const
{
	inOrder(root);
	cout << endl;
}

template
void biTree::postTraverse()const
{
	postOrder(root);
	cout << endl;
}

template
int biTree::nodeNum()const
{
	return nodeNum1(root);
}

template
int biTree::leavesNum()const
{
	return leavesNum1(root);
}

template
int biTree::depth()const
{
	return depth1(root);
}

template
void biTree::destroyTree()
{
	destroy(root);
}

template
void biTree::construct()//实际上外部调用的时候希望不带参
{
	construct1(root);
}

noRecurTraver:中序非递归遍历,用STL的stack实现

template
void biTree::noRecurTraver()//非递归中序遍历
{
	stack*> stack1;
	node* p = root;
	while (p || !stack1.empty())
	{
		if (p)
		{
			stack1.push(p);
			p = p->lChild;
		}
		else
		{
			p = stack1.top();
			stack1.pop();
			cout << p->data<< " ";
			p = p->rChild;
		}
	}
	cout << endl;
}

layerTraverse:层次遍历,用STL的queue实现

template
void biTree::layerTraverse()//层次遍历
{
	queue*> que1;
	node* p = root;
	if (p == nullptr);
	else
	{
		que1.push(p);
		while (p || !que1.empty())
		{
			cout << p->data << " ";
			if (p->lChild)que1.push(p->lChild);
			if (p->rChild)que1.push(p->rChild);
			que1.pop();
			if (que1.empty())p = nullptr;
			//注意这里必须要判断队列是否已经空了，空了的话就要把p置为空，否则直接进入到下一句就会报错，因为这个时候队列已经空了
			else
				p = que1.front();
		}
		cout << endl;
	}
}

---

三、全部代码 biTree.h

#pragma once
#include
#include
#include
#include
#include
using namespace std;
template
struct node
{
	T data;
	node* lChild;
	node* rChild;
};

template
class biTree
{
public:
	bool isEmpty()const;
	void preTraverse()const;
	void inTraverse()const;
	void postTraverse()const;
	int nodeNum()const;
	int leavesNum()const;
	int depth()const;
	void destroyTree();
	biTree();
	biTree(const biTree& otherTree);
	~biTree();
	const biTree& operator=(const biTree& otherTree);
	void construct();
	void noRecurTraver();
	void layerTraverse();
protected:
	node* root;
private:
	void preOrder(node* p)const;
	void inOrder(node* p)const;
	void postOrder(node* p)const;
	int nodeNum1(node* p)const;
	int leavesNum1(node* p)const;
	int depth1(node* p)const;
	void copyTree(node* & root, node* otherRoot);
	void destroy(node* &root);
	void construct1(node*& p);
};

template
bool biTree::isEmpty()const
{
	return root==nullptr;
}


template
void biTree::preOrder(node* p)const
{
	if (p)
	{
		cout << p->data << " ";
		preOrder(p->lChild);
		preOrder(p->rChild);
	}
}

template
void biTree::inOrder(node* p)const
{
	if (p)
	{
		inOrder(p->lChild);
		cout << p->data << " ";
		inOrder(p->rChild);
	}
}

template
void biTree::postOrder(node* p)const
{
	if (p)
	{
		postOrder(p->lChild);
		postOrder(p->rChild);
		cout << p->data << " ";
	}
}

template
int biTree::nodeNum1(node* p)const
{
	if (p == nullptr)return 0;
	else
	{
		return nodeNum1(p->lChild) + nodeNum1(p->rChild) + 1;
	}
}

template
int biTree::leavesNum1(node* p)const
{
	if (p == nullptr)return 0;
	if (p->lChild == nullptr && p->rChild == nullptr)return 1;
	else
	{
		return leavesNum1(p->lChild) + leavesNum1(p->rChild);
	}
}

template
int biTree::depth1(node* p)const
{
	if (p == nullptr)return 0;
	else
	{
		int m, n;
		m = depth1(p->lChild);
		n = depth1(p->rChild);
		if (m > n)
			return m + 1;
		else
			return n + 1;
	}
}

template
void biTree::construct1(node*& p)//构建二叉树，带参才能实现递归，但是如果直接给外面使用传参就太麻烦
{
	T temp;
	cin >> temp;
	if (temp == "#")
		p = nullptr;
	else
	{
		p = new node;
		p->data = temp;
		construct1(p->lChild);
		construct1(p->rChild);
	}
}

template
void biTree::copyTree(node*& root, node* otherRoot) //注意第一个参数的引用是必须要的，复制完之后该树的根节点不会改变
{
	if (otherRoot == nullptr)
		root = nullptr;
	else
	{
		root = new node;
		root->data = otherRoot->data;
		copyTree(root->lChild, otherRoot->lChild);
		copyTree(root->rChild, otherRoot->rChild);
	}
}

template
void biTree::destroy(node*& root)  //注意这里必须要对root进行引用
{
	if (root)
	{
		destroy(root->lChild);//注意这里必须先调用递归再去删除节点，否则删掉了节点信息就没有了
		destroy(root->rChild);
		delete root;
		root = nullptr;

	}
}


template
biTree::biTree()
{
	root = nullptr;
}

template
biTree::~biTree()
{
	destroy(root);
}

template
biTree::biTree(const biTree& otherTree)
{
	copyTree(root, otherTree.root);
}

template
const biTree& biTree::operator=(const biTree& otherTree)
{
	if (this != &otherTree)
	{
		if (root)
		{
			destroy(root);
		}
		copyTree(root, otherTree.root);
	}
	return *this;
}

template
void biTree::preTraverse()const
{
	preOrder(root);
	cout << endl;
}

template
void biTree::inTraverse()const
{
	inOrder(root);
	cout << endl;
}

template
void biTree::postTraverse()const
{
	postOrder(root);
	cout << endl;
}

template
int biTree::nodeNum()const
{
	return nodeNum1(root);
}

template
int biTree::leavesNum()const
{
	return leavesNum1(root);
}

template
int biTree::depth()const
{
	return depth1(root);
}

template
void biTree::destroyTree()
{
	destroy(root);
}

template
void biTree::construct()//实际上外部调用的时候希望不带参
{
	construct1(root);
}

template
void biTree::noRecurTraver()//非递归中序遍历
{
	stack*> stack1;
	node* p = root;
	while (p || !stack1.empty())
	{
		if (p)
		{
			stack1.push(p);
			p = p->lChild;
		}
		else
		{
			p = stack1.top();
			stack1.pop();
			cout << p->data<< " ";
			p = p->rChild;
		}
	}
	cout << endl;
}

template
void biTree::layerTraverse()//层次遍历
{
	queue*> que1;
	node* p = root;
	if (p == nullptr);
	else
	{
		que1.push(p);
		while (p || !que1.empty())
		{
			cout << p->data << " ";
			if (p->lChild)que1.push(p->lChild);
			if (p->rChild)que1.push(p->rChild);
			que1.pop();
			if (que1.empty())p = nullptr;
			//注意这里必须要判断队列是否已经空了，空了的话就要把p置为空，否则直接进入到下一句就会报错，因为这个时候队列已经空了
			else
				p = que1.front();
		}
		cout << endl;
	}
}

test.cpp

#include
#include
#include "biTree.h"
#include
#include
using namespace std;

int main()
{
	biTree tree1;
	tree1.construct();
	tree1.preTraverse();
	cout << endl;
	tree1.inTraverse();
	cout << endl;
	tree1.postTraverse();
	cout <<"depth is " << tree1.depth() << endl;
	cout <<"node numbers are " << tree1.nodeNum() << endl;
	cout << "leaves number are " << tree1.leavesNum() << endl;
	biTree tree2(tree1);
	tree2.preTraverse();
	biTree tree3;
	tree3 = tree2;
	tree3.inTraverse();
	biTree tree4;
	tree3 = tree4;
	tree3.postTraverse();
	tree1.destroyTree();

	tree2.inTraverse();
	tree2.noRecurTraver();

	tree2.layerTraverse();
	return 0;
}

四、测试结果

输入“#”代表空节点