首先二叉树的节点定义如下：
struct BinaryNode
{
BinaryNode *_left;
BinaryNode *_right;
T _data;
BinaryNode( T data ) :_data(data), _left( NULL), _right(NULL )
{};
};
二叉树的结构以及接口如下
template
class BinaryTree
{
typedef BinaryNode Node;
public:
BinaryTree() :_head( NULL)
{};
BinaryTree( const T * a, size_t size, const T & valiue)
~BinaryTree()
BinaryTree( BinaryTree &b )
void PrevOder()
void InOder()
void PostOder()
private:
public:
void LevalOder()
size_t depth()
size_t size()
size_t learsize()
void _LevalOder(BinaryNode *root);
size_t _depth(BinaryNode *root);
void _size(BinaryNode *root, int *p);
void _leafsize(BinaryNode *root, size_t *p);
int Leafsize(BinaryNode *root);
void PrevOder_Nor();
void InOder_Nor();
void PostOder_Nor();
void Distory(Node *_root)
Node* _Copy(Node *cur);
private:
BinaryNode *_root;
};
二叉树的建立（构造函数）
BinaryTree( const T * a, size_t size, const T & valiue)
{
size_t index = 0;
_root = _CreatTree( a, size , index, valiue);
}
BinaryNode* _CreatTree(const T* a, size_t size, size_t &index, const T &valiue)
{
BinaryNode *root = NULL;
if (index < size&& a[index ] != valiue)
{
root = new BinaryNode (a[index]);
root->_left = _CreatTree(a, size , ++index, valiue);
root->_right = _CreatTree(a, size , ++index, valiue);
}
return root;
}
二叉树的销毁（析构函数）
~BinaryTree()
{
Distory(_root);
cout << " ~BinaryTree()" << endl;
}
void Distory(Node *_root)
{
if (_root == NULL)
return;
Distory( _root->_left);
Distory( _root->_right);
if (_root )
delete _root ;
_root == NULL ;
}
二叉树的拷贝(拷贝构造)
BinaryTree( BinaryTree &b )
{
_root = _Copy( b._root);
}
BinaryNode* BinaryTree< T>::_Copy(Node *cur)
{
if (cur == NULL)
return NULL ;
Node *tmp = new Node(cur->_data);
tmp->_left=_Copy( cur->_left);
tmp->_right=_Copy( cur->_right);
return tmp;
}
求叶子节点个数（两种方法）
一：
int BinaryTree ::Leafsize( BinaryNode *root)
{
int count;
if (root == NULL)
count = 0;
else if (root->_left == NULL&&root ->_right == NULL)
{
count = 1;
}
else count = Leafsize(root ->_left) + Leafsize(root->_right);
return count;
}
二：
void BinaryTree ::_leafsize( BinaryNode *root, size_t * p)
{
if (root != NULL)
{
_leafsize( root->_left,p );
_leafsize( root->_right,p );
if (root ->_left == NULL&& root->_right == NULL )
{
++ *p;
}
}
}
二叉树前序遍历递归
void _PrevOder(BinaryNode * root)
{
if (root == NULL)
return;
cout << root->_data << " " ;
_PrevOder( root->_left);
_PrevOder( root->_right);
}
二叉树前序遍历非递归
void BinaryTree ::PrevOder_Nor()
{
BinaryNode *cur = _root;
stack*> s;
if (cur == NULL )
return;
s.push(cur);
while (!s.empty())
{
BinaryNode *tmp = s.top();
cout << tmp->_data << " ";
s.pop();
if (tmp->_right)
{
s.push(tmp->_right);
}
if (tmp->_left)
{
s.push(tmp->_left);
}
}
cout << endl;
}
二叉树层序遍历（队列实现）
void BinaryTree ::_LevalOder( BinaryNode *root)
{
deque*> q;
q.push_back( root);
while (q.size())
{
BinaryNode *pNode = q.front();
q.pop_front();
cout << pNode->_data << " ";
if (pNode->_left)
{
q.push_back(pNode->_left);
}
if (pNode->_right)
{
q.push_back(pNode->_right);
}
}
}
二叉树中序遍历递归
void _InOder(BinaryNode * root)
{
if (root == NULL)
return;
_InOder( root->_left);
cout << root->_data << " " ;
_InOder( root->_right);
}
二叉树中序遍历非递归
void BinaryTree ::InOder_Nor()
{
if (_root == NULL )
return;
Node *cur = _root;
stack s;
while (cur||!s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node *tmp = s.top();
cout << tmp->_data << " ";
s.pop();
cur = tmp->_right;
}
cout << endl;
}
二叉树后序遍历递归
void _PostOder(BinaryNode * root)
{
if (root == NULL)
return;
_PostOder( root->_left);
_PostOder( root->_right);
cout << root->_data << " " ;
}
二叉树后序遍历非递归
void BinaryTree ::PostOder_Nor()
{
if (_root == NULL )
return;
Node *cur = _root;
stack s;
Node *prev = NULL ;
while (cur||!s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node *tmp = s.top();
if (tmp->_right == NULL || tmp->_right == prev)
{
cout << tmp->_data << " " ;
s.pop();
prev = tmp;
}
else
{
cur = tmp->_right;
}
}
cout << endl;
}
二叉树的深度
size_t BinaryTree ::_depth( BinaryNode *root)
{
int hleft;
int hright;
int max;
if (root )
{
hleft = _depth( root->_left);
hright = _depth( root->_right);
max = hleft > hright ? hleft : hright;
return max + 1;
}
else
{
return 0;
}
}
二叉树的大小
size_t size()
{
int count = 0;
_size(_root,&count);
return count;
}
void BinaryTree ::_size( BinaryNode *root,int *p)
{
if (root )
{
++(* p);
_size( root->_left, p );
_size( root->_right, p );
}
return ;
}
