二元查找树转换成一个排序的双向链表代码

《二元查找树转换成一个排序的双向链表代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二元查找树转换成一个排序的双向链表代码题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。　　比如将二元查找树                                            10                                          /                                            6       14                       

2、               /       /                                      4     8  12 16转换成双向链表4=6=8=10=12=14=16。/*1.二叉树中序遍历的结果与链表的顺序一致，所以可以采用中序遍历的方法来修改二叉树的指针2.该题的关键是，如何将左子树的最大值与右子树的最小值通过根root连接起来，比如题目的8和12，这也是细节部分3.写递归程序最重要的是弄明白递归进入的条件、递归返回的状态，如果递归进入时改变了环境，返回时

3、应当恢复环境，就像栈的操作一样4.使用指针变量时，要记得初始化5.该算法没有返回链表头，而是返回了root。*/以下图片为测试结果：[cpp] viewplaincopy1./*节点定义*/  2.  3.typedef struct node  4.  5.{  -8-1.  2.        char value;  3.  4.        struct node *left;  5.  6.        struct node *right;  7.  8.}BSTree;  9. 

4、 10.   11.  12./*查找以tr为根最左边的节点，即以tr为根的二叉排序树的最小值*/  13.  14.BSTree *findLeft(BSTree *tr)  15.  16.{  17.  18.        BSTree*p = NULL;  19.  20.        while(tr->left)  21.  22.        {  23.                p= tr->left;  24.                tr= p;  25.  

5、      }        26.        return tr;  27.}  28.  29.   30.  31./*查找以tr为根最右边的节点，即以tr为根的二叉排序树的最大值*/  32.  33.BSTree *findRight(BSTree *tr)  34.{  35.        BSTree*p = NULL;  36.  37.        while(tr->right)  38.        {  39.                p= tr->righ

6、t;  40.                tr= p;  41.        }  42.        return tr;  43.}  44.  45.   46.  47./*实现将二叉排序树数转变为双链表*/  48.  -8-1.BSTree *ConvertBSTreeToList(BSTree **root)  2.{  3.  4.        if(!*root)  5.                return (BSTree *)NULL;  6.  7.    

7、    BSTree*lt=NULL,*rt=NULL;  8.  9.        if((*root)->right)/*先处理右子树，其实先处理左子树也行*/  10.        {  11.                rt= ConvertBSTreeToList(&(*root)->right);/*递归进入*/  12.  13.                if((*root)->right)/*递归返回处理，如果该根节点的右子树有最小值，则将该最小值的节点与root连起

8、来，否则直接处理*/  14.  15.                        lt= findLeft((*root)->right);  16.  17.                if(lt)rt = lt;  18.  19.                if(rt)  20.                {  21.                        rt->left= *root;  22.                        (*