二叉查询树转变成双向链表算法.doc

二叉查询树转变成双向链表算法————————————————————————————————作者:————————————————————————————————日期: :输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。10/\614/\/\481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下:structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};*///引用245楼tree_star的回复#include<>#include<>structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};typedefBSTreeNodeDoubleList;DoubleList*pHead;DoubleList*pListIndex;voidconvertToDoubleList(BSTreeNode*pCurrent);//创建二元查找树voidaddBSTreeNode(BSTreeNode*&pCurrent,intvalue){if(NULL==pCurrent){BSTreeNode*pBSTree=newBSTreeNode();pBSTree->m_pLeft=NULL;pBSTree->m_pRight=NULL;pBSTree->m_nValue=value;pCurrent=pBSTree;}else{if((pCurrent->m_nValue)>value){addBSTreeNode(pCurrent->m_pLeft,value);}elseif((pCurrent->m_nValue)<value){addBSTreeNode(pCurrent->m_pRight,value);}else{//cout<<"重复加入节点"<<endl;}}}//遍历二元查找树中序voidergodicBSTree(BSTreeNode*pCurrent){if(NULL==pCurrent){return;}if(NULL!=pCurrent->m_pLeft){ergodicBSTree(pCurrent->m_pLeft);}//节点接到链表尾部convertToDoubleList(pCurrent);//右子树为空if(NULL!=pCurrent->m_pRight){ergodicBSTree(pCurrent->m_pRight);}}//二叉树转换成listvoidconvertToDoubleList(BSTreeNode*pCurre