[数据结构与算法]二叉树终极版(递归)

二叉树终极版(递归)

二叉树是一个典型的递归的类型

二叉树结点

template<class T>
struct BinTreeNode
{
	T data;
	BinTreeNode<T>* leftchild;
	BinTreeNode<T>* rightchild;
	BinTreeNode()
	{
		leftchild = NULL;
		rightchild = NULL;
	}
	BinTreeNode(T x)
	{
		data = x;
		leftchild = NULL;
		rightchild = NULL;
	}
};

二叉树类函数体

class BinTree
{
public:
	BinTree();
	~BinTree();
	BinTreeNode<T>* Get_root()
	{
		return root;
	}  //返回根结点
	void CreateTree(BinTreeNode<T>*& root);  //创建二叉树
	void DeleTree(BinTreeNode<T>* root);  //销毁二叉树
	void PreTra(BinTreeNode<T>* root);  //前序遍历
	void InodTra(BinTreeNode<T>* root);  //中序遍历
	void PosodTra(BinTreeNode<T>* root);  //后序遍历
	void Output_leaves(BinTreeNode<T>* root);  //输出叶子结点
	void count_0_1_2(BinTreeNode<T>* root, int& i, int& j, int& k);  //计算度为0,1,2的结点的个数
	int Calc_Nodes(BinTreeNode<T>* root);  //计算二叉树的结点个数
	int Calc_height(BinTreeNode<T>* root);  //计算二叉树的深度
	BinTreeNode<T>* Find(BinTreeNode <T>* root, T item);  //在二叉树中搜索item
	BinTreeNode<T>* Parent(BinTreeNode <T>* root, T item);  //返回item的父结点指针     
	BinTreeNode<T>* LeftChild(BinTreeNode<T>* root, T item);  //返回item的左孩子指针     
	BinTreeNode<T>* RightChild(BinTreeNode<T>* root, T item);  //返回item的右孩子指针
protected:
	BinTreeNode<T>* root;
};

二叉树的创建

template<class T>
void BinTree<T>::CreateTree(BinTreeNode<T>*& root)
{
	T x;
	cin >> x;
	if (x == '#')
	{
		root = NULL;
		return;
	}
	root = new BinTreeNode<T>(x);
	if (root == NULL)
		return;
	CreateTree(root->leftchild);
	CreateTree(root->rightchild);
}

二叉树的销毁

template<class T>
void BinTree<T>::DeleTree(BinTreeNode<T>* root)
{
	if (root == NULL)
		return;
	DeleTree(root->leftchild);
	DeleTree(root->rightchild);
	delete root;
}

前序遍历

template<class T>
void BinTree<T>::PreTra(BinTreeNode<T>* root)
{
	if (root != NULL)
	{
		cout << root->data << ' ';
		PreTra(root->leftchild);
		PreTra(root->rightchild);
	}
}

中序遍历

template<class T>
void BinTree<T>::InodTra(BinTreeNode<T>* root)
{
	if (root != NULL)
	{
		InodTra(root->leftchild);
		cout << root->data << ' ';
		InodTra(root->rightchild);
	}
}

后序遍历

template<class T>
void BinTree<T>::PosodTra(BinTreeNode<T>* root)
{
	if (root != NULL)
	{
		PosodTra(root->leftchild);
		PosodTra(root->rightchild);
		cout << root->data << ' ';
	}
}

输出叶子结点

template<class T>
void BinTree<T>::Output_leaves(BinTreeNode<T>* root)
{
	if (root == NULL) return;
	if (root->leftchild == NULL && root->rightchild == NULL)
	{
		cout << root->data << endl;
	}
	Output_leaves(root->leftchild);
	Output_leaves(root->rightchild);
}

计算结点度为0,1,2的个数

template<class T>
void BinTree<T>::count_0_1_2(BinTreeNode<T>* root, int& i, int& j, int& k)
{
	if (root != NULL)
	{
		if (root->leftchild == NULL && root->rightchild == NULL)
			i++;
		if (root->leftchild == NULL && root->rightchild != NULL || root->leftchild != NULL && root->rightchild == NULL)
			j++;
		if (root->leftchild != NULL && root->rightchild != NULL)
			k++;
		count(root->leftchild, i, j, k);
		count(root->rightchild, i, j, k);
	}
}

计算二叉树结点的个数

template<class T>
int BinTree<T>::Calc_Nodes(BinTreeNode<T>* root)
{
	if (root == NULL)
		return 0;
	return	1 + Calc_Nodes(root->leftchild) + Calc_Nodes(root->rightchild);
}

