二叉搜索树转换成双向链表

2017-06-02 15:31 阅读 1,009 次 评论 1 条

输入一颗二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。此题处于剑指offer,但是太过于繁琐,下面是我的理解。

转换思想

在二叉搜索树中,左子节点的值总是小于父节点的值,右子节点的值总是大于父节点的值。因此在转换成排序的双向链表时,原先执行左子节点的指针调整为链表中指向前一个节点的指针,原先指向右子节点的指针调整为链表中指向后一个节点的指针。如下图所示:

从上图可以看出,所谓的双向链表其实就是二叉搜索树的中序遍历双向链接起来。

因此,我们可以通过对根的左子树进行链接,再用子问题的递归方式链接右子树就可以了。比如上图所示:以根节点5为中心,左子树的最右边的结点(即最大值)指向根节点,根节点指向右子树中最左边的结点(即最小值)。

我们不妨借助之前中序线索化时的方法,借助一个prev来指向已经转换好的链表的最后一个节点,即当前中序遍历节点的前一个节点,通过对prev执行的不断更新,最终到达最右边的结点。最后将二叉搜索树的根节点指向链表的第一个节点。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:二叉搜索树转换成双向链表 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情