/////////////////////////////////////////
// BinaryTree.h
#ifndef _BINARYTREE_H
#define _BINARYTREE_H
typedef char TElemType;
enum Status {
ERROR,
OK
};
typedef struct BiTNode {
TElemType data; //数据域
BiTNode *lchild, *rchild; //左子树 右子树指针
BiTNode() { lchild = NULL; rchild = NULL; } //构造空树
BiTNode( TElemType e ) { data = e; lchild = NULL; rchild = NULL; } //构造只有根结点的树
BiTNode( TElemType e, BiTNode *lptr, BiTNode *rptr ); //将两棵子树森林转为树
bool operator == ( BiTNode &root ); //判断两棵树是否相等
void Release(); //释放空间
}BiTNode, *BiTree;
class BinaryTree {
private:
BiTree m_pRoot; //树根
BiTNode *CreateBiTree( const char *PreOrderStr, int &pos, const TElemType empty );
BiTNode *CopyTree( const BiTree &T );
public:
BinaryTree() { m_pRoot = NULL; }
BinaryTree( const char *PreOrderStr, const TElemType empty ); //根据先序序列建树
BinaryTree( BinaryTree &T ); //复制二叉树
~BinaryTree();
bool operator == ( BinaryTree &T ); //判断两棵树是否相等
Status Clear(); //清为空树
inline bool IsEmpty() { return m_pRoot == 0; }; //判空
int GetDepth( BiTree T ); //求树的深度
inline BiTree &GetRoot() { return m_pRoot; }; //求树根
inline TElemType GetValue( BiTNode *e ) { return e->data; }; //求结点e的值
inline void SetValue( BiTNode *e, TElemType value ) { e->data = value; }; //给结点e赋值
BiTNode *GetParent( BiTNode *e ); //求结点e的双亲
BiTNode *GetLeftChild( BiTNode *e ); //求结点e的左孩子
BiTNode *GetRightChild( BiTNode *e ); //求结点e的右孩子
BiTNode *GetLeftSibling( BiTNode *e ); //求结点e的左兄弟
BiTNode *GetRightSibling( BiTNode *e ); //求结点e的右兄弟
Status PreOrderTraverse( BiTree &T, Status ( *Visit )( TElemType e ) ); //先序遍历
Status InOrderTraverse( BiTree &T, Status ( *Visit )( TElemType e ) ); //中序遍历
Status PostOrderTraverse( BiTree &T, Status ( *Visit )( TElemType e ) ); //后序遍历
int CountLeaf( BiTree &T ); //统计二叉树上叶子结点的个数
};
#endif
////////////////////////////////////////////////////////////////////////
// BinaryTree.cpp
#include <iostream>
#include "BinaryTree.h"
using namespace std;
//////////////////////////////////////////////////////////////////////
// BiTNode
BiTNode::BiTNode( TElemType e, BiTNode *lptr, BiTNode *rptr )
{
data = e;
lchild = lptr;
rchild = rptr;
}
void BiTNode::Release()
{
if( lchild ) lchild->Release();
if( rchild) rchild->Release();
delete this;
}
bool BiTNode::operator == ( BiTNode &root )
{
if( !this && !&root ) return true;
if( ( !this && &root ) || ( this && !&root ) ) return false;
if( data != root.data ) return false;
return *this->lchild == *root.lchild && *this->rchild == *root.rchild;
}
///////////////////////////////////////////////////////////////////////
// BinaryTree
BiTNode *BinaryTree::CreateBiTree( const TElemType *PreOrderStr, int &pos, const TElemType empty )
{
if( pos >= int( strlen( PreOrderStr ) ) ) return NULL;
BiTNode *T;
if( PreOrderStr[ ++ pos ] == empty )
T = NULL;
else
{
if( !( T = new BiTNode( PreOrderStr[ pos ] ) ) ) exit( 1 );
T->lchild = CreateBiTree( PreOrderStr, pos, empty );
T->rchild = CreateBiTree( PreOrderStr, pos, empty );
}
return T;
}
BinaryTree::BinaryTree( const TElemType *PreOrderStr, const TElemType empty )
{
int pos = -1;
m_pRoot = CreateBiTree( PreOrderStr, pos, empty );
}
BiTNode *BinaryTree::CopyTree( const BiTree &T )
{
if( T )
{
BiTNode *lptr = CopyTree( T->lchild );
BiTNode *rptr = CopyTree( T->rchild );
return new BiTNode( T->data, lptr, rptr );
}
else
return NULL;
}
BinaryTree::BinaryTree ( BinaryTree &T )
{
m_pRoot = CopyTree( T.GetRoot() );
}
BinaryTree::~BinaryTree()
{
if( m_pRoot ) m_pRoot->Release();
}
bool BinaryTree::operator == ( BinaryTree &T )
{
return ( *m_pRoot ) == *T.GetRoot();
}
int BinaryTree::GetDepth( BiTree T )
{
return T ? 1 + max( GetDepth( T->lchild ), GetDepth( T->rchild ) ) : 0;
}
Status BinaryTree::PreOrderTraverse( BiTree &T, Status( *Visit )( TElemType e ) )
{
if( T )
{
Visit( T->data );
PreOrderTraverse( T->lchild, Visit );
PreOrderTraverse( T->rchild, Visit );
}
return OK;
}
Status BinaryTree::InOrderTraverse( BiTree &T, Status( *Visit )( TElemType e ) )
{
if( T )
{
InOrderTraverse( T->lchild, Visit );
Visit( T->data );
InOrderTraverse( T->rchild, Visit );
}
return OK;
}
Status BinaryTree::PostOrderTraverse( BiTree &T, Status( *Visit )( TElemType e ) )
{
if( T )
{
PostOrderTraverse( T->lchild, Visit );
PostOrderTraverse( T->rchild, Visit );
Visit( T->data );
}
return OK;
}
Status BinaryTree::Clear()
{
if( m_pRoot ) m_pRoot->Release();
return OK;
}
int BinaryTree::CountLeaf( BiTree &T )
{
return T ? ( !T->lchild && !T->rchild ) + CountLeaf( T->lchild ) + CountLeaf( T->rchild ) : 0;
}