2016年9月11日由Frank

二叉树类的实现

最近看数据结构看到二叉树的时候，自己实现了一下，同时写成了类，正好复习一下以前看C++的一些知识。代码如下。

// BiTNode.h
// 参照《c++大学教程》中P639页编写
// 模版结点BiTNode类的声明

#ifndef BITNODE_H
#define BITNODE_H

// 声明BiNTree类型
template<typename NODETYPE> class BiTree;

template<typename NODETYPE>
class BiTNode
{
	// 声明友元BiNTree类，使得BiTree类可以访问BiTNode类中的private成员
	friend class BiTree<NODETYPE>;

public:
	BiTNode(const NODETYPE &d) 
		: lchild(0), 
			data(d),
			rchild(0)
	{
	}

	NODETYPE getData() const
	{
		return data;
	}

private:
	BiTNode<NODETYPE> *lchild;
	NODETYPE data;
	BiTNode<NODETYPE> *rchild;
};

#endif

// BiTree.h
// 链表二叉树类模版的定义

#ifndef BITREE_H
#define BITREE_H

#include <iostream>
#include <iomanip>
#include "BiTNode.h"
#include <queue>
#include <stack>
using namespace std;

typedef int Status;

#define OK	1
#define ERROR	0
#define TRUE	1
#define FALSE	0

template<typename NODETYPE>
class BiTree
{
public:
	BiTree();

	void CreateBiTree();
	void DestroyBiTree();
	Status BiTreeEmpty();
	NODETYPE Root();

	int BiTreeDepth();
	int BiTreeDepthNonRecursion();

	void PreOrderTraverse();
	void PreOrderNonRecursion();
	void InOrderTraverse();
	void InOrderNonRecursion();
	void PostOrderTraverse();
	void PostOrderNonRecursion();
	void LevelOrderTraverse();

	void PrintLast();
	void PrintByDepth();

private:
	BiTNode<NODETYPE> *rootPtr;

	// utility function
	void visit(BiTNode<NODETYPE> *p);
	void CreateBiTreeHelper(BiTNode<NODETYPE> **T);
	void DestroyBiTreeHelper(BiTNode<NODETYPE> **T);
	int BiTreeDepthHelper(BiTNode<NODETYPE> *T);

	// 用helper函数的原因是对二叉树进行遍历要传入参数
	void PreOrderTraverseHelper(BiTNode<NODETYPE> *T);
	void InOrderTraverseHelper(BiTNode<NODETYPE> *T);
	void PostOrderTraverseHelper(BiTNode<NODETYPE> *T);
};

template<typename NODETYPE>
BiTree<NODETYPE>::BiTree()
{
	rootPtr = 0;
}

template<typename NODETYPE>
Status BiTree<NODETYPE>::BiTreeEmpty()
{
	if (rootPtr)
		return FALSE;
	else
		return TRUE;
}

template<typename NODETYPE>
void BiTree<NODETYPE>::CreateBiTree()
{
	CreateBiTreeHelper(&rootPtr);
}

