[数据结构与算法]二叉链表基本功能的实现

1. BiTree.h

#ifndef BITREE_H
#define BITREE_H

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

template<class T>
struct BiNode
{
	T data;
	BiNode<T>*lchild;
	BiNode<T>*rchild;
};

template<class T>
class BiTree
{
private:
	BiNode<T>*root;
	BiNode<T>*CreateByPre(vector<T>&pre, int &i);
	BiNode<T>*CreateByPreMid(vector<T>&pre, vector<T>&mid, int ipre, int imid, int n);
	BiNode<T>*Copy(BiNode<T>*p);
	void Free(BiNode<T>*p);
	void PreOrder(BiNode<T>*p);
	void InOrder(BiNode<T>*p);
	void PostOrder(BiNode<T>*p);
	int Count(BiNode<T>*p);
	int Height(BiNode<T>*p);
	BiNode<T>*Search(BiNode<T>*p, T e);
	BiNode<T>*SearchParent(BiNode<T>*p, BiNode<T>*child);
public:
	BiTree();
	BiTree(vector<T>&pre);
	BiTree(vector<T>&pre, vector<T>&mid);
	BiTree(BiTree<T>&tree);
	~BiTree();
	void PreOrder();
	void InOrder();
	void PostOrder();
	void LevelOrder();
	int Count();
	int Height();
	BiNode<T>*Search(T e);
	BiNode<T>*SearchParent(BiNode<T>*child);
};

#endif

2. BiTree.cpp

#define _CRT_SECURE_NO_WARNINGS   1


#include"BiTree.h"

template<class T>
BiTree<T>::BiTree()
{
	root = NULL;
	lchild = NULL;
	rchild = NULL;
}
template<class T>
BiNode<T>* BiTree<T>::CreateByPre(vector<T>&pre, int &i)
{
	T e = pre[i];
	i++;
	if (e == '*')
	{
		return ;
	}
	BiNode<T>*p = new BiNode<T>;
	p->data = e;
	p->lchild = CreateByPre(pre, i);
	p->rchild = CreateByPre(pre, i);
	return p;
}
template<class T>
BiTree<T>::BiTree(vector<T>&pre)
{
	int i=0;
	root = CreateByPre(pre, i);
}

template<class T>
BiNode<T>* BiTree<T>::CreateByPreMid(vector<T>&pre, vector<T>&mid, int ipre, int imid, int n)
{
	if (n == 0)
		return NULL;
	BiNode<T>*p = new BiNode<T>;
	p->data = pre[ipre];
	for (int i = 0; i < n; i++)
	{
		if (pre[ipre] == mid[imid + i])
			break;
	}
	pre->lchild = CreateByPreMid(pre, mid, ipre + 1, imid, i);
	pre->rchild = CreateByPreMid(pre, mid, ipre + i + 1, imid + i + 1, n - i - 1);
	return p;
}
template<class T>
BiTree<T>::BiTree(vector<T>&pre, vector<T>&mid)
{
	n = pre.size();
	root = CreateByPreMid(pre, mid, 0, 0, n);
}

template<class T>
BiNode<T>*BiTree<T>::Copy(BiNode<T>*p)
{
	if (p == NULL)
	{
		return NULL;
	}
	BiNode<T>*newp = new BiNode<T>;
	newp->data = p->data;
	newp->lchild = Copy(p->lchild);
	newp->rchild = Copy(p->rchild);
	return newp;
}
template<class T>
BiTree<T>::BiTree(BiTree<T>&tree)
{
	root = Copy(tree.root);
}
template<class T>
void BiTree<T>::Free(BiNode<T>*p)
{
	if (p == NULL)
		return;
	Free(p->lchild);
	Free(p->rchild);
	delete p;
}
template<class T>
BiTree<T>::~BiTree()
{
	Free(root);
}
template<class T>
void BiTree<T>::PreOrder(BiNode<T>*p)
{
	if (p == NULL)
	{
		cout << "NULL   ";
		return;
	}
	cout << p->data << "   ";
	PreOrder(p ->lchild);
	PreOrder(p->rchild);
}
template<class T>
void BiTree<T>::PreOrder()
{
	PreOrder(root);
}
template<class T>
void BiTree<T>::InOrder(BiNode<T>*p)
{
	if (p == NULL)
	{
		cout << "NULL   ";
		return;
	}
	InOrder(p ->lchild);
	cout << p->data << "   ";
	InOrder(p->rchild);
}
template<class T>
void BiTree<T>::InOrder()
{
	InOrder(root);
}
template<class T>
void BiTree<T>::PostOrder(BiNode<T>*p)
{
	if (p == NULL)
	{
		cout << "NULL   ";
		return;
	}
	PostOrder(p -> lchild);
	PostOrder(p->rchild);
	cout << p->data << "   ";
}
template<class T>
void BiTree<T>::PostOrder()
{
	PostOrder(root);
}
template<class T>
void BiTree<T>::LevelOrder()
{
	if (root == NULL)
		return;
	queue<BiNode<T>*>Q;
	Q.push(root);
	while (!Q.empty())
	{
		int n = Q.size();
		for (int i = 0; i < n; i++)
		{
			BiNode<T>*p = Q.front();
			cout << p->data << "   ";
			Q.pop();
			if (p->lchild != NULL)
				Q.push(p->lchild);
			if (p->rchild != NULL)
				Q.push(p->rchild);
		}
		cout << endl;
	}
}
template<class T>
int BiTree<T>::Count(BiNode<T>*p)
{
	if (p == NULL)
		return 0;
	int left = Count(p->lchild);
	int right = Count(p->rchild);
	return 1 + left + right;
}

