How to convert a binary search tree into a doubly linked list?
Given a binary search tree, i need to convert it into a doubly linked list(by traversing in zig zag order) using only pointers to structures in C++ as follows,
Given Tree:
1
|
+-------+---------+
| |
2 3
| |
+----+---+ +----+---+
| | | |
4 5 6 7
| | | |
+--+--+ +--+--+ +--+--+ +--+--+
开发者_运维知识库| | | | | | | |
8 9 10 11 12 13 14 15
Node Structure:
struct node
{
char * data;
node * left;
node * right;
};
Create List(zig zag order):
1 <-> 3 <-> 2 <-> 4 <-> 5 <-> 6 <-> 7 <-> 15 <-> ... <-> 8
Could someone please help me out.
This is a Breadth-first search algorithm. Wikipedia has a good explanation on how to implement it.
After implementing the algorithm, creating your linked list should be a no-brainer (since it will only be a matter of appending each visited element to the list)
That's an awkward type of tree traversal. I wonder how often anyone has ever actually needed to do such a thing in real code. Nevertheless, it's the problem to be solved here...
Here's how I would approach dealing with this:
First, when I compare the desired output to the structure of the tree, I notice that each "level" of the tree is processed in turn from top to bottom. So top node first, then all child nodes, then all grand-child notes, and so on. So probably a good solution will involve a loop that processes one level and at the same time builds up a list of nodes in the next level to be used in the next iteration of the loop.
Next, this "zig zag" order means it needs to alternate which direction the child nodes are processed in. If a particular iteration goes from left to right, then the next iteration must go from right to left. And then back to left to right for the subsequent iteration and so on. So in my idea of a loop that processes one level and builds a list of the next level, it probably needs to have some sort of alternating behavior when it builds that list of nodes for the next level. On even iterations the list is built one way. On odd iterations the list is built the other way.
Alternatively, another other way to think about this whole thing is: Design a solution to that can build the result list in 1,2,3,4,5,6,etc order. Then modify that design to have the zig zag order.
Does this give you enough of an idea on how to design a solution?
This might help you:
- Create a separate list for every level of the tree
- Traverse the tree and copy the values to the lists as you traverse the tree
- Reverse the order of every other list
- Connect the lists
In this solution below I have used two stacks to store Levels alternatively. say nodes at level 0 will be store in stack 1 whose name is head1;now pop the element while it not become empty and push the elements in stack 2.the order i.e left or right child of insertion will depend on the level.and change the insertion order at each level.
node * convert_to_dll(node *p)
{
static int level=0;
push_in_stack(p,&head1);
printf("%d\n",p->data);
while( head1!=NULL || head2!=NULL) {
//pop_from_queue(&headq);
if(head1!=NULL && head2==NULL) {
while(head1!=NULL) {
if(level%2==0) {
node *p;
p=new node;
p=pop_from_stack(&head1);
if(p->right!=NULL) {
push_in_stack(p->right,&head2);
printf("%d\n",(p->right)->data);
}
if(p->left!=NULL)
{
push_in_stack(p->left,&head2);
printf("%d\n",(p->left)->data);
}
}
}
//traverse_stack(head2);
level++;
} else {
while(head2!=NULL) {
if(level%2!=0) {
node *q;
q=new node;
q=pop_from_stack(&head2);
if(q->left!=NULL) {
push_in_stack(q->left,&head1);
printf("%d\n",(q->left)->data);
}
if(q->right!=NULL) {
push_in_stack(q->right,&head1);
printf("%d\n",(q->right)->data);
}
}
} //traverse_stack(head2);
level++;
}
}
return p;
}
you can write a function to add nodes in a doubly linked list. You can then call this function while traversing the tree. In this way you should be able to do it.
Hmm... This is a tough one. The problem with traversal in this order is that you are doing a lot of skipping around. This is generally true in any tree traversal order that is not depth or breadth first.
Here's how I would resolve the situation. Start with a single, empty array of lists of nodes and begin traversing the tree depth first. Be sure to keep track of the depth of your traversal.
At each point in traversal, note the depth of your traversal and pick the list at the index in the array. If there isn't one there, add it first. If the depth is even (Assuming root has depth 0), add the node to the end of the list. If it's odd, add it to the beginning.
Once you've traversed all nodes, concatenate the lists.
Why use pointers?? You could just store your BST as an array A[1...n]. So, A[1] would have root, A[2] and A[3] would have nodes of the depth 1, etc. This is possible since it is an almost complete tree, and you know how many elements will be present at a given depth - i.e. 2^d at depth d (except of course at the last depth). Now all you've got to do is access the array in a zag-zag manner, and create a new BST (array) of the new order. So, how would you traverse the array in a zig-zag manner?? For any given element A[i], the left child would be A[2i] and the right child A[2i + 1]. So, if your current depth d is odd, then traverse 2^d elements, and when you reach the 2^dth element, go to its left child. If your current depth d is even, again traverse 2^d elements, but when you reach the 2^dth element, go to its right child. Storing them as arrays rather than nodes makes your data structure leaner, and your implementation simpler.
This ( http://cslibrary.stanford.edu/109/TreeListRecursion.html) has the answer with pretty pictures :)
#include<iostream>
#include<conio.h>
using namespace std;
class TreeNode
{
public:
int info;
TreeNode* right;
TreeNode* left;
//TreeNode* parent;
TreeNode()
{
info = 0;
right = left = NULL;
}
TreeNode(int info)
{
this -> info = info;
right = left = NULL;
}
};
class ListNode
{
public:
int info;
ListNode* next;
ListNode()
{
info = 0;
next = NULL;
}
ListNode(int info)
{
this -> info = info;
next = NULL;
}
};
TreeNode* root = NULL;
ListNode* start;
ListNode* end;
void addTreeNode(TreeNode*);
void convertTreeToList(TreeNode*);
void printList(ListNode*);
int findDepth(TreeNode*);
int _tmain(int argc, _TCHAR* argv[])
{
start = end = new ListNode(0);
char choice = 'y';
int info;
while(choice == 'y')
{
cout<<"Enter the info of new node:\n";
cin>>info;
addTreeNode(new TreeNode(info));
cout<<"Want to add a new node to the tree?(y/n)\n";
cin>>choice;
}
cout<<"Depth of the tree is: "<<findDepth(root);
cout<<"Converting the tree into a doubly linked list....\n";
convertTreeToList(root);
printList(start->next);
cin>>choice;
return 0;
}
void addTreeNode(TreeNode* node)
{
if(!root)
{
root = node;
}
else
{
TreeNode* currRoot = root;
while(1)
{
if(node -> info >= currRoot -> info)
{
if(!currRoot -> right)
{
currRoot -> right = node;
break;
}
else
{
currRoot = currRoot -> right;
}
}
else
{
if(!currRoot -> left)
{
currRoot -> left = node;
break;
}
else
{
currRoot = currRoot -> left;
}
}
}
}
}
void convertTreeToList(TreeNode* node)
{
if(node -> left != NULL)
{
convertTreeToList(node -> left);
}
end ->next = new ListNode(node -> info);
end = end -> next;
end -> next = start;
if(node -> right != NULL)
{
convertTreeToList(node -> right);
}
}
void printList(ListNode* start)
{
while(start != ::start)
{
cout<<start->info<<" -> ";
start = start -> next;
}
cout<<"x";
}
int findDepth(TreeNode* node)
{
if(!node)
{
return 0;
}
else
{
return (max(findDepth(node -> left), findDepth(node -> right)) + 1);
}
}
Linked list you get here is singly linked and sorted. Hope you can easily make changes in this code to get a doubly linked list. Just copy - paste this code and compile it.It will work fine.
Let us assume that the root of the binary tree is at level 0(an even number). Successive levels can be considered as alternating between odd even (children of root are at odd level, their children are at even level etc.). For a node at even level, we push its children onto a stack(This enables reverse traversal). For a node at odd level, we push its children onto a queue(This enables forward traversal). After children have been pushed, we remove the next available element (top of stack or front of queue) and recursively call the function by changing level to odd or even depending on where the removed element lies. The removed element can be inserted at the end of the doubly linked list. Pseudo-code below.
// S = stack [accessible globally]
// Q = queue [accessible globally]
//
// No error checking for some corner cases to retain clarity of original idea
void LinkNodes(Tree *T,bool isEven,list** l)
{
if(isEven) {
S.push(T->right);
S.push(T->left);
while( !S.empty() ) {
t = S.pop();
InsertIntoLinkedList(l,t);
LinkNodes(t,!isEven);
}
} else {
Q.enque(T->left);
Q.enque(T->right);
while( !Q.empty() ) {
t = Q.deque();
InsertIntoLinkedList(l,t);
LinkNodes(t,isEven);
}
}
}
In the calling function:
bool isEven = true;
list *l = NULL;
// Before the function is called, list is initialized with root element
InsertIntoLinkedList(&l,T);
LinkNodes(T,isEven,&l);
/* * File: main.cpp * Author: viswesn * * Created on December 1, 2010, 4:01 PM */
struct node {
int item;
struct node *left;
struct node *right;
struct node *next;
struct node *prev;
};
struct node *dlist = NULL;
struct node *R = NULL;
struct node* EQueue[10] = {'\0'};
int Etop = 0;
struct node* OQueue[10] = {'\0'};
int Otop = 0;
int level=-1;
struct node *insert(struct node *R, int item)
{
struct node *temp = NULL;
if (R != NULL) {
if (item < R->item) {
R->left = insert(R->left, item);
} else {
R->right = insert(R->right, item);
}
} else {
temp = (struct node *)malloc(sizeof(struct node));
if (temp == NULL) {
return NULL;
}
temp->item = item;
temp->left = NULL;
temp->right = NULL;
temp->next = NULL;
temp->prev = NULL;
R = temp;
}
return R;
}
void print(struct node *node)
{
if (node != NULL) {
print(node->left);
printf("%d<->", node->item);
print(node->right);
}
}
void EvenEnqueue(struct node *item) {
if (Etop > 10) {
printf("Issue in EvenEnqueue\n");
return;
}
EQueue[Etop] = item;
Etop++;
}
void OddEnqueue(struct node *item)
{
if (Otop > 10){
printf("Issue in OddEnqueue\n");
return;
}
OQueue[Otop] = item;
Otop++;
}
int isEvenQueueEmpty() {
if (EQueue[0] == '\0') {
return 1;
}
return 0;
}
int isOddQueueEmpty()
{
if (OQueue[0] == '\0') {
return 1;
}
return 0;
}
void EvenDQueue()
{
int i = 0;
for(i=0; i< Etop; i++)
EQueue[i]='\0';
Etop = 0;
}
void OddDQueue()
{
int i = 0;
for(i=0; i< Otop; i++)
OQueue[i]='\0';
Otop = 0;
}
void addList() {
int counter = 0;
struct node *item = NULL;
if (level%2 == 0) {
/* Its Even level*/
while(counter < Etop)
{
struct node *t1 = EQueue[counter];
struct node *t2 = EQueue[counter+1];
if ((t1!=NULL) && (t2!=NULL)) {
t1->next = t2;
t2->prev = t1;
}
counter++;
}
item = EQueue[0];
} else {
/* Its odd level */
while(counter < Otop)
{
struct node *t1 = OQueue[counter];
struct node *t2 = OQueue[counter+1];
if ((t1!=NULL) && (t2!=NULL)) {
t2->next = t1;
t1->prev = t2;
}
counter++;
}
item = OQueue[Otop-1];
}
if(dlist !=NULL) {
dlist->next = item;
}
item->prev = dlist;
if (level%2 == 0) {
dlist = EQueue[Etop-1];
} else {
dlist = OQueue[0];
}
}
void printTree()
{
int nodeCount = 0;
int counter = 0;
if (!isEvenQueueEmpty()) {
/* If even level queue is not empty */
level++;
nodeCount = pow(2,level);
printf("[");
while(counter < nodeCount) {
if (EQueue[counter] != '\0') {
struct node *t = EQueue[counter];
printf("%d<->", t->item);
if (t->left != NULL)
OddEnqueue(t->left);
if (t->right != NULL)
OddEnqueue(t->right);
} else {
break;
}
counter++;
}
addList();
printf("]");
EvenDQueue();
}
counter = 0;
if (!isOddQueueEmpty()){
/* If odd level queue is not empty */
level++;
nodeCount = pow(2,level);
printf("[");
while(counter < nodeCount){
if (OQueue[counter] != '\0') {
struct node *t = OQueue[counter];
printf("%d<->", t->item);
if (t->left != NULL)
EvenEnqueue(t->left);
if (t->right != NULL)
EvenEnqueue(t->right);
} else {
break;
}
counter++;
}
addList();
printf("]");
OddDQueue();
}
if (isEvenQueueEmpty() && isOddQueueEmpty()){
return;
}
else {
printTree();
}
}
void printLevel(struct node *node)
{
if (node == NULL)
return;
EvenEnqueue(node);
printTree();
printf("\n");
}
void printList(struct node *item)
{
while(item!=NULL) {
printf("%d->", item->item);
item = item->next;
}
}
int main(int argc, char** argv) {
int a[]={20,30,40,12,2,15,18};
int size = sizeof(a)/sizeof(int);
int i = 0;
for(i=0; i< size; i++) {
R = insert(R, a[i]);
}
printf("Inoder traversal - Binary tree\n");
print(R);
printf("\n\n");
printf("Level traversal - Binary tree\n");
printLevel(R);
printf("\n");
printf("Double link list traversal - Binary tree\n");
printList(R);
printf("\n");
return 0;
}
加载中,请稍侯......
精彩评论