首页 > 代码库 > 二叉搜索树与双向链表的转换
二叉搜索树与双向链表的转换
题目：输入一棵二叉搜索树（记住是搜索树），将该二叉搜索树转换为一个排序的双向链表。要求：不能创建任何新的结点，只能调整树中结点指针的指向。
分析：如下图
因为是二叉搜索树。所以树的排列是规则的。通过中序遍历正好遍历的是由小到大的序列。
要求说明是只能改变树结点指针的指向，不能增加新的空间和结点。所以在中序遍历的时候，主要是遍历到结点后就去改变指针指向。
为了简单，采用递归进行遍历。
树的结构
struct BinaryTreeNode{ int m_data; BinaryTreeNode* m_LeftNode; BinaryTreeNode* m_RightNode;};
下面这部分代码是总体框架
BinaryTreeNode* TransTreeToList(BinaryTreeNode* pBinaryTree){ if (pBinaryTree == NULL) return NULL; BinaryTreeNode *pLastNodeInList = NULL; TransTreeToList(pBinaryTree, &pLastNodeInList); //pLastNodeInList指向双向链表的尾结点 //找到链表的头结点 BinaryTreeNode* pHeadNode = pLastNodeInList; if (pHeadNode == NULL) return; while (pHeadNode->m_LeftNode != NULL) pHeadNode = pHeadNode->m_LeftNode;}
下面部分代码是详细的设计
void TransTreeToList(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList){ if (pNode == NULL) return; BinaryTreeNode* pCurrent = pNode; //根节点 //下面所有代码是采用中序遍历的递归方法，仅仅不同的只是每次递归都将pLastNodeInList放到链表的最左边。 if (pCurrent->m_LeftNode != NULL) //找到最左子树 TransTreeToList(pCurrent->m_LeftNode, pLastNodeInList); //下面三行代码表示将pLastNodeInList加到最左边 pCurrent->m_LeftNode = *pLastNodeInList; if (*pLastNodeInList != NULL) (*pLastNodeInList)->m_RightNode = pCurrent; //因为是双向链表，所以pLastNodeInList要向右指向当前结点 *pLastNodeInList = pCurrent; //再遍历根节点,此时*pLastNodeInList为根节点，也就是在没有遍历右子树之前最后的一个结点。 if(pCurrent->m_RightNode != NULL) //再遍历右子树 TransTreeToList(pCurrent->m_RightNode,pLastNodeInList);}
代码简单分析：
总体的步骤还是采用中序递归遍历。先遍历左边结点，接着将左边结点加到根节点的最左边，变成双向指针。接下来pLastNodeInList指向链表的最右边。接下来再遍历右子树，将pLastNodeInList加到右子树的最左边，这样递归下去。
总之要明白整个代码是按照中序递归遍历的，过程中仅仅就是改变了指针方向。不要过分追究过程细节。
时间复杂度分析：
该算法首先从根要点一直向左走，找到最左边的结点，其时间复杂度为O(logN)，然后对二叉排序树中的每个结点遍历一次，进行指针变换，其时间复杂度为O(N)，所以总的时间复杂度为O(N)
参考：http://blog.csdn.net/ljianhui/article/details/22338405
剑指offer
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。