计算二叉树的高度(深度)

template<class T>
int BinTree<T>::Calc_height(BinTreeNode<T>* root)
{
	int hl = 0, hr = 0, maxh = 0;
	if (root == NULL)
		return 0;
	hl = Calc_height(root->leftchild);
	hr = Calc_height(root->rightchild);
	maxh = hl > hr ? hl : hr;
	return maxh + 1;
}

二叉树中搜索一个指定的x值

template<class T>
BinTreeNode<T>* BinTree<T>::Find(BinTreeNode <T>* root, T item)
{
	BinTreeNode<T>* temp = NULL;
	if (root == NULL)
		return NULL;
	if (root->data == item)
		return root;
	temp = Find(root->leftchild, item);
	if (temp)
		return temp;
	temp = Find(root->rightchild, item);
	if (temp)
		return temp;
	return NULL;
}

求二叉树某个结点的父结点

template<class T>
BinTreeNode<T>* BinTree<T>::Parent(BinTreeNode <T>* root, T item)
{
	BinTreeNode<T>* temp = NULL;
	if (root == NULL)
		return NULL;
	if (root->leftchild != NULL)
	{
		if (root->leftchild->data == item)
			return root;
	}
	if (root->rightchild != NULL)
	{
		if (root->rightchild->data == item)
			return root;
	}
	temp = Parent(root->leftchild, item);
	if (temp)
		return temp;
	temp = Parent(root->rightchild, item);
	if (temp)
		return temp;
	return NULL;
}

求二叉树某个结点的左子女结点

template<class T>
BinTreeNode<T>* BinTree<T>::LeftChild(BinTreeNode<T>* root, T item)
{
	BinTreeNode<T>* temp = NULL;
	if (root == NULL)
		return NULL;
	if (root->data == item)
		return root->leftchild;
	temp = LeftChild(root->leftchild, item);
	if (temp)
		return temp;
	temp = LeftChild(root->rightchild, item);
	if (temp)
		return temp;
}

求二叉树某个结点的右子女结点

template<class T>
BinTreeNode<T>* BinTree<T>::RightChild(BinTreeNode<T>* root, T item)
{
	BinTreeNode<T>* temp = NULL;
	if (root == NULL)
		return NULL;
	if (root->data == item)
		return root->rightchild;
	temp = RightChild(root->leftchild, item);
	if (temp)
		return temp;
	temp = RightChild(root->rightchild, item);
	if (temp)
		return temp;
}

主函数

int main()
{
	BinTreeNode<char>* root;
	BinTree<char> t;
	int i = 0, j = 0, k = 0, count = 0, height = 0;
	char ch;
	t.CreateTree(root);
	cout << "二叉树的前序遍历为:" << endl;
	t.PreTra(root);
	cout << endl;
	cout << "二叉树的中序遍历为:" << endl;
	t.InodTra(root);
	cout << endl;
	cout << "二叉树的后序遍历为:" << endl;
	t.PosodTra(root);
	cout << endl;
	cout << "输出二叉树的叶子结点:" << endl;
	t.Output_leaves(root);
	t.count_0_1_2(root, i, j, k);
	cout << "二叉树0度点个数:" << i << ' ' << "二叉树1度点个数:" << j << ' ' << "二叉树2度点个数:" << k << endl;
	count = t.Calc_Nodes(root);
	cout << "二叉树的结点个数为:" << count << endl;
	height = t.Calc_height(root);
	cout << "二叉树的高度(深度)为:" << height << endl;
	cout << "搜索指定x值的结点,以'#'为结束" << endl;
	while (cin >> ch && ch != '#')
	{
		if (t.Find(root, ch))
			cout << "success" << endl;
		else
			cout << "failure" << endl;
	}
	cout << "搜索某结点的父结点和左右子女结点,以'#'为结束" << endl;
	while (cin >> ch && ch != '#')
	{
		BinTreeNode<char>* temp = NULL;
		temp = t.Parent(root, ch);
		if (temp)
			cout << "父结点为:" << temp->data << endl;
		else
			cout << "父结点为:" << "NULL" << endl;
		temp = t.LeftChild(root, ch);
		if (temp)
			cout << "左子女结点结点为:" << temp->data << endl;
		else
			cout << "左子女结点结点为:" << "NULL" << endl;
		temp = t.RightChild(root, ch);
		if (temp)
			cout << "右子女结点为结点为:" << temp->data << endl;
		else
			cout << "右子女结点为结点为:" << "NULL" << endl;
	}
	t.DeleTree(root);
	return 0;
}

