Posted on by

llyDUI 中的树形结构解析

《原创文章，转载请注明出处》
QQ: 745122346

一个 DUI中，需要一个树形结构，这个树形结构需要可以排序，遍历，并且有很好的性能。
我们采取如下的结构。

template<class T>
class llyDUI_TreeNode { 
public:
    llyDUI_TreeNode<T> *m_lpParent;
    llyDUI_TreeNode<T> *m_lpFirstChild, *m_lpLastChild;
    llyDUI_TreeNode<T> *m_lpPrevSibling, *m_lpNextSibling;
    T*    m_lpData;
    llyDUI_TreeNode(T& pData)
    {
        //assert(pData);
        m_lpParent = NULL;
         m_lpFirstChild = m_lpLastChild = m_lpPrevSibling = m_lpNextSibling = NULL;
         m_lpData = NULL;
        m_lpData = new T;
        if ( m_lpData )
            m_lpData–>Set(pData);
    }
    ~llyDUI_TreeNode()
    {
        if ( m_lpData )
            delete m_lpData;
    }
};

就几个 游标，指来指去。
我测了一下，100*100*100的数据量，从建树到遍历，总耗时是2496MS。还是debug的版本。
测试的文件如下：

template<class T>
class llyDUI_Tree
{
public:
    typedef    llyDUI_TreeNode<T>    CTreeNode;
    typedef CTreeNode*            HTreeNode;
public:
    llyDUI_Tree()
    {
        m_hRoot = NULL;
        m_hFeet = NULL;
    };
    virtual ~llyDUI_Tree()
    {
        HTreeNode hRoot = m_hRoot;
        HTreeNode hDel = hRoot;
        while ( hRoot )
        {
            hDel = hRoot;
            hRoot = hRoot–>m_lpNextSibling;
            
            HTreeNode hFirst = hDel–>m_lpFirstChild;
            while(hFirst)
            {
                HTreeNode hNext = hFirst–>m_lpNextSibling;
                DeleteChild(hFirst);
                hFirst = hNext;
            }
            if ( hDel–>m_lpData )
            {
#if ENABLE_TRACE
                ATLTRACE(_T(“delete root id=%d”),hDel–>m_lpData–>GetID());
#endif
            }
            delete hDel;
        }
    };
    llyVoid        DeleteChild(HTreeNode hChild)
    {
        if ( hChild == NULL )
            return ;
        HTreeNode hFirst = hChild–>m_lpFirstChild;
        while ( hFirst )
        {
            HTreeNode hNext = hFirst–>m_lpNextSibling;
            DeleteChild(hFirst);
            hFirst = hNext;
        }
        if ( hChild–>m_lpData )
        {
#if ENABLE_TRACE
            ATLTRACE(_T(“Delete Tree Node=%d\r\n”),hChild–>m_lpData–>GetID());
#endif
        }
        delete hChild;
        hChild = NULL;
    }
    HTreeNode    GetRoot()
    {
        return m_hRoot;
    };
    //! one tree has one root only
    HTreeNode    AddRoot(T& hRootData)
    {
        if ( m_hRoot )
        {
            HTreeNode pRoot = new CTreeNode(hRootData);
            if ( pRoot )
            {
                if ( m_hRoot == m_hFeet )
                {
                    m_hRoot–>m_lpNextSibling = pRoot;
                    pRoot–>m_lpPrevSibling = m_hRoot;
                    m_hFeet = pRoot;
                    return pRoot;
                }
                else if ( m_hFeet )
                {
                    m_hFeet–>m_lpNextSibling = pRoot;
                    pRoot–>m_lpPrevSibling = m_hFeet;
                    m_hFeet = pRoot;
                    return pRoot ;
                }
            }
        }
        assert(m_hRoot == NULL);
        if ( m_hRoot != NULL )
            return NULL;
        m_hRoot = new CTreeNode(hRootData);
        if ( m_hRoot == NULL )
            return NULL;
        InitRoot();
        m_hFeet = m_hRoot;
        return m_hRoot;
    }
    HTreeNode        AddChild(HTreeNode hParent,T& tChild)
    {
        if ( hParent == NULL /*|| tChild == NULL*/ )
            return NULL;
        HTreeNode hChild = new CTreeNode(tChild);
        if ( hChild == NULL )
            return NULL;
        return AddChild(hParent,hChild);
    }
    HTreeNode    AddChild(HTreeNode hParent,HTreeNode hChild)
    {
        assert(hParent!=NULL && hChild != NULL);
        if ( hParent == NULL || hChild == NULL )
            return hChild;
        hChild–>m_lpParent = hParent;
        HTreeNode hFirst = hParent–>m_lpFirstChild;
        if ( hFirst == NULL)
        {
            hParent–>m_lpFirstChild = hChild;
            hParent–>m_lpLastChild = hChild;
            hChild–>m_lpNextSibling = NULL;
            hChild–>m_lpPrevSibling = NULL;
            return hChild;
        }
        HTreeNode hLast = hParent–>m_lpLastChild;
        if ( hLast != NULL )
        {
            hParent–>m_lpLastChild = hChild;
            if ( hLast == hFirst )
            {
                hChild–>m_lpPrevSibling = hFirst;
                hFirst–>m_lpNextSibling = hChild;
                hChild–>m_lpNextSibling = NULL;
            }
            else
            {
                hChild–>m_lpPrevSibling = hLast;
                hLast–>m_lpNextSibling = hChild;
            }
        }
        return hChild;
    }
    llyVoid        DebugOutChild(HTreeNode hNode)
    {
        if ( hNode == NULL )
            return ;
        HTreeNode hChild = hNode–>m_lpFirstChild;
        while(hChild)
        {
            if ( hChild–>m_lpData )
            {
#if ENABLE_TRACE
                for ( int i=0;i<GetNodeLevel(hChild);i++)
                {
                    ATLTRACE(_T(“–“));
                    ;
                }
                ATLTRACE(_T(“DebugOut child=%d\r\n”),hChild–>m_lpData–>GetID());
#endif
                DebugOutChild(hChild–>m_lpFirstChild);
            }
            hChild = hChild–>m_lpNextSibling;
        }
    }
    llyVoid        DebugOut()
    {
        if ( m_hRoot == NULL )
            return ;
        HTreeNode    hRoot = m_hRoot;
        while ( hRoot )
        {
            T* lpData = hRoot–>m_lpData;
#if ENABLE_TRACE
            if ( lpData )
                ATLTRACE(_T(“DebugOut Root=%d\r\n”),lpData–>GetID());
#endif
            HTreeNode hChild = hRoot–>m_lpFirstChild;
            while (hChild)
            {
                if ( hChild–>m_lpData )
                {
#if ENABLE_TRACE
                    ATLTRACE(_T(“%d”),GetNodeLevel(hChild));
                    for ( int i=0;i<GetNodeLevel(hChild);i++)
                    {
                        ATLTRACE(_T(“–“));
                        ;
                    }
                    ATLTRACE(_T(“DebugOut child=%d\r\n”),hChild–>m_lpData–>GetID());
#endif
                    DebugOutChild(hChild);
                }
                hChild = hChild–>m_lpNextSibling;
            }
            hRoot = hRoot–>m_lpNextSibling;
        }
    }
    llyINT        GetNodeLevel(HTreeNode hNode)
    {
        //root level is 0
        llyINT nLevel = 0;
        if ( hNode )
        {
            HTreeNode hParent = hNode–>m_lpParent;
            while (hParent)
            {
                nLevel ++;
                hParent = hParent–>m_lpParent;
            }
        }
        return nLevel;
    }
protected:
    llyVoid InitRoot()
    {
        if ( m_hRoot )
            m_hRoot–>m_lpFirstChild = m_hRoot–>m_lpParent = m_hRoot–>m_lpLastChild = m_hRoot–>m_lpNextSibling = m_hRoot–>m_lpPrevSibling = NULL;
    }
    
protected:
    HTreeNode        m_hRoot; //top
    HTreeNode        m_hFeet; //bottom
};

 
上面是我实现的简单的模板，可以传入你自己想要的T, 对于DDUI来说，就是我们的一个Base class。
这个class可以是 NOVTABLE的。
 
