tree.h

游戏开发数据结构Data Structures for Game Programmers

        ResetIterator();
    }


// ----------------------------------------------------------------
//  Name:           Up
//  Description:    moves the iterator up by one level of the tree
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void Up()
    {
        if( m_node != 0 )
        {
            m_node = m_node->m_parent;
        }
        ResetIterator();
    }


// ----------------------------------------------------------------
//  Name:           Down
//  Description:    moves the iterator down one level, so that it
//                  points to the current child
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void Down()
    {
        if( m_childitr.Valid() )
        {
            m_node = m_childitr.Item();
            ResetIterator();
        }
    }


// ----------------------------------------------------------------
//  Name:           ChildForth
//  Description:    Moves the child iterator forward
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void ChildForth()
    {
        m_childitr.Forth();
    }

// ----------------------------------------------------------------
//  Name:           ChildBack
//  Description:    Moves the child iterator back
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void ChildBack()
    {
        m_childitr.Back();
    }

    
// ----------------------------------------------------------------
//  Name:           ChildStart
//  Description:    moves the child iterator to the first child
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void ChildStart()
    {
        m_childitr.Start();
    }


// ----------------------------------------------------------------
//  Name:           ChildEnd
//  Description:    Moves the child iterator to the last child
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void ChildEnd()
    {
        m_childitr.End();
    }

// ----------------------------------------------------------------
//  Name:           ChildValid
//  Description:    determines if the child iterator is valid
//  Arguments:      None
//  Return Value:   true if valid.
// ----------------------------------------------------------------
    bool ChildValid()
    {
        return m_childitr.Valid();
    }


// ----------------------------------------------------------------
//  Name:           ChildItem
//  Description:    returns the item the child pointer points to
//  Arguments:      None
//  Return Value:   reference to the item
// ----------------------------------------------------------------
    DataType& ChildItem()
    {
        return m_childitr.Item()->m_data;
    }


// ----------------------------------------------------------------
//  Name:           AppendChild
//  Description:    appends a child to the child list
//  Arguments:      p_node: node to append
//  Return Value:   None
// ----------------------------------------------------------------
    void AppendChild( Node* p_node )
    {
        if( m_node != 0 )
        {
            m_node->m_children.Append( p_node );
            p_node->m_parent = m_node;
        }
    }

// ----------------------------------------------------------------
//  Name:           PrependChild
//  Description:    prepends a child to the child list
//  Arguments:      p_node node to prepend
//  Return Value:   None
// ----------------------------------------------------------------
    void PrependChild( Node* p_node )
    {
        if( m_node != 0 )
        {
            m_node->m_children.Prepend( p_node );
            p_node->m_parent = m_node;
        }
    }


// ----------------------------------------------------------------
//  Name:           InsertChildBefore
//  Description:    inserts a new node before the current child
//  Arguments:      p_node: node to insert
//  Return Value:   None
// ----------------------------------------------------------------
    void InsertChildBefore( Node* p_node )
    {
        if( m_node != 0 )
        {
            m_node->m_children.InsertBefore( m_childitr, p_node );
            p_node->m_parent = m_node;
        }
    }

// ----------------------------------------------------------------
//  Name:           InsertChildAfter
//  Description:    inserts a new node after the current child
//  Arguments:      p_node: node to insert
//  Return Value:   None
// ----------------------------------------------------------------
    void InsertChildAfter( Node* p_node )
    {
        if( m_node != 0 )
        {
            m_node->m_children.InsertAfter( m_childitr, p_node );
            p_node->m_parent = m_node;
        }
    }

// ----------------------------------------------------------------
//  Name:           RemoveChild
//  Description:    removes the current child from the tree. Doesn't
//                  delete the node.
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void RemoveChild()
    {
        if( m_node != 0 && m_childitr.Valid() )
        {
            m_childitr.Item()->m_parent = 0;
            m_node->m_children.Remove( m_childitr );
        }
    }


// ----------------------------------------------------------------
//  Name:           ResetIterator
//  Description:    resets the child iterator, so that it points
//                  to the right linked list
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void ResetIterator()
    {
        if( m_node != 0 )
        {
            m_childitr = m_node->m_children.GetIterator();
        }
        else
        {
            m_childitr.m_list = 0;
            m_childitr.m_node = 0;
        }
    }
};



// ----------------------------------------------------------------
//  Name:           Preorder
//  Description:    performs a preorder traversal on a tree
//  Arguments:      p_node: node to start traversing at
//                  p_process: function that processes the node
//  Return Value:   None
// ----------------------------------------------------------------
template <class DataType>
void Preorder( Tree<DataType>* p_node, void (*p_process)(Tree<DataType>*) )
{
    // process the current node
    p_process( p_node );

    // loop through each child and process it
    DListIterator<Tree<DataType>*> itr = p_node->m_children.GetIterator();
    for( itr.Start(); itr.Valid(); itr.Forth() )
        Preorder( itr.Item(), p_process );
}


// ----------------------------------------------------------------
//  Name:           Postorder
//  Description:    performs a postorder traversal on a tree
//  Arguments:      p_node: node to start traversing at
//                  p_process: function that processes the node
//  Return Value:   None
// ----------------------------------------------------------------
template <class DataType>
void Postorder( Tree<DataType>* p_node, void (*p_process)(Tree<DataType>*) )
{
    // loop through each child and process it
    DListIterator<Tree<DataType>*> itr = p_node->m_children.GetIterator();
    for( itr.Start(); itr.Valid(); itr.Forth() )
        Postorder( itr.Item(), p_process );

    // process the current node
    p_process( p_node );
}

#endif