Solved

Print Balanced Tree nodes using level order traversal  from bottom up

Posted on 2007-12-04
17
2,366 Views
Last Modified: 2008-06-11
Hi..I have a balanced tree like this:
        1
   2         3
5   6     7   8

I have the following code to print level order traversal from top to bottom (ie. 1235678) . The code uses a queue to print it. However, how can I modify the code as to NOT use recursion and NOT use an extra datastructure (like the array queue which I am using), but still print the tree bottom up in a level order traversal ? The output should be something like this:

5678231

// Level order traversal..
void levelOrderTraversal(mynode *root)
{
  mynode *queue[100] = {(mynode *)0}; // Important to initialize!
  int size = 0;
  int queue_pointer = 0;
 
  while(root)
  {
      printf("[%d] ", root->value);

      if(root->left)
      {
        queue[size++] = root->left;
      }

      if(root->right)
      {
        queue[size++] = root->right;
      }
     
      root = queue[queue_pointer++];    
  }
}


Thanks
0
Comment
Question by:niftyhawk
  • 6
  • 5
  • 5
  • +1
17 Comments
 
LVL 28

Expert Comment

by:pepr
ID: 20409566
I do not know what is the motivation for searching the solution. I also do not know what that kind of traversal is good for. I have never saw the need for that kind of traversal. Also the nodes do not seem to be orderded the way that is usual when using binary trees. You should possibly tell more details about the purpose.

Anyway, I think that your solution of the problem is almost optimal and I can see no way how to do it without some extra data structure. I even cannot see how that traversal would be done recursively (but I may be blind). The reasons are:

1. Whenever you traverse a binary tree, the only nodes that are available immediately (if they exist) are the left node and the right node.

2. Every traversal at least at some point jumps to a node that is other than described in point 1.

3. Every traversal needs a kind of jump-back-to-the-previously-processed-node or near to it. This way, the previous or near position must be remembered somehow. Or in the form of hidden stack when solving it recursively, or in the form of the application-level stack when removing recursion, or in some other form.

4. This traversal does not fit with the recursive definition of a binary tree (i.e. "Binary tree is empty or it has the root node with left and right subtrees."). The recursive traversals always process the node, the left tree and the right tree. Only the order of the three operations makes them different. Your traversal cannot be expressed this way. Because of that I believe it cannot be solved recursively.

Short summary: Any tree traversal needs extra memory -- or hidden when doing it recursively, or in explicitly defined data structures.

If the program can use C++ and not C only, I would only suggest one enhancement to your code -- using std::queue<mynode *> for implementing the queue.
0
 
LVL 28

Expert Comment

by:pepr
ID: 20409712
Here is the sample that uses the mentioned std::queue. The good thing is that there is no restriction to number of levels (even though the balanced tree would not have too many levels). Also, I prefer explicit testing against NULL. But it is a matter of taste.
#include <queue>

#include <iostream>
 

using namespace std;
 

class mynode

{

public:

    mynode(int val, mynode * L, mynode * R)

    {

        value = val;

        left = L;

        right = R;

    }

 

    int value;

    mynode * left;

    mynode * right;

};
 
 

void levelOrderTraversal(mynode *root)

{

    queue<mynode *> q;

 

    while (root != NULL)

    {

        cout << "[" << root->value << "] ";
 

        if (root->left != NULL)

        {

            q.push(root->left);

        }
 

        if (root->right != NULL)

        {

            q.push(root->right);

        }

     

        if ( ! q.empty())

        {

            root = q.front();

            q.pop();

        }

        else

        {

            root = NULL;

        }    

    }

}
 
 

void deleteTree(mynode *root)

{

    if (root != NULL)

    {

        deleteTree(root->left);

        deleteTree(root->right);

        delete root;

    }

}
 
 

int main ()

{

    // Building the tree.

    mynode * p5 = new mynode(5, NULL, NULL);

    mynode * p6 = new mynode(6, NULL, NULL);

    mynode * p7 = new mynode(7, NULL, NULL);

    mynode * p8 = new mynode(8, NULL, NULL);
 

    mynode * p2 = new mynode(2, p5, p6);

    mynode * p3 = new mynode(3, p7, p8);
 

    mynode * root = new mynode(1, p2, p3);
 

    // Do the traversal.

    levelOrderTraversal(root);
 

    // Delete the tree recursively.

    deleteTree(root);
 

    return 0;

}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20409904
If you add a pointer-to-parent and pointer-to-next-sibling to the nodes, you can easily do it without recursion or an extra container.
Just simply descend to the lowest level, and print that level using the pointer-to-next-sibling's, then go up to the previous level using the pointer-to-parent of the leftmost sibling.

This basically keeps a tree within the tree, where the bottom left node is the "root" ...
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20410095
>>>> If you add a pointer-to-parent and pointer-to-next-sibling to the nodes

