[数据结构与算法]c++数据结构二叉树（二叉链表实现）基本操作实现

二叉树：?

????????二叉树（Binary?tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分

性质：

二叉树性质
性质1：二叉树的第i层上至多有2i-1（i≥1）个节点。
性质2：深度为h的二叉树中至多含有2h-1个节点。
性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。
性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）。
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点。
当i>1时，该节点的双亲节点的编号为i/2。
若2i≤n，则有编号为2i的左节点，否则没有左节点。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。

输入：

?

运行结果：

代码：

/*
	朱海垅2030090111
	2021年11月10日
	二叉链表实现二叉树
*/

#include<iostream>
using namespace std;
template <class T>
struct BinTreeNode {
	T data;												//数据域
	BinTreeNode<T>* leftChiild, * rightChild;			//左右子域
	BinTreeNode() :leftChiild(NULL), rightChild(NULL) {}
	BinTreeNode(T x, BinTreeNode<T>* l = NULL, BinTreeNode<T>* r = NULL) :data(x), leftChiild(l), rightChild(r) {}
};
template<class T>
class BinaryTree {
public:
	BinaryTree() : root(NULL) {}							//构造函数
	BinaryTree(T value) :RefValue(value), root(NULL) {}//构造函数
	BinaryTree(BinaryTree<T>& s) { root = Copy(s.root); }						//复制构造函数
	~BinaryTree() { destory(root); }								//析构函数
	bool IsEmpty() { return (root == NULL) ? true : false; }	//返回二叉树是否为空
	BinTreeNode<T>* Parent(BinaryTree<T>* current) { return (root == NULL || root = current) ? NULL : Parent(root, current); }	//返回父节点
	BinTreeNode<T>* LeftChild(BinTreeNode<T>* current) { return (current != NULL) ? current->leftChiild : NULL; }	//返回其节点的左子节点
	BinTreeNode<T>* RightChild(BinTreeNode<T>* current) { return (current != NULL) ? current->rightChild : NULL; }	//返回其节点的右子节点
	int Hight() { return Hight(root); }							//返回树的高度（对数据进行封装）
	int NodeCount() { return NodeCount(root); }					//返回树的节点数目（对数据进行封装）
	int LeafCount() { return LeafCount(root); }					//返回树的叶子节点数（对数据进行封装）
	BinTreeNode<T>* GetRoot() const { return root; }			//返回根节点指针
	void preOrder(void(*vist)(BinTreeNode<T>* p)) { preOrder(root, vist); }//前序遍历
	void inOrder(void (*vist)(BinTreeNode<T>* p)) { inOrder(root, vist); }//中序遍历
	void postOrder(void(*vist)(BinTreeNode<T>* p)) { postOrder(root, vist); }//后序遍历
	/*void levelOrder(void(*vist)(BinTreeNode<T>* p))
	{
		Queue<BinTreeNode<T>*>Q;
		BinTreeNode<T>* p = root;
		Q.EnQueue(p);
		while (!Q.IsEmpty())		//队列不为空时
		{
			Q.DeQueue(p); visit(p);
			if (p->leftChiild != NULL)Q.EnQueue(p->leftChiild);
			if (p->rightChild != NULL)Q.EnQueue(p->rightChild);
		}
	}//层次序遍历(使用队列类实现简单)这里不列出队列类的构造*/

protected:
	BinTreeNode<T>* root;								//二叉树根指针
	T RefValue;											//数据输入停止标志
	void destory(BinTreeNode<T>*& subTree);					//删除
	BinTreeNode<T>* Parent(BinTreeNode<T>* subTree, BinTreeNode<T>* current);//返回父节点
	int Hight(BinTreeNode<T>* subTree);						//返回数的高度
	int NodeCount(BinTreeNode<T>* subTree);					//返回树的节点数
	int LeafCount(BinTreeNode<T>* subtree);						//返回树的叶子节点数
	void CreateBinTree(istream& in, BinTreeNode<T>*& subTree);	//键盘输入建立树(用前序遍历输入)
	BinTreeNode<T>* Copy(BinTreeNode<T>* orignode);				//复制节点函数
	void Traverse(BinTreeNode<T>* subtree, ostream& out);			//前序遍历输出
	void Traverse1(BinTreeNode<T>* subtree, ostream& out);			//中序遍历输出
	void Traverse2(BinTreeNode<T>* subtree, ostream& out);			//后序遍历输出
	void preOrder(BinTreeNode<T>& subtree, void (*vist)(BinTreeNode<T>* p))
	{
		if (subtree != NULL)//递归结束条件为根空
		{
			vist(subtree);							//访问根
			preOrder(subtree->leftChiild, vist);	//访问左子树
			preOrder(subtree->rightChild, vist);	//访问右子树 
		}
	}//前序遍历
	void inOrder(BinTreeNode<T>& subtree, void (*vist)(BinTreeNode<T>* p))
	{
		if (subtree != NULL)
		{
			inOrder(subtree->leftChiild, vist);
			vist(subtree);
			inOrder(subtree->rightChild, vist);
		}
	}//中序遍历
	void postOrder(BinTreeNode<T>& subTree, void (*vist)(BinTreeNode<T>* p))
	{
		if (subTree != NULL)
		{
			postOrder(subTree->leftChiild, vist);
			postOrder(subTree->rightChild, vist);
			vist(subTree);
		}
	}//后序遍历
	template <class T> friend istream& operator>>(istream& in, BinaryTree<T>& Tree);
	template <class T> friend ostream& operator<<(ostream& out, BinaryTree<T>& Tree);
	
};
//删除
template<class T>
void BinaryTree<T>::destory(BinTreeNode<T>*& subTree)
{
	if (subTree != NULL)
	{
		destory(subTree->leftChiild);
		destory(subTree->rightChild);				//递归删除节点
		delete subTree;
	}
}

