数据结构实验2(二叉链表实现二叉树的基本运算)

包含的二叉树运算: 删除一个二叉树, 求一颗二叉树的高度, 求一颗二叉树中叶子结点数, 复制一颗二叉树, 交换一颗二叉树的左右子树,

自上到下, 自左到右层次遍历一颗二叉树.

增加相关功能完善即可, 层次遍历利用队列作为辅助的数据结构, 元素类型是指向二叉树中结点的指针类型.

实现代码:

#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
template <class T>
struct BTNode
{
	/* data */
	BTNode() { lChild = rChild = NULL; }
	BTNode(const T& x) {
		element = x;
		lChild = rChild = NULL;
	}
	BTNode(const T& x, BTNode<T>* l, BTNode<T>* r) {
		element = x;
		lChild = l;
		rChild = r;
	}
	T element;
	BTNode<T>* lChild, *rChild;
};
template <class T>
class Queue
{
public:
	virtual bool IsEmpty() const = 0; // 队列为空返回true
	virtual bool IsFull() const = 0; // 队列满返回true
	virtual bool Front(T &x) const = 0; // 队头元素赋给x，操作成功返回true
	virtual bool EnQueue(T x)  = 0; // 队尾插入元素x，操作成功返回true
	virtual bool DeQueue() = 0; // 删除队头元素，操作成功返回true
	virtual bool Clear() = 0; // 清除队列中所有元素
};
template <class T>
class SeqQueue:public Queue<T>
{
public:
	SeqQueue(int mSize);
	~SeqQueue() { delete []q; }
	bool IsEmpty() const { return front == rear; } // front与rear相等时循环队列为空
	bool IsFull() const { return (rear + 1) % maxSize == front; } // front与(rear + 1) % maxSize相等时循环队列满
	bool Front(T &x) const;
	bool EnQueue(T x);
	bool DeQueue();
	bool Clear() { front = rear = 0; return true; }
	/* data */
private:
	int front, rear, maxSize; // 队头元素 队尾元素 数组最大长度
	T *q;
};
template <class T>
SeqQueue<T>::SeqQueue(int mSize)
{
	maxSize = mSize;
	q = new T[maxSize];
	front = rear = 0;
}
template <class T>
bool SeqQueue<T>::Front(T &x) const
{
	if(IsEmpty()) { // 空队列处理
		cout << "SeqQueue is empty" << endl;
		return false;
	}
	x = q[(front + 1) % maxSize];
	return true;
}
template <class T>
bool SeqQueue<T>::EnQueue(T x)
{
	if(IsFull()) { // 溢出处理
		cout << "SeqQueue is full" << endl;
		return false;
	}
	q[(rear = (rear + 1) % maxSize)] = x;
	return true;
}
template <class T>
bool SeqQueue<T>::DeQueue()
{
	if(IsEmpty()) { // 空队列处理
		cout << "SeqQueue is empty" << endl;
		return false;
	}
	front = (front + 1) % maxSize;
	return true;
}

template <class T>
class BinaryTree
{
public:
	BinaryTree(): s(100){ root = NULL; }
	bool IsEmpty() const; // 判断是否为空, 是返回true
	void Clear(); // 移去所有结点, 成为空二叉树
	bool Root(T& x) const; // 若二叉树为空, 则x为根的值, 返回true
    BTNode<T>* Root();
    int Size();
    int Count() { return Count(root); }
	void MakeTree(const T& x, BinaryTree<T>& left, BinaryTree<T>& right); // 构造一颗二叉树, 根的值为x, left & right为左右子树
	void BreakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right); // 拆分二叉树为三部分, x为根的值, left & right为左右子树
	void PreOrder(void (*Visit)(T& x)); // 先序遍历二叉树
	void InOrder(void (*Visit)(T& x)); // 中序遍历二叉树
	void PostOrder(void (*Visit)(T& x)); // 后序遍历二叉树
	int High(BTNode<T> *p); // 返回二叉树高度
	int Num(BTNode<T> *p); // 返回二叉树叶子结点数
	BTNode<T> *Copy(BTNode<T> *t); // 复制二叉树
	void Exchange(BTNode<T> *&t); // 交换二叉树左右子树
	void Level_Traversal(void(*Visit)(T &x)); // 层次遍历二叉树
	BTNode<T>* root;
protected:
	SeqQueue<T> s;
private:
	void Clear(BTNode<T> *t);
    int Size(BTNode<T> *t); // 返回二叉树结点个数
	int Count(BTNode<T> *t); // 返回二叉树只有一个孩子的结点个数
	void PreOrder(void (*Visit)(T &x), BTNode<T> *t);
	void InOrder(void (*Visit)(T &x), BTNode<T> *t);
	void PostOrder(void (*Visit)(T &x), BTNode<T> *t);
	void Level_Traversal(void(*Visit)(T &x), BTNode<T> *t);
};
template <class T>
void Visit(T &x)
{
	cout << x << '\t';
}

template <class T>
BTNode<T>* BinaryTree<T>::Root()
{
    return root;
}
template <class T>
bool BinaryTree<T>::Root(T &x) const
{
	if(root) {
		x = root -> element;
		return true;
	}
	return false;
}

template <class T>
void BinaryTree<T>::Clear()
{
	Clear(root);
}

template <class T>
void BinaryTree<T>::Clear(BTNode<T> *t)
{
	if(t) {
		Clear(t -> lChild);
		Clear(t -> rChild);
		cout << "delete" << t -> element << "..." << endl;
		delete t;
	}
}

