|
|
#pragma once
|
|
|
#include <list>
|
|
|
using namespace std;
|
|
|
|
|
|
/************************************************************************
|
|
|
* Version : 1.0
|
|
|
* Date : 15 Nov 2016
|
|
|
* Description: 多叉树模板类
|
|
|
/************************************************************************/
|
|
|
|
|
|
template<class T>
|
|
|
class TTreeNode
|
|
|
{
|
|
|
public://methods
|
|
|
inline TTreeNode(void)
|
|
|
{
|
|
|
clear();
|
|
|
}
|
|
|
inline ~TTreeNode(void)
|
|
|
{
|
|
|
clear();
|
|
|
}
|
|
|
inline void clear(void)
|
|
|
{
|
|
|
pParent = 0;
|
|
|
children.clear();
|
|
|
}
|
|
|
|
|
|
inline void removeChild( TTreeNode* pChild)
|
|
|
{
|
|
|
pChild->pParent= 0;
|
|
|
children.remove(pChild);
|
|
|
}
|
|
|
//设置父节点
|
|
|
inline void setParent( TTreeNode* pNode)
|
|
|
{
|
|
|
//原父节点清空本节点
|
|
|
if(pParent != 0)
|
|
|
{
|
|
|
pParent->removeChild(this);
|
|
|
}
|
|
|
//设置新父节点
|
|
|
pParent = pNode;
|
|
|
|
|
|
if(0 != pParent)
|
|
|
pParent->children.push_back(this);
|
|
|
}
|
|
|
inline void addChild( TTreeNode* pNode)
|
|
|
{
|
|
|
pNode->setParent(this);
|
|
|
}
|
|
|
|
|
|
|
|
|
inline int childCount(void)
|
|
|
{
|
|
|
return children.size();
|
|
|
}
|
|
|
public: //members
|
|
|
TTreeNode* pParent;
|
|
|
T value;
|
|
|
list<TTreeNode*> children;
|
|
|
|
|
|
};
|
|
|
|
|
|
template <class T>
|
|
|
class TMultiTree
|
|
|
{
|
|
|
public:
|
|
|
inline TMultiTree(void):m_pRoot(0){}
|
|
|
inline virtual ~TMultiTree(void)
|
|
|
{
|
|
|
|
|
|
}
|
|
|
|
|
|
inline void SetRoot( TTreeNode<T>* pRoot) {
|
|
|
m_pRoot = pRoot;
|
|
|
if(m_pRoot)
|
|
|
m_pRoot->pParent = 0;
|
|
|
}
|
|
|
inline TTreeNode<T>* GetRoot(void) const {return m_pRoot; }
|
|
|
|
|
|
//向一棵树中添加子结点，pParent为插入位置,pNewNode为新插入的结点,函数指针为判断两个结点的上下级关系，
|
|
|
// 1为 pNode1 高于 pNode2 -1为 pNode1低于pNode2 0为平级 return true if succeed
|
|
|
inline bool InsertNode(TTreeNode<T>* pParent, TTreeNode<T>* pNewNode,int(*Compare)(const TTreeNode<T>* , const TTreeNode<T>* ))
|
|
|
{
|
|
|
if(0 == pParent)
|
|
|
return false;
|
|
|
if(pParent->childCount() < 1 )
|
|
|
{
|
|
|
pParent->addChild(pNewNode);
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
typename list<TTreeNode<T>*>::iterator iter = pParent->children.begin();
|
|
|
vector<TTreeNode<T>*> newChildren; //新添加点的子孩子
|
|
|
int rst = 0;
|
|
|
for(; iter != pParent->children.end(); iter ++ )
|
|
|
{
|
|
|
rst = Compare(*iter,pNewNode);
|
|
|
if(1 == rst) //*iter比newNode的级别高
|
|
|
return InsertNode(*iter,pNewNode,Compare );
|
|
|
else if(-1 == rst) //newNode比*iter级别高
|
|
|
{
|
|
|
newChildren.push_back(*iter);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//将newChildren中元素从原来子结点移除，添加到pnewNode的子结点中
|
|
|
for(int i = 0; i < (int)newChildren.size(); i ++ )
|
|
|
{
|
|
|
pParent->removeChild(newChildren[i]);
|
|
|
pNewNode->addChild(newChildren[i]);
|
|
|
}
|
|
|
|
|
|
pParent->addChild(pNewNode);
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
|
|
|
protected:
|
|
|
TTreeNode<T>* m_pRoot; //根结点
|
|
|
|
|
|
|
|
|
};
|
|
|
|