#ifndef BINARYTREE_H
#define BINARYTREE_H
#include"bintreenode.h"
#include<QDebug>
#include<QString>
#include<QQueue>
#include<functional>
template<class T>
class BinaryTree
{
protected:
BinTreeNode<T> *root; //根节点
public:
int height; //树的高度
public:
BinaryTree();
BinaryTree(const T &e,int depth=0); //缺省深度为0
virtual ~BinaryTree();
BinTreeNode<T>* getRoot();
void destroyNode(BinTreeNode<T> *node);
void preorderTravel(BinTreeNode<T> *node,void (*visit)(T &)); //前序遍历
void levelTravel(void (*visit)(BinTreeNode<T> *node)); //层次遍历
BinTreeNode<T>* insertLeftChild(BinTreeNode<T> *cur,const T &e);
BinTreeNode<T>* insertRightChild(BinTreeNode<T> *cur,const T &e);
bool isCompleteTree();
//可用指向类函数成员的指针作为参数
void levelTreeTravel(std::function<void(BinTreeNode<T> *node)> visit); //层次遍历
void postOrderTravel(BinTreeNode<T> *node,std::function<void(BinTreeNode<T> *)> visit); //后序遍历
};
template<class T>
BinTreeNode<T>* BinaryTree<T>::insertLeftChild(BinTreeNode<T> *cur, const T &e)
{
int depth=cur->depth+1;//子结点总比父结点深度多1
if(depth>this->height)
{
this->height=depth;
}
//语句的精炼与可读性
// BinTreeNode<T> *lChild=new BinTreeNode<T>(e,depth,cur);
// cur->leftChild=lChild;
// return cur->leftChild;
return cur->leftChild=new BinTreeNode<T>(e,depth,cur);
}
template<class T>
BinTreeNode<T> *BinaryTree<T>::insertRightChild(BinTreeNode<T> *cur, const T &e)
{
int depth=cur->depth+1;//子结点比父结点深度多1
if(depth>this->height)
{
this->height=depth;
}
return cur->rightChild=new BinTreeNode<T>(e,depth,cur);
}
//判断是否为完全树
/*中层遍历:从上到下，从左到右
*
*/
template<class T>
bool BinaryTree<T>::isCompleteTree()
{
QQueue<BinTreeNode<T>*> queue; //辅助队列
if(root)
{
queue.enqueue(root);
}
else
{
return true;
}
BinTreeNode<T>* cur=NULL;
while (queue.isEmpty()==false)
{
cur=queue.dequeue();
//当前结点具有两个孩子结点
if(cur->leftChild && cur->rightChild)
{
queue.enqueue(cur->leftChild);
queue.enqueue(cur->rightChild);
continue;
}
//当前结点没有孩子结点
else if(cur->leftChild==NULL && cur->rightChild==NULL)
{
continue;
}
else //有一个孩子结点
{
return false;
}
}
return true;
}
template<class T>
BinaryTree<T>::~BinaryTree()
{
destroyNode(root);
}
//postorder
template<class T>
void BinaryTree<T>::destroyNode(BinTreeNode<T> *node)
{
static int i=0;
if(node)
{
destroyNode(node->leftChild);
destroyNode(node->rightChild);
delete node;
qDebug()<<QString::number(i++);
node=NULL;
}
}
//先序遍历
template<class T>
void BinaryTree<T>::preorderTravel(BinTreeNode<T> *node, void (*visit)(T &))
{
if(node)
{
(*visit)(node->data);
preorderTravel(node->leftChild,visit);
preorderTravel(node->rightChild,visit);
}
}
template<class T>
void BinaryTree<T>::levelTravel(void (*visit)(BinTreeNode<T> *))
{
QQueue<BinTreeNode<T>*> queue; //辅助队列
if(root)
{
queue.enqueue(root);
}
else
{
return;
}
BinTreeNode<T>* cur=NULL;
while (queue.isEmpty()==false)
{
cur=queue.dequeue();
visit(cur);
if(cur->leftChild)
{
queue.enqueue(cur->leftChild);
}
if(cur->rightChild)
{
queue.enqueue(cur->rightChild);
}
}
}
template<class T>
void BinaryTree<T>::levelTreeTravel(std::function<void(BinTreeNode<T> *node)> visit)
{
QQueue<BinTreeNode<T>*> queue; //辅助队列
if(root)
{
queue.enqueue(root);
}
else
{
return;
}
BinTreeNode<T>* cur=NULL;
while (queue.isEmpty()==false)
{
cur=queue.dequeue();
visit(cur);
if(cur->leftChild)
{
queue.enqueue(cur->leftChild);
}
if(cur->rightChild)
{
queue.enqueue(cur->rightChild);
}
}
}
template<class T>
void BinaryTree<T>::postOrderTravel(BinTreeNode<T> *node, std::function<void (BinTreeNode<T> *)> visit)
{
if(node)
{
postOrderTravel(node->leftChild,visit);
postOrderTravel(node->rightChild,visit);
visit(node);
}
}
#endif // BINARYTREE_H
#include"binarytree_implement.h"
