Sumedh

C code to convert a binary tree into a circular doubly linked list.




This problem uses uses pointers, binary trees, linked lists, and recursion.

Introduction

Ordered binary tree - Each node contains a single data element and left and right pointers. All the nodes on the left of the parent node are smaller or eqal to the parent node and all the nodes on the right are greater than the parent node.



Circular Doubly linked list - Like a normal doubly linked list each node has two pointers, the next pointer points to the next node and the previous pointer points to the previous node but there are two modifications. A circular doubly linked list does not terminate at the first and last nodes. The next pointer of the last node points to the first node and the previous pointer of the first node points to the last node. A list of one node is both the first and last node.



The nodes of the binary tree and circular list have the same structure. Each contains an data element and two pointers. The pointers in a tree are called as left and right and the pointer of the list are called next and previous.

Problem

Write a recursive function to convert an ordered binary tree by rearranging its internal pointers to make it a circular doubly linked list. The list should be in an ascending order. Return the head pointer of the list.




Copyright 2002 - 07 Sumedh K