Depth First Traversal

Depth first traversal is the same as looping through all the elements in document order, i.e. the order you would encounter them reading from top to bottom. There are two common purposes for a traversal: one is for finding an element or elements anywhere in the document, the other is for processing the entire document to selectively copy out information.

Update July 12, 2005: Note that while evalutation version solutions are shown below, the CMarkup release 8.0 developer version supports finding anywhere in the document with xml.FindElem("//TAGNAME") and full depth first traversal with just while ( xmlFindElem("//*") ) as described in Paths In CMarkup.

To loop through every element in your XML document (see Simple Merge Example), you can use the following code. In the part of the code where you process the element, every element in the document (except the root element) will be encountered in depth first order. For illustrative purposes, it gets the tag name of the element.

BOOL bFinished = FALSE;
xml.ResetPos();
if ( ! xml.FindChildElem() )
    bFinished = TRUE;
while ( ! bFinished )
{
    // Process element
    xml.IntoElem();
    CString csTag = xml.GetTagName();

    // Next element (depth first)
    BOOL bFound = xml.FindChildElem();
    while ( ! bFound && ! bFinished )
    {
        if ( xml.OutOfElem() )
            bFound = xml.FindChildElem();
        else
            bFinished = TRUE;
    }
}

If you were just searching for a particular element tag name, in the code under the Process element remark you could compare to csTag and break out of the loop at that point. This would leave your current position at the desired element. You can use this code to create your own function which takes a CMarkup object reference and a tag name and returns with the position set if found.

The term "Depth first" comes from the fact that it traverses all of an element's children before going to its sibling (picture a mathematic tree where a node's children are down, parents are up, and siblings are across). See Navigating Levels in CMarkup for more information about going into and out of elements. The CMarkup download contains more examples of depth first traversal in CMarkupTest.cpp.