#=====================================================================
# Author: Isai Damier
# Title: BST to Circular Doubly Linked List (Recursive)
# Project: geekviewpoint
# Package: algorithms
#
# Description: Convert a BST into a circular doubly LinkedList.
#
# Technical Details: This is a recursive method for converting a BST
# into a cyclic doubly LinkedList. This is not the only recursive
# method around. This method however inculcates the truth that python
# does not pass by reference. The lists head = {None} and
# tail = {None} are necessary handles for tracking both the head and
# the tail of the LinkedList. (A good alternative might be to have
# the recursive function return a value.)
#
#=====================================================================
class BST( object ):
def __init__( self ):
self.root = None
def getRoot( self ):
return self.root
def toCircularDoublyLinkedList_recursive( self ):
head, tail = [None], [None]
self._toCircularDoublyLinkedList_recursive( self.root, head, tail )
if head[0] is not None:
tail[0].right = head[0]
head[0].left = tail[0]
return head[0]
def _toCircularDoublyLinkedList_recursive( self, n, h, t ):
if n is None:
return
# left
if n.left is not None:
self._toCircularDoublyLinkedList_recursive( n.left, h, t )
# visit
if h[0] is None:
h[0] = t[0] = n
else:
t[0].right = n # link right
n.left = t[0] # link left
t[0] = t[0].right # reassign tail
self._toCircularDoublyLinkedList_recursive( n.right, h, t );
import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
#====================================================================
# Description: Test the toCircularDoublyLinkedList_recursive function.
# The trick here is to avoid falling into an endless loop as the tree
# is now a circular structure with no definite end points.
#
# Technical Details: From a testing viewpoint
# toCircularDoublyLinkedList_iterative and
# toCircularDoublyLinkedList_recursive are essentially equivalent.
#====================================================================
def testToCircularDoublyLinkedList_recursive( self ):
bst = BST()
treeTape = [200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
175, 225, 275, 325, 375, 35, 212, 312, 400]
self.assertIsNone( bst.toCircularDoublyLinkedList_recursive() )
# set expectation
ino = [35, 25, 75, 50, 125, 175, 150, 100, 212, 225, 275, 250,
312, 325, 400, 375, 350, 300, 200]
ino.sort() # mergesort: like inorder
# load data into tree
for i in treeTape:
bst.add( i )
self.assertEquals( len( treeTape ), bst.size() ) # has correct size
# test toCircularDoublyLinkedList_recursive
head = bst.toCircularDoublyLinkedList_recursive()
tmp = head
i = 0
while True:
self.assertEquals( int ( ino[i] ), int( tmp.data ) )
i += 1
tmp = tmp.right
if tmp.right == head:
break
# calling on size() below would be disastrous: circular!
self.assertEquals( i + 1, len( treeTape ) )
