聚星亭

吾笨笨且懒散兮 急须改之而奋进
posts - 74, comments - 166, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理
/********************************************************************
  created:  2009/01/09
  created:  9:1:2009   12:42
  author:    cooldiyer
  site:    
http://www.xcodez.com/
  
  purpose:  多叉树类文件
********************************************************************
*/

#include 
<windows.h>
#include 
<stdio.h>

VOID
FORCEINLINE
InitializeListHead(
           IN PLIST_ENTRY ListHead
           )
{
    ListHead
->Flink = ListHead->Blink = ListHead;
}

#define IsListEmpty(ListHead) \
((ListHead)
->Flink == (ListHead))

VOID
FORCEINLINE
RemoveEntryList(
        IN PLIST_ENTRY Entry
        )
{
    PLIST_ENTRY Blink;
    PLIST_ENTRY Flink;
  
    Flink 
= Entry->Flink;
    Blink 
= Entry->Blink;
    Blink
->Flink = Flink;
    Flink
->Blink = Blink;
}

VOID
FORCEINLINE
InsertTailList(
         IN PLIST_ENTRY ListHead,
         IN PLIST_ENTRY Entry
         )
{
    PLIST_ENTRY Blink;
  
    Blink 
= ListHead->Blink;
    Entry
->Flink = ListHead;
    Entry
->Blink = Blink;
    Blink
->Flink = Entry;
    ListHead
->Blink = Entry;
}


VOID
FORCEINLINE
InsertHeadList(
         IN PLIST_ENTRY ListHead,
         IN PLIST_ENTRY Entry
         )
{
    PLIST_ENTRY Flink;
  
    Flink 
= ListHead->Flink;
    Entry
->Flink = Flink;
    Entry
->Blink = ListHead;
    Flink
->Blink = Entry;
    ListHead
->Flink = Entry;
}


typedef 
struct tagTREENODE
{
  LPARAM      lParam;      
// 关联的值
  int        cChildren;    // 子节点个数
  LIST_ENTRY    ListEntry;    // 同一等级的节点
  LIST_ENTRY    ChildListEntry;  // 子节点头
  tagTREENODE *  pParentNode;  // 父节点
} TREENODE, *PTREENODE;



#define TN_ROOT                ((HTREENODE)(ULONG_PTR)-0x10000)
#define TN_FIRST               ((HTREENODE)(ULONG_PTR)-0x0FFFF)
#define TN_LAST                ((HTREENODE)(ULONG_PTR)-0x0FFFE)
typedef PTREENODE  HTREENODE;


class CTree
{  
public:
  CTree() {
    m_nCount 
= 0;
    m_nRootChildCount 
= 0;
    InitializeListHead(
&m_ListHead);
  }
  
~CTree() {
    DeleteAllNodes();
  }

private:
  
int m_nCount;
  
int  m_nRootChildCount;
  LIST_ENTRY m_ListHead;

public:

  
int getCount() {
    
return m_nCount;
  }

  
int  getChildNodeCount(HTREENODE hNode) {
    
if (isRootNode(hNode)) {
      
return m_nRootChildCount;
    }
    
else {
      
return hNode->cChildren;
    }
  }

  HTREENODE getChildNode(HTREENODE hNode) {

    
if (NodeHasChildren(hNode) > 0) {
      
if (isRootNode(hNode)) {
        
return CONTAINING_RECORD(m_ListHead.Flink, TREENODE, ListEntry);
      }
      
else {
        
return CONTAINING_RECORD(hNode->ChildListEntry.Flink, TREENODE, ListEntry);
      }

    }
    
else {
      
return NULL;
    }
  }

  BOOL isRootNode(HTREENODE hNode) {
    
return TN_ROOT == hNode;
  }

  HTREENODE getRootNode(){
    
return TN_ROOT;
  }

  HTREENODE GetParentNode(HTREENODE hNode) {
    
return hNode->pParentNode;
  }


  HTREENODE getNextNode( HTREENODE hNode ) {

    PLIST_ENTRY  pListHead;

    
if (isRootNode(hNode)) {
      
return NULL;
    }

    
if (isRootNode(hNode->pParentNode)) {
      pListHead 
= &m_ListHead;
    }
    
else {
    
      pListHead 
= &hNode->pParentNode->ChildListEntry;
    }

    PLIST_ENTRY  pNext 
= hNode->ListEntry.Flink;

    
if (pListHead == pNext) {
      
return NULL;
    }
    
else {
      
return CONTAINING_RECORD(pNext, TREENODE, ListEntry);
    }
  }