You can do it without these additional pointers:

For level traversion a binary tree can be displayed like

                      1
           2                          3
      4          5            6            7
  8      9   A     B     C    D     E       F

Using binary numbers instead of hex we get

 
                             0001
              0010                             0011
     0100          0101           0110         0111
1000 1001 1010 1011   1100 1101 1110 1111


Given an arbitrary position (number), e. g.  D == 1101, we can traverse to that position by checking the bits of that number. The most left '1' means that we were at level 3, the next '1' mean that we have to take the right child pointer from root (pos 3 == 0011) , the next '0' means, that we go left (pos 6 == 0110) and the last '1' means that we go right after that. Found. If any node on the way was NULL we break cause the branch doesn't exist then.  

The code for that would be like (I assumed you know the depth of the tree somehow)
 
for (l = depth; l >= 0; --l)
{
    for (k = 1<<l; k < (1<<(l+1)); k++)
    {  
        mynode* next = root;
        for (n = 1; n < l; ++n)
        {
            if (k & (1<<(l - n)))
            {
                 if (!next->right)
                 {
                     cout << "- ";
                     return;
                 }
                 next = next->right;
             }
             else
            {
                  // do the same for left side
                  ....
            }
        }
               
    }
     if (next != NULL)
          cout << next->data << " ";
     else
          // print empty node "- "
          ...
}


The most outer loop iterates all levels (reverse), the next loop iterates all positions within one level, the next loop iterates up to the current level, deciding whether to go left or right by checking the appropriate bit of the position (1-based) to look for. If there was no break, it finally found the node searched for.