//返回父节点
template<class T>
BinTreeNode<T>* BinaryTree<T>::Parent(BinTreeNode<T>* subTree, BinTreeNode<T>* current)
{
	if (subTree == NULL)return NULL;
	if (subTree->leftChiild == current || subTree->rightChild == current)return subTree;
	BinTreeNode<T>* p;
	if ((p = Parent(subTree->leftChiild, current)) != NULL)return p;
	else return Parent(subTree->rightChild, current);
}

//返回树高度
template <class T>
int BinaryTree<T>::Hight(BinTreeNode<T>* subtree)
{
	//递归求出树的高度
	if (subtree == NULL)return 0;
	else
	{
		int m = Hight(subtree->leftChiild);
		int n = Hight(subtree->rightChild);
		if (m > n)return (m + 1);
		else return (n + 1);
		//m,n，要么为1，要么为0.从树底往上叠加
	}
}

//返回树节点数
template<class T>
int BinaryTree<T>::NodeCount(BinTreeNode<T>* subtree)
{
	if (subtree == NULL)return 0;
	else return NodeCount(subtree->leftChiild) + NodeCount(subtree->rightChild) + 1;//递归求出节点个数加一（根节点）
}

//返回树叶子节点数目
template<class T>
int BinaryTree<T>::LeafCount(BinTreeNode<T>* subtree)
{
	if (!subtree)return 0;
	if (!subtree->leftChiild && !subtree->rightChild)return 1;//左右子树为空
	else return LeafCount(subtree->leftChiild) + LeafCount(subtree->rightChild);
}

//前序遍历方法输入建立树，以此类推也可以用中序和和后序算法建立
template<class T>
void BinaryTree<T>::CreateBinTree(istream& in, BinTreeNode<T>*& subTree)
{
	T item;
	if (!in.eof())           //表示未读完，继续读取
	{
		cout << "请输入数据：" << endl;
		in >> item;
		if (item != RefValue)
		{
			subTree = new BinTreeNode<T>(item);			//建立根节点
			if (subTree == NULL) { cout << "存储分配错误" << endl; exit(1); }
			cout << "请输入左树：" << endl;
			CreateBinTree(in, subTree->leftChiild);		//建立左子树
			cout << "请输入右树： " << endl;
			CreateBinTree(in, subTree->rightChild);		//建立右子树
		}
		else subTree = NULL;
	}
}

//返回一个以orignode为根的二叉树副本
template<class T>
BinTreeNode<T>* BinaryTree<T>::Copy(BinTreeNode<T>* orignode)
{
	if (orignode == NULL)return NULL;
	BinTreeNode<T>* temp = new BinTreeNode<T>;
	temp->data = orignode->data;
	temp->leftChiild = Copy(orignode->leftChiild);
	temp->rightChild = Copy(orignode->rightChild);
	return temp;
}

//搜索并输出根为subTree的二叉树(前序遍历输出)
template<class T>
void BinaryTree<T>::Traverse(BinTreeNode<T>* subTree, ostream& out)
{
	if (subTree != NULL)//是空则返回，否则一直输出到空
	{
		out << subTree->data << ' ';			//根
		Traverse(subTree->leftChiild, out);		//左
		Traverse(subTree->rightChild, out);		//右
	}
}

//搜索并输出根为subTree的二叉树(中序遍历输出)
template<class T>
void BinaryTree<T>::Traverse1(BinTreeNode<T>* subTree, ostream& out)
{
	if (subTree != NULL)//是空则返回，否则一直输出到空
	{
		Traverse(subTree->leftChiild, out);		//左
		out << subTree->data << ' ';			//根
		Traverse(subTree->rightChild, out);		//右
	}
}

//搜索并输出根为subTree的二叉树(后序遍历输出)
template<class T>
void BinaryTree<T>::Traverse2(BinTreeNode<T>* subTree, ostream& out)
{
	if (subTree != NULL)//是空则返回，否则一直输出到空
	{
		Traverse(subTree->leftChiild, out);		//左
		Traverse(subTree->rightChild, out);		//右
		out << subTree->data << ' ';			//根
	}
}


//重载输入流操作，输入并建立一颗二叉树Tree
template<class T>
istream& operator>>(istream& in, BinaryTree<T>& Tree)
{
	Tree.CreateBinTree(in, Tree.root);
	return in;
}

//重载输出操作，输出二叉树Tree
template<class T>
ostream& operator<<(ostream& out, BinaryTree<T>& Tree)
{
	out << "二叉树的前序遍历：" << endl;
	Tree.Traverse(Tree.root, out);//从根开始输出
	out << endl;
	out << "二叉树的中序遍历：" << endl;
	Tree.Traverse1(Tree.root, out);
	out << endl;
	out << "二叉树的后序遍历：" << endl;
	Tree.Traverse2(Tree.root, out);
	out << endl;
	return out;
}

int main()
{
	char a='#';
	BinaryTree<char> A(a);		//默认构造函数以输入#为结束构造树
	cout << "输入”#“为构造函数结束" << endl;
	cout << "输入二叉树A:" << endl;
	cin >> A;
	char g = A.GetRoot()->data;
	cout << "根节点数据：     " << g << endl;
	int h = A.Hight();
	cout << "树高：     " << h << endl;
	int l = A.LeafCount();
	cout << "叶子节点数：       " << l << endl;
	cout << A;
	return 0;
}

?ps:

部分知识点来自百度百科。

?