  BOOL NodeHasChildren( HTREENODE hNode ) {
    
if (isRootNode(hNode)) {
      
return m_nRootChildCount > 0;
    }
    
else {
      
return hNode->cChildren > 0;
    }
  }

  HTREENODE InsertNode(LPARAM lparam, HTREENODE hParent 
= TN_ROOT, HTREENODE hInsertAfter = TN_LAST ) {

    TREENODE 
*  pTreeNode = new TREENODE;
    pTreeNode
->cChildren = 0;
    pTreeNode
->lParam = lparam;
    pTreeNode
->pParentNode = hParent;

    InitializeListHead(
&pTreeNode->ListEntry);
    InitializeListHead(
&pTreeNode->ChildListEntry);


    PLIST_ENTRY  pListEntry 
= NULL;

    
if (TN_ROOT == hParent) {
      pListEntry 
= &m_ListHead;

      m_nRootChildCount
++;
    }
    
else {
      pListEntry 
= &hParent->ChildListEntry;
      hParent
->cChildren++;
    }

    
if (TN_LAST == hInsertAfter) {
      InsertTailList(pListEntry, 
&pTreeNode->ListEntry);
    }
    
else if (TN_FIRST == hInsertAfter){
      InsertHeadList(pListEntry, 
&pTreeNode->ListEntry);
    }
    
else {
      InsertHeadList(
&hInsertAfter->ListEntry, &pTreeNode->ListEntry);
    }

    m_nCount
++;

    
return pTreeNode;
  }

  DWORD GetNodeData( HTREENODE hNode ) {
    
if (isRootNode(hNode)) {
      
return -1;
    }
    
else {
      
return hNode->lParam;
    }
  }

  BOOL SetNodeData( HTREENODE hNode, DWORD dwData ) {
    
if (isRootNode(hNode)) {
      
return FALSE;
    }
    
else {
      hNode
->lParam = dwData;
    }
    
    
return TRUE;
  }

  BOOL DeleteAllNodes() {
    
return DeleteNode(TN_ROOT);
  }

  BOOL DeleteNode(HTREENODE hNode) {
    
    HTREENODE hNext 
= getChildNode(hNode);

    
while (hNext) {
      HTREENODE hNextNode 
= getNextNode(hNext);
      DeleteNode(hNext);
      hNext 
= hNextNode;
    }

    
if (!isRootNode(hNode)) {
      
if (isRootNode(hNode->pParentNode))  {
        m_nRootChildCount
--;
      }
      
else {
        hNode
->pParentNode->cChildren--;
      }
      m_nCount
--;

      RemoveEntryList(
&hNode->ListEntry);
      delete hNode;
    }
    
return TRUE;
  }
};


void PrintNode(CTree * pTree, HTREENODE hNode, BOOL bIsRecursive)
{
  HTREENODE hNext 
= pTree->getChildNode(hNode);
  
  
while (hNext)
  {
    printf(
"0x%X 0x%X\t%d\n", hNext, pTree->GetParentNode(hNext), pTree->GetNodeData(hNext));

    
if (bIsRecursive){
      PrintNode(pTree, hNext, bIsRecursive);
    }
    
    hNext 
= pTree->getNextNode(hNext);
  }
}

int main(int argc, char* argv[])
{
  CTree  tree;
  HTREENODE hTreeNode 
= tree.InsertNode(1);
  tree.InsertNode(
2);
  tree.InsertNode(
3);

  HTREENODE hTreeChild 
= tree.InsertNode(4);
  tree.InsertNode(
6, hTreeChild);
  tree.InsertNode(
5, hTreeChild, TN_FIRST);
  HTREENODE hNewChild 
= tree.InsertNode(7, hTreeChild);

  tree.InsertNode(
8, hNewChild);
  tree.InsertNode(
9, hNewChild);

  PrintNode(
&tree, tree.getRootNode(), TRUE);


  
return 0;

说明:以上代码转载与 看雪学院 论坛
原帖地址:http://bbs.pediy.com/showthread.php?t=80173

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理