二叉树类型设计说明
一、引言
1.背景
二叉树是树形结构的一个重要类型，许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，因此，二叉树显得特别重要。
2.摘要
这是一个简单的二叉树类型及在此类型上的一些常用操作。该二叉树采用的是二叉链表的存储结构，C++实现。
3.工作条件 /
限制
由于时间仓促，外加人力有限，本二叉树类型的实现难免存在一些不足。可能会存在用户想要的接口没有定义的情况，也可能会存在是一些操作的实现效率低下等等……就此，可能会在以后的时间里进行类型的再设计与优化。
二、总体设计
１.概要设计
这是一个二叉树的类模板，用户可以根据自己的需要设置二叉树的节点类型,以下分为两部分说明：
⑴二叉树节点类型的功能规格说明
// 根据类型T设置节点的存储数据类型
template <class T>
class BinaryTreeNode
{
public:// 用户接口说明
// 缺省的构造器
BinaryTreeNode(void);
// 带参数的构造器
BinaryTreeNode(const T &data,
// 该节点保存的数据
BinaryTreeNode *leftChild = NULL, // 左指针域
BinaryTreeNode *rightChild = NULL); // 右指针域
// 返回该节点的数据
T& GetData(void);
// 返回该节点的左孩子指针
BinaryTreeNode<T>* GetLeftChild(void);
// 返回该节点的右孩子指针
BinaryTreeNode<T>* GetRightChild(void);
// 设置该节点的数据
void SetData(const T &data);
// 设置该节点的左孩子指针域
void SetLeftChild(BinaryTreeNode<T> *leftChild);
// 设置该节点的右孩子指针域
void SetRightChild(BinaryTreeNode<T> *rightChild);
private: // 私有方法及数据说明
T m_data;
// 存储该节点的数据
BinaryTreeNode<T> *m_leftChild; // 存储该节点的左孩子指针
BinaryTreeNode<T> *m_rightChild;// 存储该节点的右孩子指针
};
⑵整体二叉树类型的功能规格说明
// 根据类型T设置节点的存储数据类型
template<class T>
class BinaryTree
{
public:// 用户接口说明
// 缺省的构造器，初始化该树
BinaryTree(void);
// 析构器，释放资源给OS
virtual ~BinaryTree(void);
// 判断树是否是空树
bool IsEmpty(void)
const;
// 判断一个节点是否是左孩子
bool IsLeftChild(BinaryTreeNode<T> *p);
// 判断一个节点是否是右孩子
bool IsRightChild(BinaryTreeNode<T> *p);
// 取得整棵树的树根
BinaryTreeNode<T>* GetRoot(void);
// 取得一个节点的父亲节点指针
BinaryTreeNode<T>* GetParent(BinaryTreeNode<T> *p);
// 取得一个节点的左子树根指针
BinaryTreeNode<T>* LeftChild(BinaryTreeNode<T> *root) const;
// 取得一个节点的右子树根指针
BinaryTreeNode<T>* RightChild(BinaryTreeNode<T> *root) const;
// 取得一个节点的左兄弟指针
BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T> *leftChild);
// 取得一个节点的右兄弟指针
BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T> *rightChild);
// 返回一个节点的数据
T Retrieve(BinaryTreeNode<T> *p)
const;
// 设置一个节点的数据
void Assign(BinaryTreeNode<T> *p, const T &d) const;
// 插入右孩子到当前节点下
void InsertRightChild(BinaryTreeNode<T> *p, const T &d) const;
// 插入左孩子到当前节点下
void InsertLeftChild(BinaryTreeNode<T> *p, const T &d) const;
// 删除当前节点的右孩子
void DeleteRightChild(BinaryTreeNode<T> *p);
// 删除当前节点的左孩子
void DeleteLeftChild(BinaryTreeNode<T> *p);
// 先序遍历整棵树
virtual void PreOrderTraverse(void)
const;
// 中序遍历整棵树
virtual void InOrderTraverse(void)
const;
// 后序遍历整棵树
virtual void PostOrderTraverse(void)
const;
// 按层遍历整棵树
virtual void LevelOrderTraverse(void)
const;
protected:// 保护的数据或方法
// 用于存储树根
BinaryTreeNode<T> *m_root;
// 根据给定数据创建树的根节点
void CreateRoot(const T &data);
// 从一个节点开始先序遍历其子树
virtual void PreOrder(BinaryTreeNode<T> *root)
const;
// 从一个节点开始中序遍历其子树
virtual void InOrder(BinaryTreeNode<T> *root)
const;
// 从一个节点开始后序遍历其子树
virtual void PostOrder(BinaryTreeNode<T> *root)
const;
// 从一个节点开始按层遍历其子树
virtual void LevelOrder(BinaryTreeNode<T> *root)const;
// 取得给定节点的父亲节点指针
BinaryTreeNode<T>* Parent(BinaryTreeNode<T> *root,
BinaryTreeNode<T> *p);
// 从给定节点开始销毁其子树
void Destroy(BinaryTreeNode<T> *p);
};
２.详细设计
⑴二叉树节点类型具体实现说明
template<class T> // 以下函数均基于类型T
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：BinaryTreeNode
// 功能：缺省的构造函数，设置该节点的左右孩子指针域均为空
// 输入参数：void
// 输出参数：无
BinaryTreeNode<T>::BinaryTreeNode(void)
{
m_leftChild = m_rightChild = NULL;
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：BinaryTreeNode
// 功能：带参数的构造函数，根据参数设置该节点的左右孩子指针域
// 输入参数：const T &data：用于初始化该节点数据域
//
BinaryTreeNode *leftChild：用于初始化该节点左孩子指针
//
BinaryTreeNode *rightChild：用于初始化该节点左孩子指针
// 输出参数：无
BinaryTreeNode<T>::BinaryTreeNode(const T &data,
BinaryTreeNode *leftChild,
BinaryTreeNode *rightChild)
{
m_data = data;
m_leftChild = leftChild;
m_rightChild = rightChild;
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：GetData
// 功能：返回该节点的数据
// 输入参数：void
// 输出参数：T&：该节点的数据
T& BinaryTreeNode<T>::GetData(void)
{
return m_data;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：GetLeftChild
// 功能：返回该节点的左孩子指针
// 输入参数：void
// 输出参数：BinaryTreeNode<T>*：该节点的左孩子指针
BinaryTreeNode<T>* BinaryTreeNode<T>::GetLeftChild(void)
{
return m_leftChild;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：GetRightChild
// 功能：返回该节点的右孩子指针
// 输入参数：void
// 输出参数：BinaryTreeNode<T>*：该节点的右孩子指针
BinaryTreeNode<T>* BinaryTreeNode<T>::GetRightChild(void)
{
return m_rightChild;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：SetData
// 功能：设置该节点的数据域
// 输入参数：const T &data：根据此参数设置数据域
// 输出参数：void
void BinaryTreeNode<T>::SetData(const T &data)
{
m_data = data;
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：SetLeftChild
// 功能：设置该节点的左孩子指针域
// 输入参数：BinaryTreeNode<T> *leftChild：根据此参数设置左孩子指针域
// 输出参数：void
void BinaryTreeNode<T>::SetLeftChild(BinaryTreeNode<T> *leftChild)
{
m_leftChild = leftChild;
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：SetRightChild
// 功能：设置该节点的右孩子指针域
// 输入参数：BinaryTreeNode<T> *RightChild：根据此参数设置右孩子指针域
// 输出参数：void
void BinaryTreeNode<T>::SetRightChild(BinaryTreeNode<T> *rightChild)
{
m_rightChild = rightChild;
return;
}
⑵整体二叉树类型具体实现说明
template<class T> // 以下函数均基于类型T
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：BinaryTree
// 功能：构造器，初始化整棵树为空树
// 输入参数：void
// 输出参数：无
BinaryTree<T>::BinaryTree(void)
{
m_root = NULL;
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：~BinaryTree
// 功能：析构器，基于函数Destory销毁整棵树，释放资源给OS
// 输入参数：void
// 输出参数：无
BinaryTree<T>::~BinaryTree(void)
{
Destroy(m_root);
m_root = NULL;
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：IsEmpty
// 功能：判断这棵树是否是空树
// 输入参数：void
// 输出参数：bool：如果是则返回true，反之返回false
bool BinaryTree<T>::IsEmpty(void)
const
{
return m_root == NULL ? true:false;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：IsLeftChild
// 功能：判断该节点p是否为左孩子
// 输入参数：BinaryTreeNode<T> *p：给定p指向树中的一个节点
// 注意：树根不能作为输入参数
// 输出参数：bool：为真说明是左孩子，反之是右孩子
bool BinaryTree<T>::IsLeftChild(BinaryTreeNode<T> *p)
{
return p == GetParent(p)->GetLeftChild() ? true:false;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：IsRightChild
// 功能：判断该节点p是否为右左孩子
// 输入参数：BinaryTreeNode<T> *p：给定p指向树中的一个节点
// 注意：树根不能作为输入参数
// 输出参数：bool：为真说明是右孩子，反之是左孩子
bool BinaryTree<T>::IsRightChild(BinaryTreeNode<T> *p)
{
return p == GetParent(p)->GetRightChild() ? true:false;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：Destroy
// 功能：销毁给定树，释放资源
// 输入参数：BinaryTreeNode<T> *p：给定p指向树中的一个节点
// 输出参数：void
void BinaryTree<T>::Destroy(BinaryTreeNode<T> *p)\
{
if (NULL != p)
{
Destroy(p->GetLeftChild());
Destroy(p->GetRightChild());
delete p;
}
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：GetRoot
// 功能：取得整棵树的根节点指针
// 输入参数：void
// 输出参数：BinaryTreeNode<T>*：整棵树的树根指针
BinaryTreeNode<T>* BinaryTree<T>::GetRoot(void)
{
return m_root;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：GetParent
// 功能：基于函数Parent取得给定节点的父亲指针
// 输入参数：BinaryTreeNode<T> *p：给定p指向树中的一个节点
// 输出参数：BinaryTreeNode<T>*：指向该节点父亲的指针
BinaryTreeNode<T>* BinaryTree<T>::GetParent(BinaryTreeNode<T> *p)
{
return Parent(m_root, p);
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：Parent
// 功能：取得给定节点的父亲指针
// 输入参数：BinaryTreeNode<T> *root：从root指向的节点开始寻找
BinaryTreeNode<T> *p：给定p指向树中的一个节点
// 输出参数：BinaryTreeNode<T>*：指向该节点父亲的指针
BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T> *root,
BinaryTreeNode<T> *p)
{
BinaryTreeNode<T> *q;
if (NULL == root)
{
return NULL;
}
if ((p == root->GetLeftChild()) || (p == root->GetRightChild()))
{
return root;
}
if (NULL != (q = Parent(root->GetLeftChild(), p)))
{
return q;
}
else
{
return Parent(root->GetRightChild(), p);
}
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：RightSibling
// 功能：基于Parent函数取得给定节点的右兄弟的指针
// 注意：如果该节点就是右孩子，那么函数将返回空值
// 输入参数：BinaryTreeNode<T> *p：给定p指向树中的一个节点
// 输出参数：BinaryTreeNode<T>*：指向该节点右兄弟的指针或空值
BinaryTreeNode<T>* BinaryTree<T>::RightSibling(BinaryTreeNode<T> *p)
{
BinaryTreeNode<T> *q;
q = Parent(m_root, p);
if ((NULL == q) || (p == q->GetRightChild()))
{
return NULL;
}
else
{
return q->GetRightChild();
}
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：LeftSibling
// 功能：基于Parent函数取得给定节点的左兄弟的指针
// 注意：如果该节点就是左孩子，那么函数将返回空值
// 输入参数：BinaryTreeNode<T> *p：给定p指向树中的一个节点
// 输出参数：BinaryTreeNode<T>*：指向该节点左兄弟的指针或空值
BinaryTreeNode<T>* BinaryTree<T>::LeftSibling(BinaryTreeNode<T> *p)
{
BinaryTreeNode<T> *q;
q = Parent(m_root, p);
if ((NULL == q) || (p == q->GetLeftChild()))
{
return NULL;
}
else
{
return q->GetLeftChild();
}
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：InOrder
// 功能：从给定节点开始先序遍历其子树
// 注意：使用的时候请根据数据类型T适当修改输出方式
// 输入参数：BinaryTreeNode<T> *root：给定root指向树中的一个节点
// 输出参数：void
void BinaryTree<T>::InOrder(BinaryTreeNode<T> *root)
const
{
if (NULL != root)
{
InOrder(root->GetLeftChild());
//cout << root->GetData();
// NOTE!
InOrder(root->GetRightChild());
}
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：PostOrder
// 功能：从给定节点开始后序遍历其子树
// 注意：使用的时候请根据数据类型T适当修改输出方式
// 输入参数：BinaryTreeNode<T> *root：给定root指向树中的一个节点
// 输出参数：void
void BinaryTree<T>::PostOrder(BinaryTreeNode<T> *root)
const
{
if (NULL != root)
{
PostOrder(root->GetLeftChild());
PostOrder(root->GetRightChild());
//cout << root->GetData();
// NOTE!
}
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：PreOrder
// 功能：从给定节点开始先序遍历其子树
// 注意：使用的时候请根据数据类型T适当修改输出方式
// 输入参数：BinaryTreeNode<T> *root：给定root指向树中的一个节点
// 输出参数：void
void BinaryTree<T>::PreOrder(BinaryTreeNode<T> *root)
const
{
if (NULL != root)
{
//cout << root->GetData();
// NOTE!
PreOrder(root->GetLeftChild());
PreOrder(root->GetRightChild());
}
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：LevelOrder
// 功能：从给定节点开始按层遍历其子树（需要一个队列的支持）
// 注意：使用的时候请根据数据类型T适当修改输出方式
// 输入参数：BinaryTreeNode<T> *root：给定root指向树中的一个节点
// 输出参数：void
void BinaryTree<T>::LevelOrder(BinaryTreeNode<T> *root) const
{
queue<BinaryTreeNode<T> *> q;
if (NULL != root)
{
q.push(root);
}
while (!q.empty())
{
root = q.front(), q.pop();
//cout << p->GetData();
// NOTE!
if (root->GetLeftChild())
{
q.push(root->GetLeftChild());
}
if (root->GetRightChild())
{
q.push(root->GetRightChild());
}
}
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：LevelOrderTraverse
// 功能：基于函数LevelOrder按层遍历遍历整棵二叉树
// 输入参数：void
// 输出参数：void
void BinaryTree<T>::LevelOrderTraverse(void)
const
{
LevelOrder(m_root);
return;
}
//＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
// 函数名：PostOrderTraverse
// 功能：基于函数PostOrder后序遍历遍历整棵二叉树
// 输入参数：void
// 输出参数：void
void BinaryTree<T>::PostOrderTraverse(void)
const
{
PostOrder(m_root);
return;
