第10题 把二元查找树转换成排序的双向链表

题目：把二元查找树转换成排序的双向链表

要求：不能创建任何新的节点，只调整指针的指向

10

/ \

6 14

/ \ / \

4 8 12 16

转成双向链表

4=6=8=12=14=16

关于此题, 有一篇非常详细的文档，把这个问题讲述的非常清楚，英文好的朋友可以看一下这篇文章

http://download.csdn.net/detail/stevemarbo/4094319

#include<stdio.h>
#include<stdlib.h>


// binary search tree
struct node {
	int data;
	struct node* small;
	struct node* large;
};

void join(struct node* a, struct node* b) {
	a->large = b;
	b->small = a;
}

struct node* append(struct node* a, struct node* b) {
	struct node* aLast;
	struct node* bLast;

	if(a == NULL)
		return b;
	if(b == NULL)
		return a;

	aLast = a->small;
	bLast = b->small;

	join(aLast, b);
	join(bLast, a);

	return a;
}

struct node* treeToList(struct node* root) {
	struct node* aList;
	struct node* bList;

	if(root == NULL)
		return NULL;

	aList = treeToList(root->small);
	bList = treeToList(root->large);

	root->small = root;
	root->large = root;

	aList = append(aList, root);
	bList = append(aList, bList);

	return aList;
}

struct node* newNode(int data) {
	struct node* n = (struct node *)malloc(sizeof(struct node));
	n->data = data;
	n->small = NULL;
	n->large = NULL;

		return n;
}


void treeInsert(struct node** rootRef, int data) {
	struct node* root = *rootRef;
	if(root == NULL)
		*rootRef = newNode(data);
	else {
		if(data <= root->data)
			treeInsert(&(root->small), data);
		else
			treeInsert(&(root->large), data);
	}
}

void printList(struct node* head) {
	struct node* current = head;

	while(current != NULL) {
		printf("%d ", current->data);
		current = current->large;
		if(current == head) break;
	}
	printf("\n");
}


int main() {
	struct node* root = NULL;
	struct node* head;

	treeInsert(&root, 4);
	treeInsert(&root, 2);
	treeInsert(&root, 1);
	treeInsert(&root, 3);
	treeInsert(&root, 5);

	head = treeToList(root);

	printList(head);
}