#include <iostream>
#include <utility>
#include <string>
#include <cmath>
using namespace std;
template<typename T>
class btnode
{
public:
T key;
btnode * Lchild;
btnode * Rchild;
// function:make function
btnode( );
};
template<typename T>
btnode<T>::btnode()
{
key = -1;
Lchild = NULL;
Rchild = NULL;
};
template<typename T>
class binarytree
{
public:
// var:R id the root of the tree
btnode<T> * R;
// function:make function
binarytree();
// function:make tree
void _maketree(T * data,size_t s);
// function:insert key into tree
void _insert(btnode<T> * *bt,T d);
// function:visit node p
void _visit(btnode<T> * p);
// fucntion:preorder visit tree
void _preOrderTraver(btnode<T> * p);
// fucntion:inorder visit tree
void _inOrderTraver(btnode<T> * p);
// fucntion:postorder visit tree
void _postOrderTraver(btnode<T> * p);
// function:whether is balanced binary tree
std::pair<size_t,bool> _IsBalancedBinaryTree(btnode<T> *p);
// function:binary tree to double directed linklist
std::pair<btnode<T>*,btnode<T>*> _BinaryTreeToDoubleDirectedLinkedList(btnode<T>*p);
// function:show the linkedlist
void binarytree<T>::ShowLinklist(btnode<T>* p);
};
// function:make function
template<typename T>
binarytree<T>::binarytree()
{
this->R = NULL;
};
// function:make tree
// input:an array of data and its length
// output: a binary tree
template<typename T>
void binarytree<T>::_maketree(T * data,size_t s)
{
for(size_t i= 0;i<s;i++)
{
this->_insert(&(this->R),data[i]);
}
};
// function:insert key into tree
template<typename T>
void binarytree<T>::_insert(btnode<T> * *bt,T d)
{
if((*bt) == NULL)
{
(*bt) = new btnode<T>;
(*bt) -> key = d;
}
else
{
btnode<T> * p = *bt ;
if(d < p->key)
{
this->_insert(&(p->Lchild),d);
}
else if(d>p->key)
{
this->_insert(&(p->Rchild),d);
}
else
{
cout<<d<<" has been inserted"<<endl;
}
}
};
// function:visit node p
template<typename T>
void binarytree<T>::_visit(btnode<T> * p)
{
if(p != NULL)
{
cout<<"key="<<p->key<<endl;
}
else
{
cout<<"node point null"<<endl;
}
};
// fucntion:preorder visit tree
template<typename T>
void binarytree<T>::_preOrderTraver(btnode<T> * p)
{
if(p != NULL )
{
this->_visit(p);
this->_preOrderTraver(p->Lchild);
this->_preOrderTraver(p->Rchild);
}
};
// fucntion:inorder visit tree
template<typename T>
void binarytree<T>::_inOrderTraver(btnode<T> * p)
{
if(p != NULL )
{
this->_inOrderTraver(p->Lchild);
this->_visit(p);
this->_inOrderTraver(p->Rchild);
}
};
// fucntion:postorder visit tree
template<typename T>
void binarytree<T>::_postOrderTraver(btnode<T> * p)
{
if(p != NULL )
{
this->_postOrderTraver(p->Lchild);
this->_postOrderTraver(p->Rchild);
this->_visit(p);
}
};
// function:whether is balanced binary tree
template<typename T>
std::pair<size_t,bool> binarytree<T>::_IsBalancedBinaryTree(btnode<T> *p)
{
if( p == NULL )
return std::make_pair(0,true);
else
{
std::pair<size_t,bool> r = this -> _IsBalancedBinaryTree(p->Rchild);
std::pair<size_t,bool> l = this -> _IsBalancedBinaryTree(p->Lchild);
int h = (int)(r.first) - (int)(l.first);
h = abs(h);
if(h>1)
return std::make_pair(max(r.first,l.first)+1,false);
else return std::make_pair(max(r.first,l.first)+1,r.second && l.second);
}
};
// function:binary tree to double directed linklist
template<typename T>
std::pair<btnode<T>*,btnode<T>*> binarytree<T>::_BinaryTreeToDoubleDirectedLinkedList(btnode<T>* p)
{
std::pair<btnode<T>*,btnode<T>*> right,left ;
if(p == NULL)
{
left = std::make_pair(p,p);
return left;
}
else
{
if(p->Lchild)
{
left = this->_BinaryTreeToDoubleDirectedLinkedList(p->Lchild);
left.second->Rchild = p;
p->Lchild = left.second;
}
if(p->Rchild)
{
right = this->_BinaryTreeToDoubleDirectedLinkedList(p->Rchild);
right.first->Lchild = p;
p->Rchild = right.first;
}
if(p->Lchild && p->Rchild)
{
return std::make_pair(left.first,right.second);
}
else if(! p->Lchild && p->Rchild)
{
return std::make_pair(p,right.second);
}
else if(p->Lchild && ! p->Rchild)
{
return std::make_pair(left.second,p);
}
else return std::make_pair(p,p);
}
}
// function:show the linkedlist
template<typename T>
void binarytree<T>::ShowLinklist(btnode<T>* p)
{
cout<<"list data follows"<<endl;
while(p)
{
cout<<p->key<<endl;
p = p->Rchild;
}
}
test.cpp
#include <iostream>
#include "b-tree.h"
using namespace std;
// function:input data
std::pair<int*,size_t> Inputdata();
int main()
{
// tree has the root : tree::R
binarytree<int> * T = new binarytree<int>;
//int size = 10;
//int * data = new int[size];
//for(int i=0;i<size;i++)
//{
// data[i] = rand()%20;
//}
int data[9] = {4,7,3,2,8,6,5,9,10};
std::pair<int*,size_t> d = Inputdata();
T->_maketree(d.first,d.second);
cout<<"preorder traversal"<<endl;
T->_preOrderTraver(T->R);
cout<<"inorder traversal"<<endl;
T->_inOrderTraver(T->R);
cout<<"postorder traversal"<<endl;
T->_postOrderTraver(T->R);
std::pair<size_t,bool> r=T->_IsBalancedBinaryTree(T->R);
cout<<"whether it is balanced binary tree,result is "<<r.second<<endl;
T->ShowLinklist(T->_BinaryTreeToDoubleDirectedLinkedList(T->R).first);
system("pause");
return 0;
}
// function:input data
std::pair<int*,size_t> Inputdata()
{
size_t s = 0;
cout<<"please input the number(>=0) of data,size = "<<endl;
cin>>s;
std::pair<int*,size_t> r;
int * p = NULL;
if(s == 0)
{
r = std::make_pair(p,0);
return r;
}
else
{
p = new int[s];
cout<<"please input data"<<endl;
for(size_t i = 0; i<s; i++)
{
cin>>p[i];
}
cout<<"ok,data input over"<<endl;
r = std::make_pair(p,s);
return r;
}
}