template <class T>
void BinaryTree<T>::MakeTree(const T& x, BinaryTree<T>& left, BinaryTree<T>& right)
{
	if(root || &left == &right) return;
	root = new BTNode<T>(x, left.root, right.root);
	left.root = right.root = NULL;
}

template <class T>
void BinaryTree<T>::BreakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right)
{
	if(!root || &left == &right || left.root || right.root) return;
	x = root -> element;
	left.root = root -> lChild;
	right.root = root -> rChild;
	delete root;
	root = NULL;
}

template <class T>
void BinaryTree<T>::PreOrder(void (*Visit)(T& x))
{
	PreOrder(Visit, root);
}
template <class T>
void BinaryTree<T>::PreOrder(void (*Visit)(T& x), BTNode<T>* t)
{
	if(t) {
		Visit(t -> element);
		PreOrder(Visit, t -> lChild);
		PreOrder(Visit, t -> rChild);
	}
}

template <class T>
void BinaryTree<T>::InOrder(void (*Visit)(T& x))
{
	InOrder(Visit, root);
}
template <class T>
void BinaryTree<T>::InOrder(void (*Visit)(T& x), BTNode<T>* t)
{
	if(t) {
		InOrder(Visit, t -> lChild);
		Visit(t -> element);
		InOrder(Visit, t -> rChild);
	}
}

template <class T>
void BinaryTree<T>::PostOrder(void (*Visit)(T& x))
{
	PostOrder(Visit, root);
}
template <class T>
void BinaryTree<T>::PostOrder(void (*Visit)(T& x), BTNode<T>* t)
{
	if(t) {
		PostOrder(Visit, t -> lChild);
		PostOrder(Visit, t -> rChild);
		Visit(t -> element);
	}
}

template <class T>
int BinaryTree<T>::Size()
{
	return Size(root);
}
template <class T>
int BinaryTree<T>::Size(BTNode<T> *t)
{
	if(!t) return 0;
	return Size(t -> lChild) + Size(t -> rChild) + 1;
}

template <class T>
int BinaryTree<T>::Count(BTNode<T> *t)
{
	if(!t) return 0;
	if(((t -> lChild) && (!t -> rChild)) || ((!t -> lChild) && (t -> rChild))) return 1;
	return Count(t -> lChild) + Count(t -> rChild);
}

template <class T>
int BinaryTree<T>::High(BTNode<T> *p)
{
	if(p == NULL) return 0;
	else if(p -> lChild == NULL && p -> rChild ==NULL) return 1;
	else return(High(p -> lChild) > High(p -> rChild) ? High(p -> lChild) + 1 : High(p -> rChild) + 1);
}

template <class T>
int BinaryTree<T>::Num(BTNode<T> *p)
{
	if(p) {
		if(p -> lChild == NULL && p -> rChild == NULL) return 1;
		else return Num(p -> lChild) + Num(p -> rChild);
	}
	else return 0;
}

template <class T>
BTNode<T>*BinaryTree<T>::Copy(BTNode<T> *t)
{
	if(t == NULL) return NULL;
	BTNode<T> *q = new BTNode<T>(t -> element);
	q -> lChild = Copy(t -> lChild);
	q -> rChild = Copy(t -> rChild);
	return q;
}

template <class T>
void BinaryTree<T>::Exchange(BTNode<T> *&t)
{
	if(t) {
		BTNode<T> *q = t -> lChild;
		t -> lChild = t -> rChild;
		t -> rChild = q;
		Exchange(t -> lChild);
		Exchange(t -> rChild);
	}
}

template <class T>
void BinaryTree<T>::Level_Traversal(void(*Visit)(T &x), BTNode<T> *t)
{
	BTNode<T> *a;
	Visit(t -> element);
	if(t -> lChild) s.EnQueue(t -> lChild);
	if(t -> rChild) s.EnQueue(t -> rChild);
	while(s.Front(a) == true) {
		if(a -> lChild) s.EnQueue(a -> lChild);
		if(a -> rChild) s.EnQueue(a -> rChild);
		Visit(a -> element);
		s.DeQueue();
	}
}
int main(int argc, char const *argv[])
{
	BinaryTree<char> t[100], a, b, tmp;
	int num = 0, high = 0;
	t[7].MakeTree('H', a, b);
	t[8].MakeTree('I', a, b);
	t[3].MakeTree('D', t[7], t[8]);
	t[4].MakeTree('E', a, b);
	t[5].MakeTree('F', a, b);
	t[6].MakeTree('G', a, b);
	t[1].MakeTree('B', t[3], t[4]);
	t[2].MakeTree('C', t[5], t[6]);
	t[0].MakeTree('A', t[1], t[2]);
	cout << "二叉树z的层次遍历结果:\n";
	t[0].PreOrder(Visit);
	cout << endl;
	tmp.root = tmp.Copy(t[0].root);
	cout << "tmp复制二叉树z后层次遍历结果:\n";
	tmp.PreOrder(Visit);
	cout << endl;
	t[0].Exchange(t[0].root);
	cout << "交换左右子树后二叉树z的层次遍历结果:\n";
	t[0].PreOrder(Visit);
	cout << endl;
	num = t[0].Num(t[0].root);
	cout << "二叉树z的叶子结点数为:\n" << num << endl;
	high = t[0].High(t[0].root);
	cout << "二叉树z的高度为:\n" << high << endl;
	t[0].Clear();
	return 0;
}

数据结构实验2(二叉链表实现二叉树的基本运算)

原文：http://blog.csdn.net/gkhack/article/details/50284713