二叉树-排序二叉树
#include<iostream>
using namespace std;
/*
二叉树的节点
date : 数据
left :指向二叉树的左子树
right:指向二叉树的右子树
*/
template<class T>
struct Node{
T date;
Node<T>* left;
Node<T>* right;
Node():date(T()),left(NULL),right(NULL){}
};
template<class T>
class Btree
{
public:
Btree():root(NULL),count(NULL){}
Node<T>* & insert(Node<T> * &t,const T & e);
Node<T>* & sel(Node<T> * &t,const T& e);
voiddisplay(Node<T> * &t);
int hight(Node<T> * t);
boolclear(Node<T> * &t);
Node<T>* & getroot();
~Btree()
{
this->clear(this->root);
}
private:
Node<T>* root; //根节点指针
intcount;
};
/*
插入数据
中序遍历
*/
template<class T>
Node<T>* &Btree<T>::insert(Node<T> * &t,const T & e)
{
if(t==NULL)
{
Node<T>* p=new Node<T>;
p->date=e;
t=p;
count++;
returnt;
}
else
{
if(e<t->date) //如果e小于t节点的数据，递归往t的左子树插，反正向右子树
insert(t->left,e);
else
insert(t->right,e);
}
}
/*
查找元素 e
中序遍历
*/
template<class T>
Node<T>* &Btree<T>::sel(Node<T> * &t,const T& e)
{
if(t==NULL)
returnt;
else
{
if(e==t->date)
returnt;
else
{
if(e<t->date) //e小于t的数据，则向t的左子树查找，反之向t右子树查找
sel(t->left,e);
else
sel(t->right,e);
}
}
}
/*
先序遍历
*/
template<class T>
void Btree<T>::display(Node<T>* &t)
{
if(t==NULL)
return;
else
{
display(t->left);
cout<<t->date<<",";
display(t->right);
}
}
template<class T>
int Btree<T>::hight(Node<T> *t)
{
if(t==NULL)
return0;
else
{
intlh=hight(t->left);
intrh=hight(t->right);
return1+(lh>rh?lh:rh);
}
}
/*
清空二叉树
后序遍历
*/
template<class T>
bool Btree<T>::clear(Node<T>*& t)
{
if(t==NULL)
returnfalse;
else
{
clear(t->left);
clear(t->right);
delete t;
t=NULL;
returntrue;
}
}
template<class T>
Node<T> * &Btree<T>::getroot()
{
returnroot;
}
int main()
{
Btree<int>t;
t.insert(t.getroot(),50);
t.insert(t.getroot(),40);
t.insert(t.getroot(),45);
t.insert(t.getroot(),60);
t.display(t.getroot());
Node<int>* p;
p=t.sel(t.getroot(),45);
cout<<"查找树查找数值："<<p->date<<endl;
cout<<"二叉树的深度:"<<t.hight(t.getroot())<<endl;
t.clear(t.getroot());
return0;
}