Swapping Left and Right Children in a Binary Tree (Recursive and Iterative Methods)

Swapping the left and right children of a binary tree (using recursive and non-recursive methods).

2011-10-14 8:35

Swapping the left and right children of a binary tree (using recursive and non-recursive methods).

Recursive version:

void change( BTree * pTree )  
{  
if( NULL == pTree )  
return;  
BTree * pTemp = pTree->left;  
pTree-> left = pTree-> right;  
pTree-> right= pTemp;  
change( pTree-> left );  
change( pTree-> right );  
}

===================== Using a Queue =====================

Algorithm idea:

1. Enqueue the root node, i.e., add it to the end of the queue.
2. Dequeue a node, i.e., remove an element from the front of the queue.
3. Swap the left and right children of the dequeued node, then enqueue them sequentially.
4. If the queue is not empty, repeat steps 2 and 3.

Author: Liu Huaxi

The iterative version is as follows, using a queue:

void change( BTree * pTree )  
{  
if( NULL == pTree )  
return;  
queue <BTree*> qu;  
qu.push(pTree);  
BTree*pTree2 = null;  
while(!qu.empty()){  
pTree2= qu.front( );  
qu.pop();  
BTree * pTemp = pTree2-> left;  
pTree2-> left = pTree2-> right;  
pTree2-> right= pTemp;  
if(pTree2-> left!=null)  
qu.push(pTree2-> left);  
if(pTree2-> right!=null)  
qu.push(pTree2-> right);  
  
}  
  
}