二叉树因有规范和确定性的结构而得到广泛的应用，在每个树节点中，有两个子二叉树，通常称为孩子节点和兄弟节点。在我的应用中，要将二叉树应用于文档分析，文档是一个嵌套的子项目集合，每个项目都有其特定的属性，文档最终分析的结果是一个树型结构的项目视图。根据这一要求，我需要在节点中维护一个基于命名属性的动态属性表以存储项目的不同的属性，属性表由哈希表实现，且看设计如下：
1、定义二叉树：
/*二叉树的宿主的结构*/
typedef struct tagTreeData{
LINK lkItems; /*宿主的根连接件，维护二叉树的根节点*/
LINK lk; /*宿主的自身连接件*/
}TreeData;
/*二叉树节点的结构*/
typedef struct tagTreeItem{
LINK lkChild; /*孩子节点的根连接部件*/
LINK lkSibling; /*自身连接件，作为父节点间兄弟节点的连接之用*/
LINKPTR pht; /*该节点的属性表*/
int nChildCount; /*子节点的计数*/
unsigned long data; /*节点的长整型数值*/
}TreeItem;
/*定义节点数据标识*/
#define lkTreeData 21
#define lkTreeItem 22
/*定义属性表的哈希表的模基为7*/
#define MIN_ITEM 7
/*从宿主连接件指针中恢复宿主数据*/
#define TreeDataFromLink(p) ((TreeData*)((unsigned int)p - (unsigned int)&(((TreeData*)0)->lk)))
/*从宿主根连接件指针中恢复宿主数据*/
#define TreeDataFromChild(p) ((TreeData*)((unsigned int)p - (unsigned int)&(((TreeData*)0)->lkItems)))
/*从节点连接件指针中恢复节点数据*/
#define TreeItemFromLink(p) ((TreeItem*)((unsigned int)p - (unsigned int)&(((TreeItem*)0)->lkSibling)))
/*从节点孩子节点的根连接件指针中恢复节数据*/
#define TreeItemFromChild(p) ((TreeItem*)((unsigned int)p - (unsigned int)&(((TreeItem*)0)->lkChild)))
2、二叉分析树的操作实现：
/*创建二叉树*/
LINKPTR CreateTreeData(void)
{
TreeData* ptd = (TreeData*)calloc(1,sizeof(TreeData));
ptd->lk.tag = lkTreeData;
/*初始化根连接部件*/
InitRootLink(&ptd->lkItems);
return &(ptd->lk);
}
/*销毁二叉树
ptr: 二叉树连接部件*/
void DestroyTreeData(LINKPTR ptr)
{
TreeData* ptd;
assert(ptr);
assert(ptr->tag == lkTreeData);
ptd = TreeDataFromLink(ptr);
/*清除宿主中的所有节点*/
ClearTreeData(ptr);
free(ptd);
}
/*清除宿主中的所有节点
ptr: 二叉树连接部件*/
void ClearTreeData(LINKPTR ptr)
{
TreeData* ptd;
LINKPTR ilk,pre;
assert(ptr);
assert(ptr->tag == lkTreeData);
ptd = TreeDataFromLink(ptr);
ilk = GetFirstLink(&ptd->lkItems);
while(ilk)
{
pre = ilk;
ilk = GetNextLink(ilk);
/*删除该节点以及该节点的子节点*/
DeleteTreeDataItem(ptr,pre);
}
}
/*删除该节点以及该节点的子节点
ptrTree: 二叉树连接件指针
ptrItem: 待删除的节点连接件指针*/
void DeleteTreeDataItem(LINKPTR ptrTree,LINKPTR ptrItem)
{
LINKPTR parent,ilk,pre;
TreeItem* ptt;
TreeItem* pup;
TreeData* ptd;
assert(ptrTree);
assert(ptrTree->tag == lkTreeData);
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
ptt = TreeItemFromLink(ptrItem);
/*删除子节点*/
ilk = GetFirstLink(&ptt->lkChild);
while(ilk)
{
pre = ilk;
ilk = GetNextLink(ilk);
DeleteTreeDataItem(ptrTree,pre);
}
/*销毁该节点的属性表*/
DestroyHashTable(ptt->pht);
/*取得该节点的父节点的连接件指针*/
parent = GetTreeDataParentItem(ptrItem);
if(parent)
{
/*父节点存在，则从父节点的子节点链表中删除该节点*/
pup = TreeItemFromLink(parent);
DeleteLinkAt(&(pup->lkChild),ptrItem);
pup->nChildCount --;
}else
{
/*父节不存在，说明该节点是根节点，则从宿主的根节点链表中删除该节点*/
ptd = TreeDataFromLink(ptrTree);
DeleteLinkAt(&(ptd->lkItems),ptrItem);
}
/*释放节点*/
free(ptt);
}
/*在父节点中插入一个新的子节点
ptrTree: 二叉树连接件指针
parent: 父节点连接件指针
pos: 待插入的位置，可以为LINK_LAST、LINK_FIRST或某一已经存在于链表中的指针*/
LINKPTR InsertTreeDataItem(LINKPTR ptrTree,LINKPTR parent,LINKPTR pos)
{
TreeItem* ptt;
TreeItem* pup;
TreeData* ptd;
assert(ptrTree);
assert(ptrTree->tag == lkTreeData);
/*新建一个节点*/
ptt = (TreeItem*)calloc(1,sizeof(TreeItem));
InitRootLink(&ptt->lkChild): /*初始化该节点孩子节点的根连接件*/
ptt->lkSibling.tag = lkTreeItem;
ptt->pht = CreateHashTable(MIN_ITEM); /*创建属性表*/
if(parent == NULL)
{
/*父节点为空，则插入到根节点链表中*/
ptd = TreeDataFromLink(ptrTree);
InsertLinkAt(&(ptd->lkItems),pos,&(ptt->lkSibling));
}else
{
/*父节点存在，则插入到他的孩子节点链表中*/
pup = TreeItemFromLink(parent);
InsertLinkAt(&(pup->lkChild),pos,&(ptt->lkSibling));
pup->nChildCount ++;
}
/*返回该节点的连接件指针*/
return &(ptt->lkSibling);
}
/*取得节点的孩子节点计数
ptrItem: 节点的连接件指针*/
int GetTreeDataChildItemCount(LINKPTR ptrItem)
{
TreeItem* ptt;
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
ptt = TreeItemFromLink(ptrItem);
return ptt->nChildCount;
}
/*取得第一个孩子节点的连接件指针
ptrItem: 当前节点连接件指针*/
LINKPTR GetTreeDataChildItem(LINKPTR ptrItem)
{
TreeItem* ptt;
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
ptt = TreeItemFromLink(ptrItem);
return GetFirstLink(&ptt->lkChild);
}
/*取得父亲节点的连接件指针
ptrItem: 当前节点连接件指针*/
LINKPTR GetTreeDataParentItem(LINKPTR ptrItem)
{
TreeItem* ptt;
LINKPTR parent;
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
/*取得该节点所在的根连接件指针*/
parent = GetRootLink(ptrItem);
assert(parent);
/*从孩子根连接件指针中恢复父节点数据*/
ptt = TreeItemFromChild(parent);
if(ptt->lkSibling.tag == lkTreeItem)
return &(ptt->lkSibling); /*该节点是一个数据节点*/
else
return NULL; /*该节点是一个根节点*/
}
/*取得后续兄弟节点的连接件指针
ptrItem: 当前节点的连接件指针*/
LINKPTR GetTreeDataNextSiblingItem(LINKPTR ptrItem)
{
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
return GetNextLink(ptrItem);
}
/*取得前趋兄弟节点的连接件指针
ptrItem: 当前节点的连接件指针*/
LINKPTR GetTreeDataPrevSiblingItem(LINKPTR ptrItem)
{
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
return GetPrevLink(ptrItem);
}
/*取得宿主中第一个根节点的连接件指针
ptrItem: 宿主连接件指针*/
LINKPTR GetTreeDataRootItem(LINKPTR ptrTree)
{
TreeData* ptd;
assert(ptrTree);
assert(ptrTree->tag == lkTreeData);
ptd = TreeDataFromLink(ptrTree);
return GetFirstLink(&ptd->lkItems);
}
/*设置节点的属性
ptrItem: 节点的连接件指针
szKey: 属性名称
keylen: 属性名称长度
szVal: 属性值
valen: 属性值长度*/
void WriteTreeDataItemProper(LINKPTR ptrItem,TCHAR* szKey,int keylen,TCHAR* szVal,int vallen)
{
TreeItem* ptt;
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
ptt = TreeItemFromLink(ptrItem);
/*添加属性至属性表*/
AddHashEntry(ptt->pht,(TCHAR*)szKey,keylen,(TCHAR*)szVal,vallen);
}
/*由属性名称检索属性值
ptrItem: 节点连接件指针
szKey: 属性名称
buf: 拷贝区
max: 拷贝区的最大字符数*/
int ReadTreeDataItemProper(LINKPTR ptrItem,const TCHAR* szKey,TCHAR* buf,int max)
{
TreeItem* ptt;
LINKPTR elk;
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
assert(buf && max >= 0);
ptt = TreeItemFromLink(ptrItem);
/*查找哈希表，是否有匹配的键*/
elk = GetHashEntry(ptt->pht,(TCHAR*)szKey,-1);
if(elk == NULL)
{
buf[0] = _T('\0');
return 0;
}else
{
return GetHashEntryVal(elk,buf,max);
}
}
/*由属性名称检索属性值字符串的指针
ptrItem: 节点连接件指针
szKey: 属性名称*/
TCHAR* GetTreeDataItemProperPtr(LINKPTR ptrItem,const TCHAR* szKey)
{
TreeItem* ptt;
LINKPTR elk;
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
assert(buf && max >= 0);
ptt = TreeItemFromLink(ptrItem);
/*查找哈希表，是否有匹配的键*/
elk = GetHashEntry(ptt->pht,(TCHAR*)szKey,-1);
if(elk == NULL)
{
return NULL;
}else
{
return GetHashEntryValPtr(elk);
}
}
/*由属性名称检索属性值字符串的长度
ptrItem: 节点连接件指针
szKey: 属性名称*/
int GetTreeDataItemProperLength(LINKPTR ptrItem,const TCHAR* szKey)
{
TreeItem* ptt;
LINKPTR elk;
TCHAR* tmp;
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
ptt = TreeItemFromLink(ptrItem);
/*查找哈希表，是否有匹配的键*/
elk = GetHashEntry(ptt->pht,(TCHAR*)szKey,-1);
if(elk == NULL)
return 0;
else
{
tmp = GetHashEntryValPtr(elk);
if(tmp == NULL)
return 0;
else
return _tcslen(tmp);
}
}
/*取得节点的长整型值
ptrItem: 节点连接件指针*/
unsigned long GetTreeDataItemData(LINKPTR ptrItem)
{
TreeItem* ptt;
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
ptt = TreeItemFromLink(ptrItem);
return ptt->data;
}
/*设置节点的长整型值
ptrItem: 节点连接件指针*/
void SetTreeDataItemData(LINKPTR ptrItem,unsigned long data)
{
TreeItem* ptt;
assert(ptrItem);
assert(ptrItem->tag == lkTreeItem);
ptt = TreeItemFromLink(ptrItem);
ptt->data = data;
}
3、由于树节点内置了动态属性表，增强了二叉分析树的通用性，在接下来的XML文档的解析自动机中，将有用武之地。
