二叉树按照数据结构类型来划分属于树结构，在树结构中他又是比较简单而且具有理论研究的意义的一种数据结构。有很多树形结构都是基于二叉树的变种，所以对二叉树的学习与了解是很有必要的。根据笔者的经验，在学习数据结构的过程中要深刻的体会逻辑接口与物理存储实现的区别与联系。比如在之前的博客中有讲到栈和队列的实现，栈和队列都有基于数组存储方式的实现和基于链表存储形式的实现。所谓的逻辑接口就是这个数据结构具备哪些特点与性质，具备哪些抽象的能力，比如栈是一个后进者先出的特点，普通队列是先进者先出特点。可是这些特点与性质在具体的实现的时候可是各有不同了，如果是基于数组存储的栈，那内部维护的就是一个连续的内存空间，所有的操作仅仅是作用在数组的索引下标上。如果是基于链式存储的栈，那么内部就是维护了一个单链表。
二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点后，每个顶点定义了唯一的根结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。
二叉树的存储结构一般采用二叉链表，树中每一个结点都有一个数据域data还有两个分别用于指向该节点的左右儿子结点的指针域，通过这两个指针域建立了上下层结点的关系，这样就可以为以后的遍历奠定基础了。
结点类的类声明：
#pragma once
#include<iostream>
using namespace std;
template<class T>
class BT_Node//二叉树结点类
{
public:
T data;//结点类 数据域
BT_Node<T> *leftchild;//用于指向左孩子的指针域
BT_Node<T> *rightchild;//用于指向右孩子的指针域
public:
BT_Node()//无参 构造函数用于单一new结点开辟纯空间
{
leftchild = NULL;
rightchild = NULL;//新开辟的结点空间左右孩子指针域全赋为空 不管数据域
}
BT_Node(T da)//有参构造函数 用于深复制等需要根据已有数据开辟空间的
{
data = da;
leftchild = NULL;
rightchild = NULL;
}
~BT_Node()//析构函数template<class T>
void BinTree<T>::CreateBinTree_(ifstream& in,BT_Node<T> * &subTree) //文件流输入重载 适用于从文件中读进内存
{
T item;
if(!in.eof())//不到文件的末尾 执行
{
in>>item;
if(item != endflag_value)
{
subTree = new BT_Node<T>(item);//调用含参 构造函数 指针域为NULL
if(subTree == NULL)
{
cout<<"内存分配错误!"<<endl;
exit(1);//强制结束进程
}
CreateBinTree_(in,subTree->leftchild);//递归调用 建立当前结点为根结点的左右子树
CreateBinTree_(in,subTree->rightchild);
}
else
subTree = NULL;//把当前参数中的指针置为NULL 封闭子树指针域
}
}
{//析构什么也不做}};
文中的二叉树采用的是前序递归的形式创建的，在递归的过程中要有一个出口，做法是：当某个结点的指针域均为NULL时就说明该节点是叶子结点了，就不再往下递归了。
下面是源码，已经注释的很清晰了，由于遍历和创建树，以及求结点数目，求高度等函数都是递归实现的，所以实现了两个版本，一个是内部递归使用的私有的函数名后面有下划线，对外的接口是无参的，里面直接调用的是私有函数。还有关于模板函数的友元形式的声明，在VS系列编译器中必须加Template<class T>才行。
#pragma once
#include"BinTreeNode.h"
#include<queue>
#include <algorithm>
#include<iostream>
#include<fstream>//文件流 重载输入
using namespace std;
template<class T>
class BinTree
{
protected:
BT_Node<T> *root;//一个二叉树的根结点 被封装
T endflag_value;//二叉树的输入结束标志
protected:
//bool Insert_(BT_Node<T> *subTree,const T& x);//插入 参数(sunTree 为子树的意思)
void Destroy_(BT_Node<T> *subTree);//删除
BT_Node<T> * Copy_(BT_Node<T> *orignNode);//复制 返回根结点指针参数(复制 结点)
BT_Node<T> * Find_(BT_Node<T> *subTree,const T& x)const;//常函数 不允许改动类中的数据 查找
int Height_(BT_Node<T> *subTree);//求一棵二叉树的高度或是深度
int Size_(BT_Node<T> *subTree);//求一棵二叉树的结点个数
BT_Node<T> * Parent_(BT_Node<T> *subTree,BT_Node<T> *current);//寻找父结点 参数(子树 当前需要被找的结点)
void PreOrder_(BT_Node<T> *subTree,void(* )(BT_Node<T> *));//前序遍历 后一个参数是函数指针
void InOrder_(BT_Node<T> *subTree,void(* )(BT_Node<T> *));//中序遍历
void PostOrder_(BT_Node<T> *subTree,void(* )(BT_Node<T> *));//后序遍历
void Output_(ostream& out,BT_Node<T> *subTree);//输出一棵二叉树
void CreateBinTree_(ifstream& in,BT_Node<T> * &subTree);//私有函数后带有_标志，建树被封装
void CreateBinTree_(istream& in,BT_Node<T> * &subTree);//私有函数后带有_标志，建树被封装
public:
BinTree();//无参构造函数
BinTree(T value);//带参 初始化输入结束标志
BinTree(BinTree<T> &Tree);//深复制函数
~BinTree();//析构函数
bool isEmpty();//判树空
BT_Node<T> * & Get_Root();//返回树的根结点
BT_Node<T> * Get_Parent(BT_Node<T> *current);//返回父结点 用于对外接口 只接受一个指针参数
BT_Node<T> * Get_Leftchild(BT_Node<T> *subTree);//返回该结点的左孩子
BT_Node<T> * Get_Rightchild(BT_Node<T> *subTree);//返回该结点的右孩子
int Get_Height();//返回树的高度或是深度 对外无参接口
int Get_Size();//返回树的结点个数 对外无参接口
void PreOrder(void (* visit)(BT_Node<T> *));//前序遍历 无参对外接口内部使用根结点封装
void InOrder(void (* visit)(BT_Node<T> *));//中序遍历
void PostOrder(void (* visit)(BT_Node<T> *));//后序遍历
void LevelOrder(void (* )(BT_Node<T> *));//按层遍历
void Destroy();//删除 对外无参接口 同析构一样作用
//int Insert(const T &item);//插入新元素 在二叉树的下一个合法结点位置处
BT_Node<T> * Find(const T &item)const;//搜索
template<class T> friend ifstream& operator>> (ifstream& input,BinTree<T> &Tree);//友元 文件流重载 输入
template<class T> friend istream& operator>> (istream& input,BinTree<T> &Tree);//友元，标准输入流重载
template<class T> friend ostream& operator<< (ostream& output,BinTree<T> &Tree);//输出重载
void operator= (BinTree<T> &BT);
};
/****************** 私有函数域 ******************/
template<class T>
void BinTree<T>::Destroy_(BT_Node<T> *subTree)//删除
{
if(subTree != NULL)//当前指针不为空 说明有子树
{
Destroy_(subTree->leftchild);//则递归下去
Destroy_(subTree->rightchild);
delete subTree;//最后删除
}
//当前指针为NULL时 会不执行语句直接返回上一层
}
template<class T>
BT_Node<T> * BinTree<T>::Find_(BT_Node<T> *subTree,const T& x)const //查找
{
if(subTree == NULL)
return NULL;
if(subTree->data == x)//找到
{
return subTree;
}
BT_Node<T> *temp;
if((temp = Find_(subTree->leftchild,x)) != NULL)//若当前不相等 则递归下去
return temp;
else
return Find_(subTree->rightchild,x);
}
template<class T>
BT_Node<T> * BinTree<T>::Copy_(BT_Node<T> *orignNode)//复制 返回根结点指针参数(复制 结点)
{
if(orignNode == NULL)
return NULL;//如果当前指针为空则不执行后面的复制语句
BT_Node<T> *temp = new BT_Node<T>;//创立一个新的结点
temp->data = orignNode->data;//复制数据域
temp->leftchild = Copy_(orignNode->leftchild);
temp->rightchild = Copy_(orignNode->rightchild);
return temp;//最后的效果是 返回根结点指针
}
template<class T>
void BinTree<T>::operator= (BinTree<T> &BT)
{
root = Copy_(BT.root);
}
template<class T>
int BinTree<T>::Height_(BT_Node<T> *subTree)//求一棵二叉树的高度或是深度
{
if(subTree == NULL)
return 0;//如果递归到底 则返回0到上一层
else
{
int left_H = Height_(subTree->leftchild);//当前指针不为NULL 递归下去
int right_H = Height_(subTree->rightchild);
return ( (left_H < right_H) ? (right_H + 1) : (left_H + 1) ); //左右子树的深度进行比较 返回较大值 并且加1
}
}
template<class T>
int BinTree<T>::Size_(BT_Node<T> *subTree)//求一棵二叉树的结点个数
{
if(subTree == NULL)
return 0;//递归到底 则返回0
else
{
return ( 1 + Size_(subTree->leftchild) + Size_(subTree->rightchild));
//否则一直计算下一个左右子树的结点树 +1 为统计核心
}
}
template<class T>
BT_Node<T> * BinTree<T>::Parent_(BT_Node<T> *subTree,BT_Node<T> *current)
{ //寻找父结点 参数(子树 当前需要被找的结点)
if(subTree == NULL)
return NULL;
if(subTree->leftchild == current || subTree->rightchild == current)//找到父结点
return subTree;//返回父结点
BT_Node<T> *temp;//临时存储指针变量
if( (temp = Parent_(subTree->leftchild,current)) != NULL)
return temp;//递归左子树
else
return Parent_(subTree->rightchild,current);//递归右子树
}
template<class T>
void BinTree<T>::PreOrder_(BT_Node<T> *subTree,void (* )(BT_Node<T> *))//前序遍历
{
if(subTree != NULL)//当前指针不为空时指向一下语句
{
visit(subTree);//对当前指针指向的对象的任意操作
PreOrder_(subTree->leftchild,visit);//递归 左子树
PreOrder_(subTree->rightchild,visit);//递归右子树
}
//当前指针为空则直接不执行 返回上一层
}
template<class T>
void BinTree<T>::InOrder_(BT_Node<T> *subTree,void (* )(BT_Node<T> *))//中序遍历
{
if(subTree != NULL)
{
InOrder_(subTree->leftchild,visit);
visit(subTree);
InOrder_(subTree->rightchild,visit);
}
}
template<class T>
void BinTree<T>::PostOrder_(BT_Node<T> *subTree,void (* )(BT_Node<T> *))//后序遍历
{
if(subTree != NULL)
{
PostOrder_(subTree->leftchild,visit);
PostOrder_(subTree->rightchild,visit);
visit(subTree);
}
}
template<class T>
void BinTree<T>::CreateBinTree_(ifstream& in,BT_Node<T> * &subTree) //文件流输入重载 适用于从文件中读进内存
{
T item;
if(!in.eof())//不到文件的末尾 执行
{
in>>item;
if(item != endflag_value)
{
subTree = new BT_Node<T>(item);//调用含参 构造函数 指针域为NULL
if(subTree == NULL)
{
cout<<"内存分配错误!"<<endl;
exit(1);//强制结束进程
}
CreateBinTree_(in,subTree->leftchild);//递归调用 建立当前结点为根结点的左右子树
CreateBinTree_(in,subTree->rightchild);
}
else
subTree = NULL;//把当前参数中的指针置为NULL 封闭子树指针域
}
}
template<class T>
void BinTree<T>::CreateBinTree_(istream& in,BT_Node<T> * &subTree) //标准输入流重载 适用于从键盘上读进内存
{
T item;
in>>item;
if(item != endflag_value)
{
subTree = new BT_Node<T>(item);//调用含参 构造函数 指针域为NULL
if(subTree == NULL)
{
cout<<"内存分配错误!"<<endl;
exit(1);//强制结束进程
}
CreateBinTree_(in,subTree->leftchild);//递归调用 建立当前结点为根结点的左右子树
CreateBinTree_(in,subTree->rightchild);
}
if(item == endflag_value)
{
subTree = NULL;//把当前参数中的指针置为NULL 封闭子树指针域
}
}
template<class T>
void BinTree<T>::Output_(ostream& out,BT_Node<T> *subTree)//输出一棵二叉树 假定使用前序遍历方式
{
if(subTree != NULL)
{
out<<"#: "<<subTree->data<<endl;//输出当前指针指向的对象数据
Output_(out,subTree->leftchild);//递归左子树
Output_(out,subTree->rightchild);//递归右子树
}
}
/****************** 私有函数域 ******************/
/****************** 对外接口域 ******************/
template<class T>
BinTree<T>::BinTree()
{
root = NULL;//根结点被赋为空 不理会输入结束标志 一般用不到
}
template<class T>
BinTree<T>::BinTree(T value)
{
root = NULL;
endflag_value = value;
}
template<class T>
BinTree<T>::BinTree(BinTree<T> &Tree)//深复制函数
{
root = Copy_(Tree.root);//调用内部函数 生成一棵树后把根结点给当前对象的root
}
template<class T>
BinTree<T>::~BinTree()
{
Destroy_(root);//调用内部函数 释放一个树的所有的结点的内存
}
template<class T>
bool BinTree<T>::isEmpty()//判树空
{
return ((root == NULL) ? true : false);
}
template<class T>
BT_Node<T> * & BinTree<T>::Get_Root()//返回树的根结点
{
return root;
}
template<class T>
BT_Node<T> * BinTree<T>::Get_Parent(BT_Node<T> *current)//返回父结点 用于对外接口 只接受一个指针参数
{
return ( Parent_(root,current) );//调用内部函数 返回父结点指针
}
template<class T>
BT_Node<T> * BinTree<T>::Get_Leftchild(BT_Node<T> *subTree)//返回该结点的左孩子
{
if(subTree != NULL)//不为空 返回左孩子指针
return subTree->leftchild;
else
return NULL;//否则返回NULL
}
template<class T>
BT_Node<T> * BinTree<T>::Get_Rightchild(BT_Node<T> *subTree)//返回该结点的右孩子
{
if(subTree != NULL)
return subTree->rightchild;
else
return NULL;
}
template<class T>
int BinTree<T>::Get_Height()//返回树的高度或是深度 对外无参接口
{
return ( Height_(root) );//返回树的深度
}
template<class T>
int BinTree<T>::Get_Size()//返回树的结点个数 对外无参接口
{
return ( Size_(root) );//返回树结点数目
}
template<class T>
void BinTree<T>::Destroy()
{
Destroy_();
}
template<class T>
void BinTree<T>::PreOrder(void (* visit)(BT_Node<T> *))//前序遍历 无参对外接口内部使用根结点封装
{
PreOrder_(root,visit);//调用内部函数 前序遍历
}
template<class T>
void BinTree<T>::InOrder(void (* visit)(BT_Node<T> *))//中序遍历
{
InOrder_(root,visit);
}
template<class T>
void BinTree<T>::PostOrder(void (* visit)(BT_Node<T> *))//后序遍历
{
PostOrder_(root,visit);
}
template<class T>
void BinTree<T>::LevelOrder(void (* )(BT_Node<T> *))//按层遍历 要用到队列 逐层访问类问题
{
queue<BT_Node<T> *> qu; //STL中的队列 ,存储树结点指针
BT_Node<T> *current = root;
qu.push(current); //STL中的进队列就是PUSH
while(!qu.empty())
{
current = qu.front(); //获取对头元素的引用
visit(current);
qu.pop(); //删除对头元素 无返回值 ,所以要先返回引用再删除
if(current->leftchild != NULL)
qu.push(current->leftchild);
if(current->rightchild != NULL)
qu.push(current->rightchild);
}
}
template<class T>
BT_Node<T> * BinTree<T>::Find(const T &item) const//搜索
{
return Find_(root,item);
}
template<class T>
ifstream& operator>> (ifstream& input,BinTree<T> &Tree)//友元 重载 输入
{
Tree.CreateBinTree_(input,Tree.Get_Root());
return input;
}
template<class T>
istream& operator>> (istream& input,BinTree<T> &Tree)
{
Tree.CreateBinTree_(input,Tree.root);
return input;
}
template<class T>
ostream& operator<< (ostream& output,BinTree<T> &Tree)//这里的输出是一个全局函数，与类无关
{
Tree.Output_(output,Tree.Get_Root());
return output;
}