首页 > 代码库 > 二叉搜索树与双向链表 【第一题】
二叉搜索树与双向链表 【第一题】
题目要求：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解决思路：
1. 根据观察可知，双向链表顺序即为二叉树的中序遍历结果----->采用中序遍历+递归；
2. 中序遍历顺序为：左+中+右，传入一个变量pre。
pre可以这样理解：当前结点的pre就是当前结点的前驱。如结点6的前驱是4，结点10的前驱是8.结点4的前驱是NULL。
#include <iostream>using namespace std;typedef struct BinaryTree{ struct BinaryTree *left,*right; int data;}BinaryTree;void initTree(BinaryTree **p);void printList(BinaryTree *list);BinaryTree *treeToList(BinaryTree *pTree);int main(void){ BinaryTree *pTree = NULL,*pList = NULL; initTree(&pTree); pList = treeToList(pTree); printList(pList); return 0;}// 1// / // 2 3// / // 4 5void initTree(BinaryTree **p){ *p = new BinaryTree; (*p)->data = http://www.mamicode.com/1;"<==>"; } list = list->right; }}
//---------------核心代码-----------------------void convert(BinaryTree *pTree,BinaryTree **pre){ if(pTree == NULL) return; BinaryTree *pCurrent = pTree; if(pCurrent->left != NULL) convert(pTree->left,pre); //当前点的前驱为pre pCurrent->left = *pre; //pre不为NULL，pre的后继为当前点 if(*pre != NULL) (*pre)->right = pCurrent; //pre为当前点 *pre = pCurrent; if(pCurrent->right != NULL) convert(pTree->right,pre);}BinaryTree *treeToList(BinaryTree *pTree){ BinaryTree *pre = NULL; convert(pTree,&pre); //按照初始化的树，链表为4<==>2<==>5<==>1<==>3 //此时pre在结点3处，应该返回到结点4处，再遍历输出 while(pre!=NULL && pre->left!=NULL) pre = pre->left; return pre;}
二叉搜索树与双向链表 【第一题】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。