返回信息流把二元查找树转变成排序的双向链表
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 比如将二元查找树
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
struct BiTreeNode
{
int value;
BiTreeNode *left;
BiTreeNode *right;
};
void Convert(BiTreeNode *& head, BiTreeNode *& tail, BiTreeNode *root)
{
BiTreeNode *left, *right;
if (root == NULL)
{
head = NULL;
tail = NULL;
return;
}
Convert(head, left, root->left);
Convert(right, tail, root->right);
if (left!=NULL)
{
left->right = root;
root->left = left;
}
else
{
head = root;
}
if (right!=NULL)
{
root->right=right;
right->left = root;
}
else
{
tail = root;
}
}
BiTreeNode * treeToLinkedList(BiTreeNode * root)
{
BiTreeNode * head, * tail;
Convert(head, tail, root);
return head;//返回链表的头指针
}
Convert函数里的left和right怎么理解，程序中一直没有指定指向，不是一直为null吗？
这是一条镜像帖。来源：北邮人论坛 / cpp / #78085同步于 2014/4/3
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
[问题]把二元查找树转变成排序的双向链表
yonghu
2014/4/3镜像同步5 回复
订阅后，新回复会通过你的通知中心匿名送达。
5 条回复
如果你输入一棵只有一个节点的树，好像是会正确返回的，说明递归的终止条件是没有问题的。 接下来只需要考虑递归的情况，head 和 left 可以看成是左子树已经转换完成的链表的头尾指针， right 和 tail 同理， 这样，问题就变成两个链表 和 头结点 的连接。 不知道说的对不对。 另外，head 和 tail 什么的，是传递的指针的引用，所以，在底层的递归调用中，是会改变指向的，不会一直为NULL。 有错轻拍。