template<class T>
int BiTree<T>::Count()
{
	return Count(root);
}


template<class T>
int BiTree<T>::Height(BiNode<T>*p)
{
	if (p == NULL)
		return 0;
	int left = 0;
	int right = 0;
	left = Height(p->lchild);
	right = Height(p->rchild);
	if (left > right)
		return left + 1;
	else
		return right + 1;

}
template<class T>
int BiTree<T>::Height()
{
	return Height(root);
}

template<class T>
BiNode<T>*BiTree<T>::Search(BiNode<T>*p, T e)
{
	if (p == NULL)
	{
		return NULL;
	}
	if (p->data == e)
	{
		return p;
	}
	BiNode<T>*q = Search(p->lchild, e);
	if (q != NULL)
	{
		return q;
	}
	return Search(p->rchild, e);
}
template<class T>
BiNode<T>*BiTree<T>::Search(T e)
{
	return Search(root, e);
}


template<class T>
BiNode<T>*BiTree<T>::SearchParent(BiNode<T>*p, BiNode<T>*child)
{
	if (p == NULL || child == NULL)
		return NULL;
	if (p->lchild == child || p->rchild == child)
		return p;
	BiNode<T>*q = SearchParent(p->lchild, child);
	if (q != NULL)
		return q;
	return SearchParent(p->rchild, child);
}
template<class T>
BiNode<T>*BiTree<T>::SearchParent(BiNode<T>*child)
{
	return SearchParent(root, child);
}

3. test.cpp

#define _CRT_SECURE_NO_WARNINGS   1


#include"BiTree.cpp"
#include<iostream>
#include<queue>
#include<vector>
using namespace std;

void menu()
{
	cout << endl;
	cout << "|-------------------------------------|" << endl;
	cout << "|----------- 欢迎来到顺序表 ----------|" << endl;
	cout << "|---------------1. 先序输出-----------|" << endl;
	cout << "|---------------2. 中序输出-----------|" << endl;
	cout << "|---------------3. 后序输出-----------|" << endl;
	cout << "|---------------4. 层序输出-----------|" << endl;
	cout << "|---------------5. 找结点数-----------|" << endl;
	cout << "|---------------6. 求树高度-----------|" << endl;
	cout << "|---------------7. 寻找结点-----------|" << endl;
	cout << "|---------------8. 寻找双亲-----------|" << endl;
	cout << "|---------------0. 退出---------------|" << endl;
	cout << "|-------------------------------------|" << endl;
}
int main()
{
	vector<char>GetTree;
	char num;
	int input = 0;
	cout << "现在开始我们的程序之旅" << endl;
	cout << endl;
	cout << "请输入先序序列，我将以此来构造一棵树，记住，请用星号来代表空指针，并且，不要忘记输入空格" << endl;
	while (1)
	{
		cin >> num;
		GetTree.push_back(num);
		if (cin.get() == '\n')
			break;
	}
	BiTree<char>tree(GetTree);
	cout << "构造完成，您可以选择接下来的操作" << endl;
	do
	{
		menu();
		cout << endl;
		cout << "请选择您要进行的操作" << endl;
		cout << endl;
		cin >> input;
		switch (input)
		{
		case 1:
			cout << "先序遍历的结果如下:";
			cout << endl;
			tree.PreOrder();
			break;
		case 2:
			cout << "中序遍历的结果如下:";
			cout << endl;
			tree.InOrder();
			break;
		case 3:
			cout << "后序遍历的结果如下:";
			cout << endl;
			tree.PostOrder();
			break;
		case 4:
			cout << "层序遍历的结果如下:";
			cout << endl;
			tree.LevelOrder();
			break;
		case 5:
			cout << "该树的结点数为: ";
			cout << tree.Count() << endl;
			break;
		case 6:
			cout << "该树的高度为: ";
			cout << tree.Height() << endl;
			break;
		case 7:
			char ch;
			cout << "请输入您要查找的值" << endl;
			cin >> ch;
			if (tree.Search(ch))
			{
				cout << "查找到了，该结点存在于该树中" << endl;
			}
			else
			{
				cout << "很遗憾，该结点并不存在于该树中" << endl;
			}
			break;
		case 8:
			char ch1;
			cout << "请输入您要查找其双亲的值" << endl;
			cin >> ch1;
			if (tree.Search(ch1))
			{
				cout << "它的双亲的值为：";
				cout<<tree.SearchParent(tree.Search(ch1))->data<<endl;
			}
			else
			{
				cout << "很遗憾，该结点并不存在于该树中，所以我们不能为您查找到它的双亲" << endl;
			}
			break;
		case 0:
			cout << "程序退出,感谢您的使用" << endl;
			exit(-1);
			break;
		default:
			cout << "抱歉，您的输入有误，我无法理解当前您想要进行的操作，请重新输入您的选择" << endl;
		}

	} while (input);
	return 0;
}