Posted on 2009-03-30 17:20
besterChen 阅读(939)
评论(0) 编辑 收藏 引用
/********************************************************************
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