一些关于树的题目

---------------------------------------------------------------------------

将一棵二叉搜索树转换为有序链表。

/***************************************************************************
* 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;
}

---------------------------------------------------------------------------