完整代码

#include<iostream>

using namespace std;

template<class T>
struct BinTreeNode
{
	T data;
	BinTreeNode<T>* leftchild;
	BinTreeNode<T>* rightchild;
	BinTreeNode()
	{
		leftchild = NULL;
		rightchild = NULL;
	}
	BinTreeNode(T x)
	{
		data = x;
		leftchild = NULL;
		rightchild = NULL;
	}
};

template<class T>
class BinTree
{
public:
	BinTree();
	~BinTree();
	BinTreeNode<T>* Get_root()
	{
		return root;
	}  //返回根结点
	void CreateTree(BinTreeNode<T>*& root);  //创建二叉树
	void DeleTree(BinTreeNode<T>* root);  //销毁二叉树
	void PreTra(BinTreeNode<T>* root);  //前序遍历
	void InodTra(BinTreeNode<T>* root);  //中序遍历
	void PosodTra(BinTreeNode<T>* root);  //后序遍历
	void Output_leaves(BinTreeNode<T>* root);  //输出叶子结点
	void count_0_1_2(BinTreeNode<T>* root, int& i, int& j, int& k);  //计算度为0,1,2的结点的个数
	int Calc_Nodes(BinTreeNode<T>* root);  //计算二叉树的结点个数
	int Calc_height(BinTreeNode<T>* root);  //计算二叉树的深度
	BinTreeNode<T>* Find(BinTreeNode <T>* root, T item);  //在二叉树中搜索item
	BinTreeNode<T>* Parent(BinTreeNode <T>* root, T item);  //返回item的父结点指针     
	BinTreeNode<T>* LeftChild(BinTreeNode<T>* root, T item);  //返回item的左孩子指针     
	BinTreeNode<T>* RightChild(BinTreeNode<T>* root, T item);  //返回item的右孩子指针
protected:
	BinTreeNode<T>* root;
};

template<class T>
BinTree<T>::BinTree()
{
	root = NULL;
}

template<class T>
BinTree<T>::~BinTree()
{

}

template<class T>
void BinTree<T>::CreateTree(BinTreeNode<T>*& root)
{
	T x;
	cin >> x;
	if (x == '#')
	{
		root = NULL;
		return;
	}
	root = new BinTreeNode<T>(x);
	if (root == NULL)
		return;
	CreateTree(root->leftchild);
	CreateTree(root->rightchild);
}

template<class T>
void BinTree<T>::DeleTree(BinTreeNode<T>* root)
{
	if (root == NULL)
		return;
	DeleTree(root->leftchild);
	DeleTree(root->rightchild);
	delete root;
}

template<class T>
void BinTree<T>::PreTra(BinTreeNode<T>* root)
{
	if (root != NULL)
	{
		cout << root->data << ' ';
		PreTra(root->leftchild);
		PreTra(root->rightchild);
	}
}

template<class T>
void BinTree<T>::InodTra(BinTreeNode<T>* root)
{
	if (root != NULL)
	{
		InodTra(root->leftchild);
		cout << root->data << ' ';
		InodTra(root->rightchild);
	}
}

template<class T>
void BinTree<T>::PosodTra(BinTreeNode<T>* root)
{
	if (root != NULL)
	{
		PosodTra(root->leftchild);
		PosodTra(root->rightchild);
		cout << root->data << ' ';
	}
}

template<class T>
void BinTree<T>::Output_leaves(BinTreeNode<T>* root)
{
	if (root == NULL) return;
	if (root->leftchild == NULL && root->rightchild == NULL)
	{
		cout << root->data << endl;
	}
	Output_leaves(root->leftchild);
	Output_leaves(root->rightchild);
}

template<class T>
void BinTree<T>::count_0_1_2(BinTreeNode<T>* root, int& i, int& j, int& k)
{
	if (root != NULL)
	{
		if (root->leftchild == NULL && root->rightchild == NULL)
			i++;
		if (root->leftchild == NULL && root->rightchild != NULL || root->leftchild != NULL && root->rightchild == NULL)
			j++;
		if (root->leftchild != NULL && root->rightchild != NULL)
			k++;
		count_0_1_2(root->leftchild, i, j, k);
		count_0_1_2(root->rightchild, i, j, k);
	}
}