下面我们来测试。 当然这个 Tree Node 只有一个成员，所以new的时间可能会少一点。
我没有算过new 1M 和 new 1K的时间有多少差距，但按照下面的来算。性能还是可以的。
但一个好的排序算法是最为关键的——以后会继续加入排序。

class CllyTreeNode 
{
public:
    CllyTreeNode()
    {
        
    }
    virtual ~CllyTreeNode()
    {
        
    }
    llyVoid        SetID(UINT nID)
    {
        m_nID = nID;
    }
    llyVoid        Set(CllyTreeNode& node)
    {
        m_nID = node.m_nID;
    }
    UINT        GetID()
    {
        return m_nID;
    }
protected:
    UINT m_nID;
};

 
我们的测试tree。
 

class llyTree_Test /*: public llyDUI_Tree<CllyTreeNode>*/
{
public:
    llyTree_Test()
    {
    }
    ~llyTree_Test()
    {
    }
    llyVoid DoTest()
    {
        typedef llyDUI_Tree<CllyTreeNode>    CTestTree;
        typedef CTestTree::HTreeNode HTreeNode;
        CTestTree testTree;
        //Node = 100 * 100 * 100  // 1M 的Node
   
        for ( int k=0;k<100;k++)
        {    
            CllyTreeNode rootNode;
            rootNode.SetID(100+k);
            HTreeNode hRoot = testTree.AddRoot(rootNode);
            if ( hRoot )
            {
                for ( int i=0;i<100;i++)
                {
                    CllyTreeNode rootChildNode;
                    rootChildNode.SetID(1001+i);
                    HTreeNode hRootChild = testTree.AddChild(hRoot,rootChildNode);
                    for ( int j = 0;j<100;j++)
                    {
                        CllyTreeNode rootChildNode1;
                        rootChildNode1.SetID(10001+i+j);
                        HTreeNode hRootChild1 = testTree.AddChild(hRootChild,rootChildNode1);
                    }
                }
            }
        }
        
        DWORD dwLast = GetTickCount();
        testTree.DebugOut();
        dwLast = GetTickCount() – dwLast;
          }
};

#endif
 
测试结果是 2496MS。
因为我们建树的时候 已经建立了 node 的 前 兄，后兄，父，第一个child 和 最后一个child。所以以后的操作会非常的简单。
看一个 节点的 层级数，我们约定 Root 是0 的话，如下代码，非常简单快速。
llyINT        GetNodeLevel(HTreeNode hNode)
    {
        //root level is 0
        llyINT nLevel = 0;
        if ( hNode )
        {
            HTreeNode hParent = hNode–>m_lpParent;
            while (hParent)
            {
                nLevel ++;
                hParent = hParent–>m_lpParent;
            }
        }
        return nLevel;
    }
接下来的工作是 把 Tree render 到一个 window上。
0
6 comments to “llyDUI 中的树形结构解析”

Comments are closed.