Regards, Alex
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20410200
Interesting idea, Alex. To make it work good, you can store the nodes in an array, with the binary position value as index.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20410254
>>>> To make it work good, you can store the nodes in an array
Yes, you would have a direct access to all nodes with that. However,  the requirements here were to not using an extra data structure and - beside of traversing - there is no real benefit when doing so, e. g. for seeking a value in the tree. Of course you could 'calculate' the 'approximate' position of a value by comparing with the min and max (the positions are 1<<(depth-1) and (1<<depth) -1, then correct the 'approximation' by comparing with the approximated node, and so on. But I fear that method is slower than a normal binary search ...

I have good experiences by using a sorted array instead of a binary tree. The binary search is as fast as in a binary tree and in case of 'growing' keys, e. g. date-based keys or id numbers, you mostly will insert at end of the array so that the costs for inserting were comparable with that of a binary tree.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20410293
>> However,  the requirements here were to not using an extra data structure and - beside of traversing - there is no real benefit when doing so, e. g. for seeking a value in the tree.

What I meant was to store the nodes in an array, indexed on your position value, but still keep the normal left and right child node pointers.

So, this example tree :

          1
     2        3

would look like :

        --------
    ---|   1   |---
    |   --------   |
    ->|   2   |   |
        --------   |
        |   3   |<-
        --------

etc. Keeping the tree balanced when inserting or removing nodes becomes a harder task though, but looking up nodes and printing in the required order becomes easier.
0
 
LVL 28

Expert Comment

by:pepr
ID: 20410353
Infinity08> If you add a pointer-to-parent and pointer-to-next-sibling to the nodes, you can easily do it without recursion or an extra container.

Yes. But the extra pointer is a kind of distributed extra data structure. The main problem is how difficult it would be to fill the extra pointer. Insertion can be very costly. Also ballancing the tree (if required) means updating the extra pointers.  It works with what I have heard named "monkey-puzzle tree" where the extra pointer reflects the in-order traversal. However, it would be costly operation in the above case.
0
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 
LVL 53

Expert Comment

by:Infinity08
ID: 20410378
I agree, pepr, insertion and deletion will indeed be more costly ... but at the moment you want to look for a node, or print all nodes, there will be no performance impact, and no need to create an extra data structure.

A lot depends on the ratio of lookups versus inserts/deletes. If that ratio is sufficiently high, then the method I described is a good alternative.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20410407
>>>> The main problem is how difficult it would be to fill the extra pointer.
>>>> Insertion can be very costly.
I have a tree with that spec. It is not a binary tree as each node can have an arbitrary count of siblings. The management of the extra pointers is a minor thing compared to the advantages regarding traversing and balancing.

The tree was used as a baseclass for a FileTree wiith (nested) folders and files.

Regards, Alex



#ifndef TREE_HPP

#define TREE_HPP
 

// project includes
 

// basis types and macros

#ifndef BASTYPES_HPP

   #include <bastypes.hpp>

#endif
 

// handle concurrency in a multithreading environment

#ifndef MUTEX_HPP

   #include <mutex.hpp>

#endif
 

// dynamic array collecion

#ifndef HAT_HPP

    #include <hat.hpp>

#endif
 

// string class 

#ifndef STRING_HPP

    #include <string.hpp>

#endif
 

// forward declaration
 

template <class TNodeData, class TLeafData>

class Tree;
 

template <class TNodeData, class TLeafData>

class TreeIterator;
 

template <class TNodeData, class TLeafData>

class TreeNode;
 

template <class TNodeData, class TLeafData>

class TreeLeaf;
 

// macros for easier template type declaration
 

#define TreeItemPtr                 TreeItem*

#define TreeNodePtr                 TreeNode<TNodeData, TLeafData>*

#define TreeLeafPtr                 TreeLeaf<TNodeData, TLeafData>*

#define TreePtr                     Tree<TNodeData, TLeafData>*

#define TreeRef                     Tree<TNodeData, TLeafData>&

#define TreeIteratorPtr             TreeIterator<TNodeData, TLeafData>*

#define TreeIteratorRef             TreeIterator<TNodeData, TLeafData>&
 

// default macros

#ifndef DEFAULT_PATH_SEPARATOR

    #define DEFAULT_PATH_SEPARATOR      '/'

#endif
 

// macros for easier code reading

#define HANDLE_CHAIN_TRUE           True

#define HANDLE_CHAIN_FALSE          False

#define IS_TREE_OWNER_TRUE          True

#define IS_TREE_OWNER_FALSE         False

#define IS_DATA_OWNER_TRUE          True

#define IS_DATA_OWNER_FALSE         False

#define LOOK_IN_SUB_TRUE            True

#define LOOK_IN_SUB_FALSE           False

#define GOTO_NEXT_LEAF_TRUE         True

#define GOTO_NEXT_LEAF_FALSE        False

#define START_ITERATION_TRUE        True

#define START_ITERATION_FALSE       False

#define INCLUDE_LEAFS_FALSE         False

#define INCLUDE_LEAFS_TRUE          True

#define FORWARD_TRUE                True
 

/////////////////////////////////////////////////////////////////////////////

// @doc   Tree

//
 
 

// @class Base class for elements of a tree. A TreeItem holds pointers to the parent, previous and next tree element 

//
 

class TreeItem

{

// @dataprivate

private:

    // Attributes

    String               m_key;         // @cmember item key (should be unique for all siblings)

    TreeItemPtr          m_pParent;     // @cmember pointer to parent node item or NULL if root

    TreeItemPtr          m_pPrev;       // @cmember pointer to previous item of the same level or NULL if first

    TreeItemPtr          m_pNext;       // @cmember pointer to next item of the same level or NULL if last
 

// @funcpublic

public:

    // constructors, destructor
 

    // @cmember constructor for any item, node or leaf; 

    TreeItem(const String& key, TreeItemPtr pParent=NULL, TreeItemPtr pPrev=NULL, TreeItemPtr pNext=NULL);

    // @cmember destructor makes nothing; data must be deleted before destructing (by tree)

    virtual ~TreeItem();
 

public:

    // @cmember get key

    String                      getKey()

        { return m_key; }
 

protected:

    // @cmember get parent node 

    TreeItemPtr                 getParent()

        { return m_pParent; }

    // @cmember get previous child 

    TreeItemPtr                 getPrev()

        { return m_pPrev; }

    // @cmember get next child 

    TreeItemPtr                 getNext()

        { return m_pNext; }

    // @cmember get path

    String                      getPath(Char cPathSeparator);

    // @cmember set new parent node and return old one

    TreeItemPtr                 setParent(TreeItemPtr pParent)

        { TreeItemPtr pOld = m_pParent; m_pParent = pParent; return pOld; }

    // @cmember set new backward pointer for level chain and return old one

    TreeItemPtr                 setPrev(TreeItemPtr pPrev, Bool handleChain = True)

        { TreeItemPtr pOld = m_pPrev; m_pPrev = pPrev; 

          if (handleChain) 

          { if (pOld != NULL)  { pOld->m_pNext = pPrev; } 

            if (pPrev != NULL) { pPrev->m_pPrev = pOld; pPrev->m_pNext = this; }

          }

          return pOld; 

        }

    // @cmember set new forward pointer for level chain and return old one

    TreeItemPtr                 setNext(TreeItemPtr pNext, Bool handleChain = True)

        { TreeItemPtr pOld = m_pNext; m_pNext = pNext; 

          if (handleChain) 

          { if (pOld != NULL)  { pOld->m_pPrev = pNext; }

            if (pNext != NULL) { pNext->m_pNext = pOld; pNext->m_pPrev = this; }  

          }

          return pOld; 

        }

    // @cmember remove from same level chain

    Void                        chainOut()

        {   if (m_pPrev != NULL) { m_pPrev->m_pNext = m_pNext; }  // chain left sibling (if any) to right one

            if (m_pNext != NULL) { m_pNext->m_pPrev = m_pPrev; }  // chain right sibling (if any) to left one

        }

    // @cmember set new key

    String                      setKey(const String& key)

        { String oldKey = m_key; m_key = key; return oldKey; }
 

};
 

/////////////////////////////////////////////////////////////////////////////

// @doc   TreeNode

//

// @class  Derived class of class TreeItem to hold nodes. A node is a tree item  

//   <nl>  that may be parent of a list of leafs and/or parent of a list of

//         child nodes, Nodes and leafs may associate different data types

//
 

template <class TNodeData, class TLeafData>

class TreeNode  : public TreeItem

{

// @dataprivate

private:

    // Attributes

    TNodeData*           m_pData;        // @cmember pointer to data

    TreeNodePtr          m_pFirstKid;    // @cmember pointer to first child node or NULL if last level

    TreeNodePtr          m_pLastKid;     // @cmember pointer to last child node or NULL if last level

    TreeLeafPtr          m_pFirstLeaf;   // @cmember pointer to first leaf or NULL if no leafs

    TreeLeafPtr          m_pLastLeaf;    // @cmember pointer to last leaf or NULL if no leafs
 

// @funcpublic

public:

    // constructors, destructor
 

    // @cmember constructor for node; gets node data, parent and left and right sibling

    TreeNode(const String& nodeName,  TreeNodePtr pParent=NULL,

             TreeNodePtr pPrev=NULL,  TreeNodePtr pNext=NULL,   TNodeData* pNodeData=NULL

             );

    // @cmember destructor deletes the array (chain) but not the data

    virtual ~TreeNode();
 

private:

    // @cmember delete data if a tree item owns its data; the ownership property is 

    //          a property of the whole tree rather than of a single tree item

    Void                        deleteData();
 

public:

    // @cmember get data pointer

    TNodeData*                  getData()

        { return m_pData; }

    // @cmember get parent node 

    TreeNodePtr                 getParent()

        { return (TreeNodePtr)TreeItem::getParent(); }

    // @cmember get previous child 

    TreeNodePtr                 getPrev()

        { return (TreeNodePtr)TreeItem::getPrev(); }

    // @cmember get next child 

    TreeNodePtr                 getNext()

        { return (TreeNodePtr)TreeItem::getNext(); }

    // @cmember get first child 

    TreeNodePtr                 getFirstKid()

        { return m_pFirstKid; }

    // @cmember get last child 

    TreeNodePtr                 getLastKid()

        { return m_pLastKid; }

    // @cmember get first leaf 

    TreeLeafPtr                 getFirstLeaf()

        { return m_pFirstLeaf; }

    // @cmember get last leaf 

    TreeLeafPtr                 getLastLeaf()

        { return m_pLastLeaf; }

    // @cmember check for next level 

    Bool                        hasKids()

        { return m_pLastKid != NULL; }

    // @cmember check for leafs 

    Bool                        hasLeafs()

        { return m_pLastLeaf != NULL; }
 

    // @cmember set new data pointer and return olds one

    TNodeData*                  setData(TNodeData* pData)

        { TNodeData* pOld = m_pData; m_pData = pData; return pOld; }

    // @cmember set new parent pointer for level chain and return old one

    TreeNodePtr                 setParent(TreeNodePtr pParent)

        { return (TreeNodePtr)TreeItem::setParent(pParent); }

    // @cmember set new backward pointer for level chain and return old one

    TreeNodePtr                 setPrev(TreeNodePtr pPrev, Bool handleChain = True)

        { TreeNodePtr pOld = (TreeNodePtr)TreeItem::setPrev(pPrev, handleChain); 

          if (handleChain)

          {  TreeNodePtr pPar = getParent();

             if (pOld == NULL && pPar != NULL) { pPar->m_pFirstKid = pPrev; }

          }

          return pOld;

        }

    // @cmember set new forward pointer for level chain and return old one

    TreeNodePtr                 setNext(TreeNodePtr pNext, Bool handleChain = True)

        { TreeNodePtr pOld = (TreeNodePtr)TreeItem::setNext(pNext, handleChain);

          if (handleChain)

          { TreeNodePtr pPar = getParent();

            if (pOld == NULL && pPar != NULL) { pPar->m_pLastKid = pNext; }

          }

          return pOld;

        }

    // @cmember remove from same level chain

    Void                        chainOut()

    { TreeNodePtr pParent = getParent();

      if (pParent != NULL) 

      { if (pParent->m_pFirstKid == this) { pParent->m_pFirstKid = getNext(); }

        if (pParent->m_pLastKid == this)  { pParent->m_pLastKid  = getPrev(); } 

      }

      TreeItem::chainOut();

    }

    // @cmember set new start pointer for level chain and return old one

    TreeNodePtr                 setFirstKid(TreeNodePtr pFirstKid)

        { TreeNodePtr pOld = m_pFirstKid; m_pFirstKid = pFirstKid; return pOld; }

    // @cmember set new last pointer for level chain and return old one

    TreeNodePtr                 setLastKid(TreeNodePtr pLastKid)

        { TreeNodePtr pOld = m_pLastKid; m_pLastKid = pLastKid; return pOld; }

    // @cmember set new start pointer for leaf chain and return old one

    TreeLeafPtr                 setFirstLeaf(TreeLeafPtr pFirstLeaf)

        { TreeLeafPtr pOld = m_pFirstLeaf; m_pFirstLeaf = pFirstLeaf; return pOld; }

    // @cmember set new last pointer for leaf chain and return old one

    TreeLeafPtr                 setLastLeaf(TreeLeafPtr pLastLeaf)

        { TreeLeafPtr pOld = m_pLastLeaf; m_pLastLeaf = pLastLeaf; return pOld; }
 

    friend class TreeLeaf<TNodeData, TLeafData>;

    friend class Tree<TNodeData, TLeafData>;

};
 

/////////////////////////////////////////////////////////////////////////////

// @doc   TreeLeaf

//

// @class  Derived class of class TreeItem to hold leafs. A leaf is a child   

//   <nl>  tree item that has no child items
 

template <class TNodeData, class TLeafData>

class TreeLeaf  : public TreeItem

{

// @dataprivate

private:

    // Attributes

    TLeafData*                  m_pData;       // @cmember pointer to data
 

// @funcpublic

public:

    // constructors, destructor
 

    // @cmember constructor for node; gets all linked tree items

    TreeLeaf(const String& leafName, TreeNodePtr pParent, TreeLeafPtr pPrev=NULL, TreeLeafPtr pNext=NULL, TLeafData* pLeafData=NULL );

    // @cmember destructor deletes the array (chain) but not the data

    virtual ~TreeLeaf();
 

private:

    // @cmember delete data if a tree item owns its data; the ownership property is 

    //          a property of the whole tree rather than of a single tree item

    Void                        deleteData();
 

public:

    // @cmember get data pointer

    TLeafData*                  getData()

        { return m_pData; }

    // @cmember get parent node 

    TreeNodePtr                 getParent()

    { return (TreeNodePtr)TreeItem::getParent(); }

    // @cmember get previous child 

    TreeLeafPtr                 getPrev()

        { return (TreeLeafPtr)TreeItem::getPrev(); }

    // @cmember get next child 

    TreeLeafPtr                 getNext()

        { return (TreeLeafPtr)TreeItem::getNext(); }

    // @cmember set new data pointer and return olds one

    TLeafData*                  setData(TLeafData* pData)

        { TLeafData* pOld = m_pData; m_pData = pData; return pOld; }

    // @cmember set new parent pointer for level chain and return old one

    TreeNodePtr                 setParent(TreeNodePtr pParent)

        { return (TreeNodePtr)TreeItem::setParent(pParent); }

    // @cmember set new backward pointer for level chain and return old one

    TreeLeafPtr                 setPrev(TreeLeafPtr pPrev, Bool handleChain = True)

        { TreeLeafPtr pOld = (TreeLeafPtr)TreeItem::setPrev(pPrev, handleChain);

          if (handleChain)

          { TreeNodePtr pPar = getParent();

            if (pOld == NULL && pPar != NULL) { pPar->m_pFirstLeaf = pPrev; }

          }

          return pOld;

        }

    // @cmember set new forward pointer for level chain and return old one

    TreeLeafPtr                 setNext(TreeLeafPtr pNext, Bool handleChain = True)

        { TreeLeafPtr pOld = (TreeLeafPtr)TreeItem::setNext(pNext, handleChain);

          if (handleChain)

          { TreeNodePtr pPar = getParent();

            if (pOld == NULL && pPar != NULL) { pPar->m_pLastLeaf = pNext; }

          }

          return pOld;

        }

    // @cmember remove from same level chain

    Void                        chainOut()

    { TreeNodePtr pParent = getParent();

      if (pParent->m_pFirstLeaf == this) { pParent->m_pFirstLeaf = getNext(); }

      if (pParent->m_pLastLeaf == this)  { pParent->m_pLastLeaf  = getPrev(); } 

      TreeItem::chainOut();

    }
 

    friend class TreeNode<TNodeData, TLeafData>;

    friend class Tree<TNodeData, TLeafData>;

};
 

/////////////////////////////////////////////////////////////////////////////

// @class  Tree

//   <nl>  Collection class to handle a tree with nodes and leafs where any  

//   <nl>  node may be (unique) parent of a list of nodes and/or a list of leafs,

//   <nl>  e.g. the directory and file tree of a hierarchical file system 
 

template <class TNodeData, class TLeafData>

class Tree

{

// @dataprivate

private:

    // Attributes
 

    // @cmember pointer of the root node

    TreeNodePtr             m_pRoot;

    // @cmember indicates that the tree is owner of all its tree items, thus is responsible for deletion

    Bool                    m_isTreeOwner;  

    // @cmember indicates that any tree item deletes its data when destructed

    Bool                    m_isDataOwner;  

    // @cmember list of iterators currently operating on this tree

    Hat<TreeIteratorPtr>    m_iteratorList;
 

// @funcpublic

public:

    // constructors, destructor
 

    // @cmember constructor for tree; gets root data 

    Tree(const String& rootName, TNodeData* pRootData=NULL, Bool isTreeOwner=True, Bool isDataOwner=True);
 

private:

    // @cmember constructor for tree; gets root data pointer

    Tree(TreeNodePtr pRoot);
 

public:

    // @cmember destructor deletes items and data depending on ownership

    virtual ~Tree();
 

public:

    // @cmember get root data 

    TNodeData*                  getRootData()

        { return (m_pRoot == NULL)? NULL : m_pRoot->getData(); }

    // @cmember check if data owner

    Bool                        isDataOwner()

        {   return m_isDataOwner; }

    // @cmember check if tree owner

    Bool                        isTreeOwner()

        {   return m_isTreeOwner; }

    // @cmember check if tree is empty ( having no nodes or only the root node)

    Bool                        isEmpty()

        {   return ( m_pRoot == NULL || ( !( m_pRoot->hasKids() && ! m_pRoot->hasLeafs() ) ) ); }
 

private:

    // @cmember get root node 

    TreeNodePtr                 getRoot()

        { return m_pRoot; }

    // @cmember set root node  

    TreeNodePtr                 setRoot(TreeNodePtr pRoot, Bool isTreeOwner=True, Bool isDataOwner=True);

    // @cmember add new iterator to iterator list

    int                         registerIterator(TreeIteratorPtr pIterator)

        {  int idx = m_iteratorList.index(pIterator); return (idx >= 0)? idx : m_iteratorList.append(pIterator); } 

    // @cmember remove iterator from iterator list

    int                         unregisterIterator(TreeIteratorPtr pIterator)

        {  int idx = m_iteratorList.index(pIterator); if (idx >= 0 ) { m_iteratorList.removeAt(idx); } return idx; } 

    // @cmember notify any concurrent iterator when a node or leaf was deleted

    Bool                        notifyDeletion(TreeIteratorPtr pIterator, TreeNodePtr pItemDeleted);

    // @cmember notify any concurrent iterator when a leaf was deleted

    Bool                        notifyDeletion(TreeIteratorPtr pIterator, TreeLeafPtr pItemDeleted);

    // @cmember get any concurrent iterator to notify when a node or leaf was deleted 

    TreeIteratorPtr             getNextConcurrentIterator(TreeIteratorPtr pInitiator, int& nextIndex);
 

    friend class TreeIterator<TNodeData, TLeafData>;

};
 
 

/////////////////////////////////////////////////////////////////////////////

// @class  TreeIterator

//   <nl>  Operates on a tree with nodes and leafs where any  

//   <nl>  node may be (unique) parent of a list of nodes and/or a list of leafs,

//   <nl>  e.g. the directory and file tree of a hierarchical file system 
 

template <class TNodeData, class TLeafData>

class TreeIterator

{

// @dataprivate

private:

    // Attributes
 

    // @cmember tree to iterate on

    TreeRef                     m_tree;

    // @cmember current node

    TreeNodePtr                 m_pCurNode;

    // @cmember current leaf    

    TreeLeafPtr                 m_pCurLeaf;
 

// @funcpublic

public:

    // constructors, destructor
 

    // @cmember constructor for tree iterator; gets reference of the associated tree

    TreeIterator(TreeRef tree)

        : m_tree(tree), m_pCurNode(tree.getRoot()), m_pCurLeaf(NULL) 

        { m_tree.registerIterator(this); }
 

    // @cmember copy constructor for tree iterator

    TreeIterator(TreeIteratorRef iterRef)

        : m_tree(iterRef.m_tree), m_pCurNode(iterRef.m_pCurNode), m_pCurLeaf(iterRef.m_pCurLeaf)

        { m_tree.registerIterator(this); }
 

    // @cmember destructor notifies the tree

    virtual ~TreeIterator() { m_tree.unregisterIterator(this); }
 

public:

    // basic tree operations
 

    // @enum direction modes to iterate within tree

    enum TreeDirection 

    { 

        CURRENT,                // @emem no move

        UP,                     // @emem to parent node

        PREVIOUS,               // @emem to previous (left) sibling

        NEXT,                   // @emem to next (right) sibling

        FIRST_CHILD,            // @emem down to first sub node

        LAST_CHILD,             // @emem down to last sub node

        FORWARD,                // @emem forward in preorder (left down .. left down - right .. right - up - right - again)

        BACK                    // @emem back in preorder (left .. left - up - left - right down .. right down - again)

    };
 

    // @cmember set root node current (cd \)

    Bool                        gotoRoot()

        {  m_pCurNode = m_tree.getRoot();   m_pCurLeaf = NULL;  return (m_pCurNode != NULL); }          

    // @cmember set parent node current (cd ..)

    Bool                        gotoParent()

        {  m_pCurNode = m_pCurNode->getParent();  m_pCurLeaf = NULL;  return (m_pCurNode != NULL); }

    // @cmember find node by node data; search starts at current node

    Bool                        findNodeByData(TNodeData* pNodeData);

    // @cmember find node by name; search starts at current node; wildcards * and ? are allowed

    Bool                        findNodeByName(const String& searchName, Bool lookInSub=True);

    // @cmember find node by path; search starts at current node; wildcards are NOT allowed

    Bool                        findNodeByPath(const String& searchPath);

    // @cmember get name of current node; 

    String                      getCurrentNodeName() const;

    // @cmember get level of current node; 

    Int                         getCurrentNodeLevel() const;

    // @cmember get name of current leaf

    String                      getCurrentLeafName() const;

    // @cmember get node data 

    TNodeData*                  getCurrentNodeData() const;

    // @cemmber check if leaf is current

    Bool                        hasCurrentLeaf() const

        {  return m_pCurLeaf != NULL && (m_pCurLeaf->getParent() == m_pCurNode); }

    // @cmember check for younger brother

    Bool                        hasCurrentLeftNode() const

        {  return (m_pCurNode != NULL)? (m_pCurNode->getPrev() != NULL) : False; }

    // @cmember check for elder brother

    Bool                        hasCurrentRightNode() const

        {  return (m_pCurNode != NULL)? (m_pCurNode->getNext() != NULL) : False; }

    // @cmember check for children

    Bool                        hasCurrentKids() const

        {  return (m_pCurNode != NULL)? (m_pCurNode->getFirstKid() != NULL) : False; }

    // @cmember get path string of current node; the path string contains all node names of the parent up chain  

    //          beginning with the root node name and separated by the iterators path separator character e.g. '\'

    String                      getCurrentPath(Char cPathSeparator) const;

    // @cmember add next node to current chain

    Bool                        addNode(const String& name, TNodeData* pNodeData);

    // @cmember add to next level chain

    Bool                        addKid(const String& name, TNodeData* pNodeData);

    // @cmember insert node before current node 

    Bool                        insertNode(const String& name, TNodeData* pNodeData);

    // @cmember add leaf to current node

    Bool                        addLeaf(const String& name, TLeafData* pLeafData);

    // @cmember add leaf to parent node

    Bool                        addLeafToParent(const String& name, TLeafData* pLeafData);

    // @cmember insert leaf before current leaf

    Bool                        insertLeaf(const String& name, TLeafData* pLeafData);

    // @cmember delete current node

    Bool                        deleteCurrentNode(TreeDirection gotoAfterDelete=BACK);

    // @cmember delete current leaf

    Bool                        deleteCurrentLeaf(Bool gotoNextLeaf=True);

    // @cmember goto last node of (sub-)tree beginning at current node

    Void                        gotoLastNode();

    // @cmember goto next node in preorder (son, brother, uncle, grand uncle, ...)

    //  direction is forward or backward; search starts at current node or last node if backward     

    Bool                        gotoNextInPreorder(Bool startIteration, Bool includeLeafs = INCLUDE_LEAFS_FALSE);

    // @cmember goto previous node in preorder (son, brother, uncle, grand uncle, ...)

    //  direction is backward; search starts at last node and stops at current node

    Bool                        gotoPrevInPreorder(Bool startIteration, Bool includeLeafs = INCLUDE_LEAFS_FALSE);

    // @cmember go relatively to current node

    Bool                        gotoNode(TreeDirection direction = NEXT );

// @funcprivate

private:

    // @cmember iterator gets notified that a node was deleted

    Void                        notifyDeletion(TreeNodePtr pItemDeleted);

    // @cmember iterator gets notified that a leaf was deleted

    Void                        notifyDeletion(TreeLeafPtr pItemDeleted);

};
 

/////////////////////////////////////////////////////////////////////////////

// @class  TreeQuery

//   <nl>  Operates on a tree with nodes and leafs where any  

//   <nl>  node may be (unique) parent of a list of nodes and/or a list of leafs,

//   <nl>  e.g. the directory and file tree of a hierarchical file system 
 

template <class TNodeData, class TLeafData>

class TreeQuery

{

// @dataprivate

private:

    // Attributes
 

    // @cmember tree to iterate on

    TreeRef                     m_tree;
 

// @funcpublic

public:

    // constructors, destructor
 

    // @cmember constructor for tree iterator; gets reference of the associated tree

    TreeQuery(TreeRef tree);

};

#endif

Open in new window

0
 
LVL 28

Expert Comment

by:pepr
ID: 20410410
Infinity08> What I meant was to store the nodes in an array...

I am not sure the original intention but your suggestion may be close to the implementation of a ballanced binary tree in an array that is used by Heap sort algorithm. See

http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation
http://en.wikipedia.org/wiki/Heap_sort

The level order traversal is then simply iteration through the elements of the array from zero to max. Indices of the levels can also be easily computed.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20410412
>> A lot depends on the ratio of lookups versus inserts/deletes. If that ratio is sufficiently high, then the method I described is a good alternative.

Btw, that's often the case for a binary tree ... a lot more lookups than inserts ... ie. fill it once, then consult it often.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20410438
>>>> What I meant was to store the nodes in an array,
Yes, so did I understand it.  But I still see no benefits if doing so beside of the level traversion.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20410473
>> But I still see no benefits if doing so beside of the level traversion.

Which is what the question is about ;) But I agree :)
0
 
