---------------------------------------------------------------------------
将一棵二叉搜索树转换为有序链表。
/***************************************************************************
* Description:
* 将一棵二叉搜索树转换为有序链表
* Author : wplxb
* Language: C
* Date : 2007-11-01
***************************************************************************/
#include <stdio.h>
typedef struct node
{
int d;
struct node * l;
struct node * r;
} * node;
/* 中序遍历框架。 */
node convert(node h)
{
static node head = NULL; /* 最终返回的头指针。 */
static node tail = NULL; /* 尾指针，始终指向当前构建好的链表尾。 */
if (!h)
{
return NULL;
}
/* 遍历左子树。 */
convert(h->l);
/* 处理根节点。 */
if (tail)
{
tail->l = h;
}
tail = h; /* 使尾指针指向当前构建好的链表尾。 */
if (!head)
{
head = tail;
}
/* 遍历右子树。 */
convert(h->r);
return head;
}
int main(int argc, char * argv[])
{
/*
* 测试数据：
* __a 5__
* __b 3__ c 6
* d 1__ e 4
* f 2
*/
struct node a = {5, NULL, NULL};
struct node b = {3, NULL, NULL};
struct node c = {6, NULL, NULL};
struct node d = {1, NULL, NULL};
struct node e = {4, NULL, NULL};
struct node f = {2, NULL, NULL};
node head;
a.l = &b;
a.r = &c;
b.l = &d;
b.r = &e;
d.r = &f;
head = convert(&a);
while (head)
{
printf("%d/n", head->d);
head = head->l;
}
return 0;
}
---------------------------------------------------------------------------
将一个结点为树节点的有序链表转换为平衡二叉搜索树。
/***************************************************************************
* Description:
* 将一个结点为树节点的有序链表转换为平衡二叉搜索树
* Author : wplxb
* Language: C
* Date : 2007-11-02
***************************************************************************/
#include <stdio.h>
typedef struct node
{
int d;
struct node * l; /* 链表使用 l 作为 next。 */
struct node * r;
} * node;
node convert(node h)
{
node prev = h;
node head = h;
node fast = h;
if (!h)
{
return NULL;
}
if (!h->l)
{
h->r = NULL;
return h;
}
while (fast && fast->l)
{
fast = fast->l->l;
prev = head;
head = head->l;
}
prev->l = NULL;
head->r = convert(head->l);
head->l = convert(h);
return head;
}
void inorder_print(node h)
{
if (!h)
{
return;
}
inorder_print(h->l);
printf("%d/n", h->d);
inorder_print(h->r);
}
int main(int argc, char * argv[])
{
/*
* 测试数据：
* a 1, b 2, c 3, d 4, e 5, f 6
*/
struct node a = {1, NULL, NULL};
struct node b = {2, NULL, NULL};
struct node c = {3, NULL, NULL};
struct node d = {4, NULL, NULL};
struct node e = {5, NULL, NULL};
struct node f = {6, NULL, NULL};
node head;
a.l = &b;
b.l = &c;
c.l = &d;
d.l = &e;
e.l = &f;
head = convert(&a);
inorder_print(head);
return 0;
}
---------------------------------------------------------------------------