二叉排序树转化成双向链表

问题描述：
微软面试题，输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

思路：
二叉排序树，通过中序遍历就可以得到排序数，再改变前后指针就可以了

过程：

过程

代码：

void bst_2_list(Node *ptr, Node *Head, Node *Tail) //将树转换成双向链表  
{   
    if(ptr==NULL)   
        return;  
    bst_2_list(ptr->pleft, Head, Tail);  

    ptr->pleft=Tail;   
    if(Tail)   
        Tail->pright=ptr;   
    else   
        Head=ptr;   
    Tail=ptr;   
  
    bst_2_list(ptr->pright, Head, Tail);   
}

参考：
http://blog.csdn.net/coolingcoding/article/details/8016238

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 关于B树的一些总结(一)
    B树的定义 一棵m阶的B树满足下列条件： 树中每个结点至多有m个孩子。 除根结点和叶子结点外，其它每个结点至少有m...
    文档随手记阅读 13,355评论 0赞 25
  • 算法与数据结构面试题(转自网络)
    1.把二元查找树转变成排序的双向链表 题目： 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不...
    曲终人散Li阅读 3,371评论 0赞 19
  • 四、树与二叉树
    四、树与二叉树 1. 二叉树的顺序存储结构 二叉树的顺序存储就是用数组存储二叉树。二叉树的每个结点在顺序存储中都有...
    MinoyJet阅读 1,587评论 0赞 7
  • 《大话数据结构》总结
    第一章 绪论 什么是数据结构？ 数据结构的定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 5,822评论 0赞 19
  • B树（转）
    原文链接 B树 1.前言： 动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（...
    非典型程序员阅读 1,188评论 0赞 3