how to print tree non-recursively

[Daniel Shawul]

So my mind is stuck right now and I can't seem to convert a tail-recursive (I think) tree printing function to a recursive equivalent. It is supposed to print something like:

Code: Select all

1.e2e4 2.e7e5 3.d2d4
..............3.d2d3
..............3.a2a3
.......2.d7d5
.......2.d7d6
       ..
       ..
1.e2e3 2.e7e5
       2.d7d5

The nodes of the tree has child and sibling pointers, so in a recursive format the printing function is

Code: Select all

void print_node(Node* n) {
   Node* cur = n->child;
   while(cur) {
         if(cur->child)
              print_node(cur->child);
         else
              printf_with_proper_offset(cur);
         cur = cur->sibling;
   }
}

How do you convert that to iterative with out using a stack if possible ?

[Ron Murawski]

try Googling for:
"iterative tree traversal"
you might want to add one of the following terms:
in-order, pre-order, post-order, breadth-first etc

Most (all?) of the iterative methods I remember seeing use a stack to keep track. You can use a large-enough (over-sized) fixed-size array to hold a simulated stack, but I do not know if that approach will help you at all.

[Daniel Shawul]

Thanks for the suggestions. I thought it may be a tail recursive function , which doesn't need a stack, but I now see it is not. That forces me to use a stack for depth first traversal to print in that format. Breadth first traversal generates a bad tree format and still requires a queue data structure.
Problem is I am doing this on a gpu that don't support recursion and don't have stl. I don't want to implement a stack just for printing output. I managed to avoid recursion everywhere else but here.I guess I will have to copy the tree back to the cpu and use the recursive version there.

[hMx]

Try to lookup "dancing links" from Knuth

[Daniel Shawul]

Try to lookup "dancing links" from Knuth

It is not exactly what I wanted but nice algorithm though!
I have decided to use the recursive version until a suitable iterative version is found.

[Daniel Shawul]

I can't believe it but I may have found a solution without using a stack. It uses three (!) loops to do a depth first traversal. It is better to explain it by code so here it goes:

Code: Select all

__global__ 
void printTree() { 
      Node* current = root_node; 
      while(current) { 
         while(current) { 
            while(current) { 
               PRINT_WITH_FORMAT(); 
               //child 
               if(current->child) current = current->child; 
               else break; 
            } 
            //sibling 
            if(current->next) current = current->next; 
            else break; 
         } 
         //parent 
         if(current->parent) current = current->parent->next; 
         else break; 
      } 
   } 

Caution at the outer loop during backing up. We go to the parent and the sibling at once (two commands unlike the single one in the inner loops). Please let me know if you find problem with it. I have printed a tree with it but I am still not sure if it is bug free.

Edit: Yep it works correctly. I have modified it further to get the depth of the tree at any node. The width is a bit difficult because of that back up step I mentioned above. The width should be stored in a stack to resume where we left of before. Actually for my case I can calculate it indirectly from the address of contigious blocks of siblings but that is a hack. So the modified working code for depth changes and depth limit is:

Code: Select all

__global__ void printTree(int depthLimit) {
		int depth = 0;
		Node* current = root_node;
		while(current) {
			while(current) {
				while(current) {
					if(current->uct_visits) {
						for&#40;int i = 0;i < depth;i++)
							cuPrintf&#40;"\t");
						cuPrintf&#40;"%d. %d %d %.6f\n",
							depth,current->uct_wins,current->uct_visits,
							float&#40;current->uct_wins&#41; / current->uct_visits
							);
					&#125;
					//child
					if&#40;current->child && depth < depthLimit&#41; &#123;
						depth++;
						current = current->child;
					&#125; else break;
				&#125;
				//sibling
				if&#40;current->next&#41; &#123;
					current = current->next;
				&#125; else break;
			&#125;
			//parent
			if&#40;current->parent&#41; &#123;
				depth--;
				current = current->parent->next;
			&#125; else break;
		&#125;

		cuPrintf&#40;"Total nodes in tree&#58; %d\n",head - mem_);
	&#125;

And a partial result of a UCT tree like I wanted

Code: Select all

0. 25633078 46102528 0.556002
        1. 307115 688128 0.446305
                2. 96636 172032 0.561733
                2. 97952 172032 0.569382
                2. 97758 172032 0.568255
        1. 316998 688128 0.460667
                2. 96680 172032 0.561988
                2. 93590 172032 0.544027
                2. 94959 172032 0.551985
        1. 319653 688128 0.464525
                2. 98002 172032 0.569673
                2. 93706 172032 0.544701
                2. 92391 172032 0.537057
        1. 318789 688128 0.463270
                2. 98179 172032 0.570702
                2. 94831 172032 0.551241
                2. 92591 172032 0.538220
        1. 319246 688128 0.463934
                2. 97904 172032 0.569103
                2. 95177 172032 0.553252
                2. 92802 172032 0.539446
        1. 321420 688128 0.467093
                2. 96948 172032 0.563546
                2. 94361 172032 0.548508
                2. 92705 172032 0.538882
        1. 323445 688128 0.470036
                2. 96227 172032 0.559355
                2. 94062 172032 0.546770
                2. 92600 172032 0.538272
        1. 326112 688128 0.473912
                2. 96093 172032 0.558576
                2. 93268 172032 0.542155
                2. 92214 172032 0.536028
                        3. 966 2048 0.471680
        1. 300756 688128 0.437064
                2. 105769 172032 0.614822
                2. 98580 172032 0.573033
                2. 96993 172032 0.563808
        1. 290090 688128 0.421564

----
cheers

[Daniel Shawul]

There was a bug in backing up. It was only printing a segment of the whole tree. Now it required a goto. Maybe that can be avoided somehow..

Code: Select all

__global__ 
void printTree() { 
      Node* current = root_node; 
      while(current) { 
         while(current) { 
            while(current) { 
               PRINT_WITH_FORMAT(); 
               //child 
               if(current->child) current = current->child; 
               else break; 
            } 
NEXT: 
            //sibling 
            if(current->next) current = current->next; 
            else break; 
         } 
         //parent 
         if(current->parent) { 
              current = current->parent; 
              goto NEXT; 
         } else break; 
      } 
   } 

[Karlo Bala]

I found some old code, but I don't know if it is working.

Code: Select all

void PrintSubTree	(Node* current) 
{ 
	Node* parent = current->parent;
	while	(current	!=	parent)
	{
		if	(current->child)
			current	=	current->child;
		else	do
		{
			if	(current->next)
			{
				current	=	curent->next;
				break;
			}
			curent	=	curent->parent;
		}	while	(curent	!=	parent);
	}       
}

There was a bug in backing up. It was only printing a segment of the whole tree. Now it required a goto. Maybe that can be avoided somehow..

Code: Select all

__global__ 
void printTree() { 
      Node* current = root_node; 
      while(current) { 
         while(current) { 
            while(current) { 
               PRINT_WITH_FORMAT(); 
               //child 
               if(current->child) current = current->child; 
               else break; 
            } 
NEXT: 
            //sibling 
            if(current->next) current = current->next; 
            else break; 
         } 
         //parent 
         if(current->parent) { 
              current = current->parent; 
              goto NEXT; 
         } else break; 
      } 
   } 

[Daniel Shawul]

I found some old code, but I don't know if it is working.

Thanks Karlo! It seems to work. I counted the leaf nodes inside the inner loop and it gave same results

Code: Select all

Total nodes   : 254081
Leaf  nodes   : 249984
Maximum depth : 3
Average depth : 3.00

total karlo&#58; 249983  <<<<===

time 1375