Question

Construct 2 algorithms to make mirror image of any binary tree inputs, one of them using recursive method, another one using looping method. Mirror image means a binary tree that is the horizontal reflection of the original tree.

Solution

First, to do it in recursive method, we can perform pre-order traversal as usual, see preference. Then swap the left and right children for every node.

reflect(node)
  if node is null then return
  swap(node.left, node.right)
  if node.left is not null then reflect(node.left)
  if node.right is not null then reflect(node.right)

Second, to do it in looping method, we can make use of a stack. Put root node in the stack first. Then in a while-loop, as long as the stack isn’t empty, swap its children. Then put the children nodes into the stack.

reflect(root)
  if root is null then return
  stack.push(root)
  while stack is not empty, do
    node = stack.pop()
    swap(node.left, node.right)
    if node.left is not null then reflect(node.left)
    if node.right is not null then reflect(node.right)

Example

# node structure
class bst_node:
    value = None
    left = None
    right = None
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# swap node's children while visiting
def visit(node):
    temp = node.left
    node.left = node.right
    node.right = temp

# reflect a binary tree
def depth_first_traversal(node):
    if not node: return
    visit(node)
    if node.left: depth_first_traversal(node.left)
    if node.right: depth_first_traversal(node.right)

# debug function to print tree
def print_tree(node, indent=''):
    print "%s-%s" % (indent, node.value)
    if node.left: print_tree(node.left, indent + '  ')
    if node.right: print_tree(node.right, indent + '  ')

# a binary tree and display how was it before reflection
node_05 = bst_node(5)
node_07 = bst_node(7)
node_09 = bst_node(9)
node_11 = bst_node(11)
node_06 = bst_node(6,  node_05, node_07)
node_10 = bst_node(10, node_09, node_11)
node_08 = bst_node(8,  node_06, node_10)
root = node_08
print_tree(root)

# do reflection
depth_first_traversal(root)
print_tree(root)
# node structure
class bst_node:
    value = None
    left = None
    right = None
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# what to do in a loop, here swap the children
def visit(node):
    temp = node.left
    node.left = node.right
    node.right = temp

# reflect a binary tree
def depth_first_traversal(root):
    if not root: return
    stack = [root]
    while len(stack) > 0:
        node = stack.pop()
        visit(node)
        if node.left: stack.append(node.left)
        if node.right: stack.append(node.right)

# debug function to print tree
def print_tree(node, indent=''):
    print "%s-%s" % (indent, node.value)
    if node.left: print_tree(node.left, indent + '  ')
    if node.right: print_tree(node.right, indent + '  ')

# a binary tree and display how was it before reflection
node_05 = bst_node(5)
node_07 = bst_node(7)
node_09 = bst_node(9)
node_11 = bst_node(11)
node_06 = bst_node(6,  node_05, node_07)
node_10 = bst_node(10, node_09, node_11)
node_08 = bst_node(8,  node_06, node_10)
root = node_08
print_tree(root)

# do reflection
depth_first_traversal(root)
print_tree(root)
struct BSTreeNode // a node in the binary search tree (BST)
{
  int m_nValue; // value of node
  BSTreeNode *m_pLeft; // left child of node
  BSTreeNode *m_pRight; // right child of node
};
//就是递归翻转树,有子树则递归翻转子树。
//July、2010/10/19

void Revertsetree(list *root)
{
    if(!root)
       return;
    list *p;

    p=root->leftch;
    root->leftch=root->rightch;
    root->rightch=p;

    if(root->leftch)
      Revertsetree(root->leftch);
    if(root->rightch)
      Revertsetree(root->rightch);
}
void Revertsetree(list *phead)
{
    if(!phead)
       return;

    stack<list*> stacklist;
    stacklist.push(phead);         //首先把树的头结点放入栈中。

    while(stacklist.size())
    //在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树
    {
      list* pnode=stacklist.top();
      stacklist.pop();

      list *ptemp;
      ptemp=pnode->leftch;
      pnode->leftch=pnode->rightch;
      pnode->rightch=ptemp;

      if(pnode->leftch)
        stacklist.push(pnode->leftch);   //若有左子树,把它的左子树压入栈中
      if(pnode->rightch)
        stacklist.push(pnode->rightch);  //若有右子树,把它的右子树压入栈中
    }
}

Reference

Pre-order Tree Transversal (Wikipedia)

Leave a Reply

%d bloggers like this: