【面试题】把二元查寻树转变成排序的双向链表

2012-10-14

【面试题】把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向

【面试题】把二元查找树转变成排序的双向链表

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

　　比如将二元查找树
                                            10
                                          /    \
                                        6 14
                                      / \     /　 \
4     8 12 16
转换成双向链表4=6=8=10=12=14=16。定义二元查找树结点的数据结构如下：    struct BSTreeNode// a node in the binary search tree
    {
      int m_nValue;// value of node
        BSTreeNode *m_pLeft; // left child of node
        BSTreeNode *m_pRight; // right child of node
    };
分析与解答：可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。代码如下：

/* 建立二叉排序树 */void addBSTreeNode(BSTreeNode *&pCurrent,int value)//在这个函数中会要改变指针值，一定要记得使用引用传递 {     if (pCurrent==NULL)     {         BSTreeNode* pBSTree=new BSTreeNode();         pBSTree->m_nValue=value;         pBSTree->m_pLeft=NULL;         pBSTree->m_pRight=NULL;         pCurrent=pBSTree;     }     else if (pCurrent->m_nValue<value)     {         addBSTreeNode(pCurrent->m_pRight,value);     }     else if (pCurrent->m_nValue>value)     {         addBSTreeNode(pCurrent->m_pLeft,value);     }     else    {         cout<<"重复节点"<<endl;     }  }/*将一颗二叉搜索树转换成一个双向链表*///pNode:当前节点，即子二叉树的根节点//pLastNodeInList：双向链表中的最后一个节点void convertToDoubleList(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList){         if(pNode == NULL)            return;  BSTreeNode *pCurrent = pNode;         /*转换左子树*/  if (pCurrent->m_pLeft != NULL)            convertToDoubleList(pCurrent->m_pLeft, pLastNodeInList);   // 把当前节点放入双向链表中   pCurrent->m_pLeft = pLastNodeInList;//设置当前节点的左指针       if(pLastNodeInList != NULL)            pLastNodeInList->m_pRight = pCurrent;            pLastNodeInList=pCurrent;// 转换右子树         if (pCurrent->m_pRight != NULL)            convertToDoubleList(pCurrent->m_pRight, pLastNodeInList);}//BSTreeNode* Convert(BSTreeNode* pHeadOfTree){      BSTreeNode *pLastNodeInList = NULL;//双链表最后一个节点      convertToDoubleList(pHeadOfTree, pLastNodeInList);           // 获取双向链表的头节点      BSTreeNode *pHeadOfList = pLastNodeInList;      while(pHeadOfList && pHeadOfList->m_pLeft)            pHeadOfList = pHeadOfList->m_pLeft;      return pHeadOfList; //返回双向链表的头节点}int main(){/****创建二叉查找树****/    BSTreeNode *pRoot=NULL;     addBSTreeNode(pRoot,10);     addBSTreeNode(pRoot,6);     addBSTreeNode(pRoot,14);     addBSTreeNode(pRoot,4);     addBSTreeNode(pRoot,8);     addBSTreeNode(pRoot,12);     addBSTreeNode(pRoot,16); /***************转换为双向链表*******************/ BSTreeNode *pHeadOfList=Convert(pRoot);/**********************输出双向链表******************/  while(pHeadOfList!=NULL) {  cout<<pHeadOfList->m_nValue<<"->";       pHeadOfList=pHeadOfList->m_pRight;  }  return 0;}

热点排行

编程

【面试题】把二元查寻树转变成排序的双向链表