LVL 28

Expert Comment

by:pepr
ID: 20410624
Hi Alex. You are right. It depends on where the extra pointer points to. All of this depends also on the original intention of niftyhawk.
0
 
LVL 1

Author Comment

by:niftyhawk
ID: 20414992
Alex>> for (l = depth; l >= 0; --l)
{
    for (k = 1<<l; k < (1<<(l+1)); k++)
    {  
        mynode* next = root;
        for (n = 1; n < l; ++n)
        {
            if (k & (1<<(l - n)))
            {
       ..............

I think your solution is what I am really looking for. It is an iterative solution with no extra data structure. However, I am new to bitwise shifting and am confused. I didn't understand why you considered binary representation and why bitwise shifting was needed. Can't it be done without bitwise shifting considering the tree has all integers or strings?
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 500 total points
ID: 20417870
>>>> for (l = depth; l >= 0; --l)

the outer loop goes from depth (== deepest level, in my sample depth == 3) to 0. The last iteration would assign root to next and print root data.

>>>>    for (k = 1<<l; k < (1<<(l+1)); k++)

1<<l   shifts the bits of the number 1 (1 == 00000001 in binary representation) l positions to the left. '1' has only one bit, the lowest bit at the right, so the result in binary is (for l == 3)  00001000, what is 8 in decimal. So, bit-shifting the 1 to the left for l positions is equivalent to taking 2 to the power of l:  2^3 == 8. That is what I intended. If you look at the binominal tree, you see that the first number of each level is a power of 2. Hence (1<<l) can be used to calulate the first position in that level.  Same happens with   (1<<(l+1)). Here I calculate the next power, thus getting an upper boundary for the iteration at the current level.

>>>>        mynode* next = root;
to search the node for the current level position I have to start at the top again.

>>>>        for (n = 1; n < l; ++n)
The loop runs from 1 to the current level, in the sample it runs from 1 to 3, what is 3 times. Starting from root I hvae to change the level 3 times to come down to the current level.


>>>>            if (k & (1<<(l - n)))
Now, it gets nifty.  'k' is the position I want to look-up. The binary representation of   that number tells now, whether i have to go left or right in the binary tree:

 
                             0001
              0010                             0011
     0100          0101           0110         0111
1000 1001 1010 1011   1100 1101 1110 1111

Look at the most left branch. It was a left shift of the most significant bit of the root. The left child of root has a 0 bit at the most right pos. Looking at the subtree where that child is root of, you see that the 0 bit was moved to pos 2 (we always count from the right when talking from bits and starting with base = 0) for all items of the bottom level. Check the right subtree and you see that all numbers of the bottom level have a 1 bit at pos 2. So, that bit 2 determines whether I have to go left or right when starting from root. The same happens one level deeper now it is the bit at pos1 of the bottom level numbers which says whether to go right or left, and finally it is the bit 0 which says what to when branching to the bottom level.

>>>>            if (k & (1<<(l - n)))

Coming back to the statement. (1<<(l - n)) raises 2 to the power of (l-n) as discussed above. We have l  == 3 and n == 1 at begin, so we have 4 == 0100 for  (1<<(l - n)) . That exactly is bit 2 (the 3rd from the right). The '&' operator compares bits and, if we have 1101 & 0100, the result is
0100 as only that bit will get 1 where both operands have a 1 as well. The & operator therefore is used to 'test' whether a bit at a given position was set or not.

 'if (k & (1<<(l - n)))' checks whether the given k (0xD == 1101) has the bit at pos l-n  (== 2) set, and the result is non-zero, what means 'true'. So, the if condition is true and we goon turning to the right subtree. for the next iteration n was 2, so l-n is 1, and we are testing bit 1 of theoriginal number, whether to go right or left. The bit is 0, so we go left. Finally we test for bit 0 what is 1 and go right and have our number found...

Regards, Alex
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now