輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。
要求不能創建任何新的結點，只調整指針的指向。
10
/ /
6 14
/ / / /
4 8 12 16
轉換成雙向鏈表
4=6=8=10=12=14=16。
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
typedef struct BSTreeNode
{
int date;
struct BSTreeNode *leftnode;
struct BSTreeNode *rightnode;
}BSTree;
BSTree *head = NULL;
BSTree *tail = NULL;
void creatree(BSTree **node, int num)
{
BSTree *newnode;
newnode = (BSTree *)malloc(sizeof(BSTree));
newnode->date = num;
newnode->leftnode = NULL;
newnode->rightnode = NULL;
BSTree *p = NULL;
BSTree *y = NULL;
p = *node;
while (p)
{
y = p;
if (newnode->date > p->date)
{
p = p->rightnode;
}
else
{
p = p->leftnode;
}
}
if (y == NULL)
{
*node = newnode;
}
else
{
if (y->date > num)
{
y->leftnode = newnode;
}
else
{
y->rightnode = newnode;
}
}
}
void inorder(BSTree *node, void(*TreeLink)(BSTree *node))
{
if (node != NULL)
{
inorder((node->leftnode), TreeLink);
TreeLink(node);
inorder((node->rightnode), TreeLink);
}
}
void TreeLink(BSTree *node)
{
node->leftnode=tail;
if (tail==NULL)
{
head = node;
}
else
{
tail->rightnode = node;
}
tail = node;
printf("%d ", node->date);
}
void main()
{
int a[8] = { 10, 6, 14, 4, 8, 12, 16 };
BSTree *node=NULL;
for (int i = 0; i < 7; i++)
{
creatree(&node, a[i]);
}
inorder(node,TreeLink);
system("pause");
}