深夜了,"种"一棵"树",注释不多,有兴趣的朋友可看一下.

Question

一些宏
#ifndef NULL  
#define NULL 0  
#endif //NULL    #ifndef TRUE  
#define TRUE 1  
#endif //TRUE    #ifndef FALSE   
#define FALSE 0  
#endif //FALSE    typedef  int BOOL;  
typedef  void * HID; -----------------------------------*.h------------------------------------------------
class CfPtrTree  
{
protected:

struct CNode
{
CNode *lpstParent;  //指向父节点
CNode *lpstFirstChild,*lpstLastChild;  //指向子节点
CNode *lpstPrevSibling, *lpstNextSibling;  //指向兄弟节点
LPVOID pElement;      //数据
DWORD  dwKey;      //KEY
};public:
//
CfPtrTree();
virtual ~CfPtrTree();

protected:
//申请一个新节点
CNode * AllocNode();
//释放一个旧节点
void FreeNode(CNode * lpstNode);public:
//创建根节点
virtual HID CreateRoot(LPVOID lpElement);
//插入一个新"子"节点
virtual HID InsertChild(LPVOID lpElement,HID hParentNode);
//在...前插入一个新"兄弟"节点
virtual HID InsertSiblingBefore(LPVOID lpElement,HID hSiblingNode);
//在...后插入一个新"兄弟"节点
virtual HID InsertSiblingAfter(LPVOID lpElement,HID hSiblingNode);
//取得根节点
HID GetRootPosition();
//取得父节点
HID GetParent(HID hNode);
//取得第一个"子"节点
HID GetFirstChild(HID hNode);
//取得最后一个"子"节点
HID GetLastChild(HID hNode);
//取得下一个"兄弟"节点
HID GetNextSibling(HID hNode);
//取得上一个"兄弟"节点
HID GetPrevSibling(HID hNode);
//取得节点值
virtual BOOL GetElement(HID hNode,LPVOID & lpElement);
//取得节点KEY
virtual BOOL GetKey(HID hNode,DWORD & dwKey);
//设置节点值
virtual BOOL SetElement(HID hNode,LPVOID lpElement);
//设置节点KEY
virtual BOOL SetKey(HID hNode,DWORD dwKey);
//移除节点
virtual BOOL RemoveAt(HID hNode,LPVOID & lpElement);
//移除节点
BOOL RemoveAt(HID hNode);
//移除所有节点
void RemoveAll();
//取得节点数量
ULONG GetCount();

public:
// 其它方法protected:
//根节点
CNode * m_pstRoot;
//节点数量
ULONG m_nCount;};-----------------------------------*.h------------------------------------------------

Answer 1

