首页 > 编程语言 > 详细

算法-1.把二元查找树转变成排序的双向链表

时间:2016-04-10 10:20:15      阅读:147      评论:0      收藏:0      [点我收藏+]

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 如下图。

      10

          /\

       6    14

      /\     /\

     4 8 12 16

转换成双向链表
4=6=8=10=12=14=16。 

这是一种二叉树的中序遍历。

 

typedef struct BSTreeNode {

    int data;

    struct BSTreeNode *m_pLeft;

    struct BSTreeNode *m_pRight;

}BSTreeNode,*pBSTreeNode;

 

pBSTreeNode linkList = NULL;//全局变量,当前链表的指针

pBSTreeNode  pFormer = NULL;//以前的

void BinTreeToLinkList(pBSTreeNode BT){

    if(BT!=NULL){

        BinTreeToLinkList(BT->m_pLeft);

        if(linkList==NULL){

            linkList=BT;

            pFormer=BT;

        }else{

            pFormer->m_pRight=BT;

            BT->m_pLeft=pFormer;

            pFormer=BT;

        }

        BinTreeToLinkList(BT->m_pRight);

    }

}

如何进行验证呢,首先创建一个二叉树。

void  addBSTreeNode(pBSTreeNode *pNode,int  data){

        if (*pNode == NULL) {

        *pNode =  (pBSTreeNode)malloc(sizeof(BSTreeNode));

        (*pNode)->data = data;

        (*pNode)->m_pLeft = NULL;

        (*pNode)->m_pRight = NULL;

    }

    else if((*pNode)->data<data){

        addBSTreeNode(&(*pNode)->m_pRight,  data);

    }

    else if((*pNode)->data>data){

        addBSTreeNode(&(*pNode)->m_pLeft,  data);

    }

}

//创建

void  createTree(){

    BSTreeNode *pRoot = NULL;

     addBSTreeNode(&pRoot,10);

    addBSTreeNode(&pRoot,6);

    addBSTreeNode(&pRoot,14);

    addBSTreeNode(&pRoot,4);

    addBSTreeNode(&pRoot,8);

    addBSTreeNode(&pRoot,12);

    addBSTreeNode(&pRoot,16);

     BinTreeToLinkList(pRoot);

  }

算法-1.把二元查找树转变成排序的双向链表

原文:http://www.cnblogs.com/menchao/p/5373376.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!