今天,我们来讨论树的部分算法和实现以及如何使用递归算法.
好了,我们看如何实现的吧.我还是要重申一遍,大家写程序的时候,一定要注意思想,方法,风格这三方面.因为,当你维护一个大型系统的时候,你会发现,它会减轻你好多负担的.
代码如下:
#ifndef _TREE_H_#define _TREE_H_
typedef void* HTREEITEM;
template <typename T>class CTree;template <typename T>struct Elem{ friend class CTree<T>; private: T elem; Elem<T> * plChild; Elem<T> * prChild;
public: Elem():plChild(NULL),prChild(NULL){}; Elem( T e ):plChild(NULL),prChild(NULL),elem(e){};};
template <typename T>class CTree{ private: Elem<T> * m_pRoot;
public: CTree( const T e ); virtual ~CTree();
HTREEITEM InsertItem( const T e, HTREEITEM hParent = NULL );
void PreOrder( HTREEITEM hStartItem = NULL ); void InOrder( HTREEITEM hStartItem = NULL ); void PostOrder( HTREEITEM hStartItem = NULL );};
template <typename T>CTree<T>::CTree( const T e ){ m_pRoot = new Elem<T>(e);}
template <typename T>CTree<T>::~CTree(){ if ( m_pRoot ) { if ( m_pRoot->plChild ) { delete m_pRoot->plChild; } if ( m_pRoot->prChild ) { delete m_pRoot->prChild; } delete m_pRoot; }}
template <typename T>HTREEITEM CTree<T>::InsertItem( const T e, HTREEITEM hParent/* = NULL*/ ){ Elem<T> * pParent = NULL; Elem<T> * pElem = NULL;
pElem = new Elem<T>(e); if ( hParent == NULL ) pParent = m_pRoot; else pParent = static_cast<Elem<T>*>(hParent); if ( pParent ->plChild == NULL ) { pParent ->plChild = pElem; } else { pParent = pParent ->plChild; while( pParent ->prChild ) { pParent = pParent ->prChild ; } pParent ->prChild = pElem; } return static_cast<HTREEITEM>(pElem);}
template <typename T>void CTree<T>::PreOrder( HTREEITEM hStartItem/* == NULL*/ ){ Elem<T> * pStart = NULL;
if ( hStartItem == NULL ) pStart = m_pRoot; else pStart = static_cast<Elem<T>*>(hStartItem); if ( pStart ) { cout << pStart ->elem ; if ( pStart ->plChild ) { PreOrder( static_cast<HTREEITEM>(pStart ->plChild) ); } if ( pStart ->prChild ) { PreOrder( static_cast<HTREEITEM>(pStart ->prChild) ); } }}
template <typename T>void CTree<T>::InOrder( HTREEITEM hStartItem /* = NULL */ ){ Elem<T> * pStart = NULL; if ( hStartItem == NULL ) pStart = m_pRoot; else pStart = static_cast<Elem<T>*>(hStartItem); if ( pStart ) { if ( pStart ->plChild ) { PreOrder( static_cast<HTREEITEM>(pStart ->plChild) ); } cout << pStart ->elem ; if ( pStart ->prChild ) { PreOrder( static_cast<HTREEITEM>(pStart ->prChild) ); } }}
template <typename T>void CTree<T>::PostOrder( HTREEITEM hStartItem /* = NULL */ ){ Elem<T> * pStart = NULL; if ( hStartItem == NULL ) pStart = m_pRoot; else pStart = static_cast<Elem<T>*>(hStartItem); if ( pStart ) { if ( pStart ->plChild ) { PreOrder( static_cast<HTREEITEM>(pStart ->plChild) ); } if ( pStart ->prChild ) { PreOrder( static_cast<HTREEITEM>(pStart ->prChild) ); } cout << pStart ->elem ; }}
#endif//_TREE_H_
至少,我认为这个代码是很酷的.呵呵