//申请内存,这里封装的是malloc + memset
//释放内存,这里封装的是free
//请在使用前自行替换.-----------------------------------*.CPP------------------------------------------------
CfPtrTree::CfPtrTree()
{
m_pstRoot = NULL;
m_nCount = 0;
}CfPtrTree::~CfPtrTree()
{
RemoveAll();
}
//申请一个新节点
CfPtrTree::CNode * CfPtrTree::AllocNode()
{
CNode* pNode = (CNode*)::fAlloc(sizeof(CNode));
if( pNode )
{
//计数+1
m_nCount++;
}
return pNode;
}
//释放一个旧节点
void CfPtrTree::FreeNode(CNode * lpstNode)
{
if( lpstNode )
{
::fFree(lpstNode);
//计数-1
m_nCount--;
}
}
//创建根节点
HID CfPtrTree::CreateRoot(LPVOID lpElement)
{
if( m_pstRoot == NULL )
{
//根节点为空,构造一个根节点
m_pstRoot = AllocNode();
if( m_pstRoot )
{
//保存元素
m_pstRoot->pElement = lpElement; }
}
else
{
//根节点已经存在,则只更新节点"值"
SetElement(m_pstRoot,lpElement);
} return m_pstRoot;
}//插入一个新"子"节点
HID CfPtrTree::InsertChild(LPVOID lpElement,HID hParentNode)
{
//"父"节点
CNode * pstParentNode = (CNode *)hParentNode;
//新节点
CNode * pstNewNode = NULL;  if( pstParentNode )
{
if( pstParentNode->lpstLastChild == NULL && pstParentNode->lpstFirstChild == NULL )
{
//如果没有"子"节点
//新节点
pstNewNode = AllocNode();
if( pstNewNode )
{

//保存元素
pstNewNode->pElement = lpElement;

//指向"父"节点
pstNewNode->lpstParent = pstParentNode;
//同时指向"子"节点
pstParentNode->lpstLastChild = pstNewNode;
pstParentNode->lpstFirstChild = pstNewNode;

}

}
else
{
//在最后"弟"插入一个新"弟"节点
pstNewNode =(CNode *)InsertSiblingAfter(lpElement,pstParentNode->lpstLastChild);
}
}

return pstNewNode;
}//在...前插入一个新"兄弟"节点
HID CfPtrTree::InsertSiblingBefore(LPVOID lpElement,HID hSiblingNode)
{
//"父"节点
CNode * pstParentNode = NULL;
//插入点
CNode * pstInsertNode = (CNode *)hSiblingNode;
//新节点
CNode * pstNewNode = NULL; 

if( pstInsertNode )
{
//"父"节点
pstParentNode = pstInsertNode->lpstParent;
//新节点
pstNewNode = AllocNode();

if( pstNewNode )
{
//保存元素
pstNewNode->pElement = lpElement;

//指向"父"节点
pstNewNode->lpstParent = pstParentNode;

//A<--->C ( 有可能并不存在A )
//在"兄弟"C前插入B到A和C之间
//1: A<---B
pstNewNode->lpstPrevSibling = pstInsertNode->lpstPrevSibling;
//2: A--->B
if( pstInsertNode->lpstPrevSibling )
{
//如果C不是最前一个"兄弟"
pstInsertNode->lpstPrevSibling->lpstNextSibling = pstNewNode;
}
//3: B--->C
pstNewNode->lpstNextSibling = pstInsertNode;
//4: B<---C
pstInsertNode->lpstPrevSibling = pstNewNode;

//A<--->B<--->C (可能并不存在A)
//如果B为最前一个"兄弟" && 不是根节点
if( pstNewNode->lpstPrevSibling == NULL && pstParentNode)
{
//更改"父"节点的最前一个"子"节点
pstParentNode->lpstFirstChild = pstNewNode;

}
}
} return pstNewNode;
}//在...后插入一个新"兄弟"节点
HID CfPtrTree::InsertSiblingAfter(LPVOID lpElement,HID hSiblingNode)
{
//"父"节点
CNode * pstParentNode = NULL;
//插入点
CNode * pstInsertNode = (CNode *)hSiblingNode;
//新节点
CNode * pstNewNode = NULL;  if( pstInsertNode )
{
//"父"节点
pstParentNode = pstInsertNode->lpstParent;
//新节点
pstNewNode = AllocNode();

if( pstNewNode )
{
//保存元素
pstNewNode->pElement = lpElement;

//指向"父"节点
pstNewNode->lpstParent = pstParentNode;

//A<--->C ( 有可能并不存在C )
//在"兄弟"A后插入B到A和C之间
//1:  B--->C 
pstNewNode->lpstNextSibling = pstInsertNode->lpstNextSibling;
//2:  B<---C 
if( pstInsertNode->lpstNextSibling )
{
//如果A不是最后一个"兄弟"
pstInsertNode->lpstNextSibling->lpstPrevSibling = pstNewNode;
}
//3:  A<---B
pstNewNode->lpstPrevSibling = pstInsertNode;
//4:  A--->B
pstInsertNode->lpstNextSibling = pstNewNode;

//A<--->B<--->C (可能并不存在C)
//如果B为最后一个"兄弟" && 不是根节点
if( pstNewNode->lpstNextSibling == NULL && pstParentNode)
{
//更改"父"节点的最后一个"子"节点
pstParentNode->lpstLastChild = pstNewNode;

}

}

}

return pstNewNode;
}
//取得根节点
HID CfPtrTree::GetRootPosition()
{
return m_pstRoot;
}
//取得父节点
HID CfPtrTree::GetParent(HID hNode)
{
CNode * pstParentNode = NULL;
if( hNode )
{
pstParentNode = ((CNode *)hNode)->lpstParent;
}
return pstParentNode;
}
//取得第一个子节点
HID CfPtrTree::GetFirstChild(HID hNode)
{
CNode * pstFirstChildNode = NULL;
if( hNode )
{
pstFirstChildNode = ((CNode *)hNode)->lpstFirstChild;
}
return pstFirstChildNode;
}
//取得最后一个子节点
HID CfPtrTree::GetLastChild(HID hNode)
{
CNode * pstLastChildNode = NULL;
if( hNode )
{
pstLastChildNode = ((CNode *)hNode)->lpstLastChild;
}
return pstLastChildNode;
}
//取得下一个兄弟节点
HID CfPtrTree::GetNextSibling(HID hNode)
{
CNode * pstNextSiblingNode = NULL;
if( hNode )
{
pstNextSiblingNode = ((CNode *)hNode)->lpstNextSibling;
}
return pstNextSiblingNode;
}
//取得上一个兄弟节点
HID CfPtrTree::GetPrevSibling(HID hNode)
{
CNode * pstPrevSiblingNode = NULL;
if( hNode )
{
pstPrevSiblingNode = ((CNode *)hNode)->lpstPrevSibling;
}
return pstPrevSiblingNode;
}
//取得节点值
BOOL CfPtrTree::GetElement(HID hNode,LPVOID & lpElement)
{
BOOL bResult = FALSE;
if(  bResult = ( hNode != NULL ) )
{
CNode * pstNode = ((CNode *)hNode);
//取值
lpElement = pstNode->pElement;
}
return bResult;
}
//取得节点KEY
BOOL CfPtrTree::GetKey(HID hNode,DWORD & dwKey)
{
BOOL bResult = FALSE;
if(  bResult = ( hNode != NULL ) )
{
CNode * pstNode = ((CNode *)hNode);
//取值
dwKey = pstNode->dwKey;
}
return bResult;
}//设置节点值
BOOL CfPtrTree::SetElement(HID hNode,LPVOID lpElement)
{
BOOL bResult = FALSE;
if( bResult = ( hNode != NULL ) )
{
CNode * pstNode = ((CNode *)hNode);
//写值
pstNode->pElement = lpElement;
}
return bResult;
}
//设置节点KEY
BOOL CfPtrTree::SetKey(HID hNode,DWORD dwKey)
{
BOOL bResult = FALSE;
if( bResult = ( hNode != NULL ) )
{
CNode * pstNode = ((CNode *)hNode);
//写值
pstNode->dwKey = dwKey;
}
return bResult;
}//移除节点
BOOL CfPtrTree::RemoveAt(HID hNode,LPVOID & lpElement)
{
BOOL bResult = FALSE;
if( bResult = ( hNode != NULL ) )
{
//分离节点
CNode *pstNode = ((CNode *)hNode);

if( pstNode->lpstNextSibling && pstNode->lpstPrevSibling )
{ 
//有"兄弟"节点
//A<--->B<--->C
//1: A<---C
pstNode->lpstNextSibling->lpstPrevSibling = pstNode->lpstPrevSibling;
//2: A--->C
pstNode->lpstPrevSibling->lpstNextSibling = pstNode->lpstNextSibling;
// //清除节点连接
// pstNode->lpstPrevSibling = NULL;
// pstNode->lpstNextSibling = NULL;
// pstNode->lpstParent = NULL;


}
else if( pstNode->lpstNextSibling )
{
//有"弟"节点

if( pstNode->lpstParent )
{
//有"父"节点 //"父"节点的第一个"子"节点指向"弟"节点
pstNode->lpstParent->lpstFirstChild = pstNode->lpstNextSibling;
//"弟"节点没有"兄"节点
pstNode->lpstParent->lpstFirstChild->lpstPrevSibling = NULL;
}
else
{
//无"父"节点
//"弟"节点没有"兄"节点
pstNode->lpstNextSibling->lpstPrevSibling = NULL;
//当前节点是根节点并且有"弟"节点
if( pstNode == m_pstRoot && pstNode->lpstNextSibling )
{
//根节点为"弟"节点
m_pstRoot = pstNode->lpstNextSibling;
}

}

// //清除节点连接
// pstNode->lpstPrevSibling = NULL;
// pstNode->lpstNextSibling = NULL;
// pstNode->lpstParent = NULL;

}
else if( pstNode->lpstPrevSibling )
{
//有"兄"节点 if( pstNode->lpstParent )
{
//有"父"节点
//"父"节点的最后一个"子"节点指向"兄"节点
pstNode->lpstParent->lpstLastChild = pstNode->lpstPrevSibling;
//"兄"节点没有"弟"节点
pstNode->lpstParent->lpstLastChild->lpstNextSibling = NULL;
}
else
{
//无"父"节点
//"兄"节点没有"弟"节点
pstNode->lpstPrevSibling->lpstNextSibling = NULL;
}
// //清除节点连接
// pstNode->lpstPrevSibling = NULL;
// pstNode->lpstNextSibling = NULL;
// pstNode->lpstParent = NULL;

}
else // if(  pstNode->lpstNextSibling == NULL && pstNode->lpstPrevSibling == NULL )
{
//当前节点是根节点
if( pstNode == m_pstRoot )
{
//树已经为"空"
m_pstRoot = NULL;
}
}

//取出节点值
lpElement = pstNode->pElement;

//清除节点连接
pstNode->lpstPrevSibling = NULL;
pstNode->lpstNextSibling = NULL;
pstNode->lpstParent = NULL;
//层次遍历删除
//把所有节点连成一个链表进行删除
//当前节点
CNode *pstHead = pstNode;
//尾节点
CNode *pstTail = pstHead; while(pstHead)
{
if( pstHead->lpstFirstChild && pstHead->lpstLastChild )
{
//连接到最后(这里只是半连接)
pstTail->lpstNextSibling = pstHead->lpstFirstChild;
//指向末尾
pstTail = pstHead->lpstLastChild;

//"子"节点已经都连接到"兄弟"节点后了
pstHead->lpstFirstChild = pstHead->lpstLastChild = NULL;
}

//下一节点
CNode *pstTemp = pstHead->lpstNextSibling;
//删除节点
FreeNode(pstHead);
//头节点
pstHead = pstTemp; }
}
return bResult;
}
//移除节点
BOOL CfPtrTree::RemoveAt(HID hNode)
{
LPVOID pElement = NULL;
return RemoveAt(hNode,pElement);
}
//移除所有节点
void CfPtrTree::RemoveAll()
{
//从根节点开始删除
while( m_pstRoot )
{
//如果删除节点为根节点,则根节点会指向"弟"节点
RemoveAt(m_pstRoot); 
}
}
//取得节点数量
ULONG CfPtrTree::GetCount()
{
return m_nCount;
}-----------------------------------*.CPP------------------------------------------------

Answer 2

MFC 用的 还是 WTL 呵呵 
有demo 就更好了 
[email protected]

Answer 3

1:没用任何类库,用的宏都已经重定义了(*.h)
2:按上面注释的改了就可以用.
3:编写测试环境 MS C/C++
4:都在这里了,邮件就不发了.DEMO?下面这个算不算?
还有个枚举磁盘文件(WINDOWS),只用到一个方法(InsertChild),不太好做示例.CfPtrTree a;

HID b = a.CreateRoot("aaaa");
// a.InsertSiblingAfter("bbbb",b);
// a.InsertSiblingAfter("bbbb",b);
HID c = a.InsertChild("cccc",b);
HID e = a.InsertSiblingAfter("bbbb",c);
a.InsertChild("asda",e);
HID d = a.InsertSiblingBefore("dddd",c);
a.InsertChild("eeee",d);

// a.RemoveAt(c);
// a.RemoveAt(b);
a.RemoveAll();