// 按前序输入二叉树中结点的值（一个字符）
// #表示空树，构造二叉链表表示二叉树T。
template<typename NODETYPE>
void BiTree<NODETYPE>::CreateBiTreeHelper(BiTNode<NODETYPE> **T)
{
	NODETYPE val;

	cin >> val;

	if (val == '#')
		*T = NULL;
	else
	{
		*T = new BiTNode<NODETYPE>(val);
		CreateBiTreeHelper(&(*T)->lchild);
		CreateBiTreeHelper(&(*T)->rchild);
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::DestroyBiTree()
{
	DestroyBiTreeHelper(&rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::DestroyBiTreeHelper(BiTNode<NODETYPE> **T)
{
	if (*T)
	{
		if ((*T)->lchild)
			DestroyBiTreeHelper(&(*T)->lchild);
		if ((*T)->rchild)
			DestroyBiTreeHelper(&(*T)->rchild);
		free(*T);
		*T = NULL;
	}
}

template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepth()
{
	return BiTreeDepthHelper(rootPtr);
}

template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepthHelper(BiTNode<NODETYPE> *T)
{
	int i, j;

	if (!T)
		return 0;

	if (T->lchild)
		i = BiTreeDepthHelper(T->lchild);
	else 
		i = 0;
	if (T->rchild)
		j = BiTreeDepthHelper(T->rchild);
	else
		j = 0;

	return i > j ? i+1 : j+1;
}

template<typename NODETYPE>
NODETYPE BiTree<NODETYPE>::Root()
{
	if (!rootPtr)
		return ' ';
	else
		return rootPtr->data;
}

// 借用层次遍历的思想，实现非递归形式求出二叉树深度
template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepthNonRecursion()
{
	if (!rootPtr)
		return 0;

	BiTNode<NODETYPE> *p; // 工作指针，每次记录从队列队首弹出的结点
	BiTNode<NODETYPE> *back; // 记录每层二叉树的最右边的结点。此结点在每次遍历一层之后的队列队尾
	int level = 0; // 层数，初始值为0
	queue<BiTNode<NODETYPE> *> Q;

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back) // 如果p == 每层的最右边的结点，则层数+1，同时重新赋值队尾结点
		{
			level++;
			if (!Q.empty()) // 如果队列为空，则下一步的操作出错。主要用于防止最后一个结点弹出队列之后的那次操作
				back = Q.back();
		}
	}

	return level;
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderTraverse()
{
	PreOrderTraverseHelper(rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
	if (!T)
		return;

	visit(T);
	PreOrderTraverseHelper(T->lchild);
	PreOrderTraverseHelper(T->rchild);
}

// 前序遍历非递归形式
template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderNonRecursion()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	stack<BiTNode<NODETYPE> *> S; // 借助栈实现非递归的前序遍历

	p = rootPtr;
	while (p || !S.empty())
	{
		while (p) 
		{
			visit(p); // 在每次入栈之前进行访问
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			S.pop();
			p = p->rchild;
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderTraverse()
{
	InOrderTraverseHelper(rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
	if (!T)
		return;

	InOrderTraverseHelper(T->lchild);
	visit(T);
	InOrderTraverseHelper(T->rchild);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderNonRecursion()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	stack<BiTNode<NODETYPE> *> S;

	p = rootPtr;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			S.pop();
			visit(p); // 在每次出栈之时进行访问
			p = p->rchild;
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderTraverse()
{
	PostOrderTraverseHelper(rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
	if (!T)
		return;

	PostOrderTraverseHelper(T->lchild);
	PostOrderTraverseHelper(T->rchild);
	visit(T);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderNonRecursion()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *r; // 用于记录栈中弹出的结点的右子树是否访问过
	stack<BiTNode<NODETYPE> *> S;

	p = rootPtr;
	r = NULL;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			if (p->rchild && p->rchild != r) // 此结点的右子树尚未入栈
			{
				p = p->rchild;
				S.push(p);
				p = p->lchild;
			}
			else
			{
				S.pop();
				visit(p); // 每次出栈时访问结点
				r = p;
				p = NULL;
			}
		}
	}

}

template<typename NODETYPE>
void BiTree<NODETYPE>::LevelOrderTraverse()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针
	queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p);

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PrintLast()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针
	queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			visit(p);
			if (!Q.empty())
				back = Q.back(); // 更新back指针的位置
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PrintByDepth()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针
	queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p);

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			cout << endl;
			if (!Q.empty())
				back = Q.back(); // 更新back指针的位置
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::visit(BiTNode<NODETYPE> *p)
{
	cout << left << setw(5) << p->data;
}

#endif

为了省事，main函数有些代码直接使用了前面一篇文章里面c的代码。

// main.h
#include <iostream>
#include "BiTree.h"
using namespace std;

int main()
{
	int i;
	BiTree<char> T;
	char e1;
	
	//StrAssign(str,"ABDH#K###E##CFI###G#J##");

	T.CreateBiTree();

	printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度: %d\n",T.BiTreeEmpty(), T.BiTreeDepthNonRecursion());
	e1 = T.Root();
	printf("二叉树的根为: %c\n",e1);

	printf("\n前序遍历二叉树:\n");
	//T.PreOrderTraverse();
	T.PreOrderNonRecursion();

	printf("\n中序遍历二叉树:\n");
	T.InOrderTraverse();
	//T.InOrderNonRecursion();

	printf("\n后序遍历二叉树:\n");
	//T.PostOrderTraverse();
	T.PostOrderNonRecursion();

	printf("\n层次遍历二叉树:\n");
	T.LevelOrderTraverse();

	printf("\n每行二叉树的最右边的结点为:\n");
	T.PrintLast();

	printf("\n按层次输出每行的结点:\n");
	T.PrintByDepth();

	T.DestroyBiTree();
	printf("\n清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",T.BiTreeEmpty(),T.BiTreeDepth());
	i = T.Root();
	if(!i)
		printf("树空，无根\n");

	getchar();
	getchar();
	return 0;
}

写这个代码的时候，感觉自己计算机编程入门了——之前写代码主要都是照着书写，出错了更多都是照着书查找错误。写这个二叉树类的时候有个地方指针出错了，自己设断点改错，改了很久。所以入门的一些经验在下面一篇文章里面谈谈吧。

参考资料：
1.《大话数据结构》
2.《C++大学教程（第七版）》

“二叉树类的实现”的一个回复

Pingback：计算机入门的一点经验和对迷茫的一些分析 – Frank

发表评论取消回复