template<class T>
int BinTree<T>::Calc_Nodes(BinTreeNode<T>* root)
{
	if (root == NULL)
		return 0;
	return	1 + Calc_Nodes(root->leftchild) + Calc_Nodes(root->rightchild);
}

template<class T>
int BinTree<T>::Calc_height(BinTreeNode<T>* root)
{
	int hl = 0, hr = 0, maxh = 0;
	if (root == NULL)
		return 0;
	hl = Calc_height(root->leftchild);
	hr = Calc_height(root->rightchild);
	maxh = hl > hr ? hl : hr;
	return maxh + 1;
}

template<class T>
BinTreeNode<T>* BinTree<T>::Find(BinTreeNode <T>* root, T item)
{
	BinTreeNode<T>* temp = NULL;
	if (root == NULL)
		return NULL;
	if (root->data == item)
		return root;
	temp = Find(root->leftchild, item);
	if (temp)
		return temp;
	temp = Find(root->rightchild, item);
	if (temp)
		return temp;
	return NULL;
}

template<class T>
BinTreeNode<T>* BinTree<T>::Parent(BinTreeNode <T>* root, T item)
{
	BinTreeNode<T>* temp = NULL;
	if (root == NULL)
		return NULL;
	if (root->leftchild != NULL)
	{
		if (root->leftchild->data == item)
			return root;
	}
	if (root->rightchild != NULL)
	{
		if (root->rightchild->data == item)
			return root;
	}
	temp = Parent(root->leftchild, item);
	if (temp)
		return temp;
	temp = Parent(root->rightchild, item);
	if (temp)
		return temp;
	return NULL;
}

template<class T>
BinTreeNode<T>* BinTree<T>::LeftChild(BinTreeNode<T>* root, T item)
{
	BinTreeNode<T>* temp = NULL;
	if (root == NULL)
		return NULL;
	if (root->data == item)
		return root->leftchild;
	temp = LeftChild(root->leftchild, item);
	if (temp)
		return temp;
	temp = LeftChild(root->rightchild, item);
	if (temp)
		return temp;
}

template<class T>
BinTreeNode<T>* BinTree<T>::RightChild(BinTreeNode<T>* root, T item)
{
	BinTreeNode<T>* temp = NULL;
	if (root == NULL)
		return NULL;
	if (root->data == item)
		return root->rightchild;
	temp = RightChild(root->leftchild, item);
	if (temp)
		return temp;
	temp = RightChild(root->rightchild, item);
	if (temp)
		return temp;
}

int main()
{
	BinTreeNode<char>* root;
	BinTree<char> t;
	int i = 0, j = 0, k = 0, count = 0, height = 0;
	char ch;
	t.CreateTree(root);
	cout << "二叉树的前序遍历为:" << endl;
	t.PreTra(root);
	cout << endl;
	cout << "二叉树的中序遍历为:" << endl;
	t.InodTra(root);
	cout << endl;
	cout << "二叉树的后序遍历为:" << endl;
	t.PosodTra(root);
	cout << endl;
	cout << "输出二叉树的叶子结点:" << endl;
	t.Output_leaves(root);
	t.count_0_1_2(root, i, j, k);
	cout << "二叉树0度点个数:" << i << ' ' << "二叉树1度点个数:" << j << ' ' << "二叉树2度点个数:" << k << endl;
	count = t.Calc_Nodes(root);
	cout << "二叉树的结点个数为:" << count << endl;
	height = t.Calc_height(root);
	cout << "二叉树的高度(深度)为:" << height << endl;
	cout << "搜索指定x值的结点,以'#'为结束" << endl;
	while (cin >> ch && ch != '#')
	{
		if (t.Find(root, ch))
			cout << "success" << endl;
		else
			cout << "failure" << endl;
	}
	cout << "搜索某结点的父结点和左右子女结点,以'#'为结束" << endl;
	while (cin >> ch && ch != '#')
	{
		BinTreeNode<char>* temp = NULL;
		temp = t.Parent(root, ch);
		if (temp)
			cout << "父结点为:" << temp->data << endl;
		else
			cout << "父结点为:" << "NULL" << endl;
		temp = t.LeftChild(root, ch);
		if (temp)
			cout << "左子女结点结点为:" << temp->data << endl;
		else
			cout << "左子女结点结点为:" << "NULL" << endl;
		temp = t.RightChild(root, ch);
		if (temp)
			cout << "右子女结点为结点为:" << temp->data << endl;
		else
			cout << "右子女结点为结点为:" << "NULL" << endl;
	}
	t.DeleTree(root);
	return 0;
}