二元查找树转有序的双向链表 - c++编程基础

de
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
BSTreeNode *pHead=NULL; //指向双向链表头结点
BSTreeNode *pIndex=NULL;//保存当前访问节点的前一个节点
//比如当前访问节点6，那么pIndex指向的是4
void AddBSTreeNode(BSTreeNode **pRoot,int value)
{
if(NULL==*pRoot)
{
BSTreeNode *tmpNode=new BSTreeNode;
tmpNode->value=value;
tmpNode->left=NULL;
tmpNode->right=NULL;
*pRoot=tmpNode;
}
else if((*pRoot)->value {
AddBSTreeNode(&(*pRoot)->right,value);
}
else if((*pRoot)->value>value)
{
AddBSTreeNode(&(*pRoot)->left,value);
}
}
//中序遍历，同时调整节点指针
void InOrderAdjust(BSTreeNode* pBSTree)
{
if(NULL==pBSTree)
return;
//递归访问左子
if(NULL!=pBSTree->left)
InOrderAdjust(pBSTree->left);
//调整节点指针

pBSTree->left=pIndex;//将当前访问节点的左指针指向前一个节点
if(NULL==pIndex)//如果前一个节点是空，说明是第一次访问
pHead=pBSTree;//此时的节点应作为双向链表的表头节点
else
pIndex->right=pBSTree;//将前一个节点右指针指向当前节点，这样便构成了一个双向链表
pIndex=pBSTree;
//递归访问右子
if(NULL!=pBSTree->right)
InOrderAdjust(pBSTree->right);
}
//输出结果验证
void Print(BSTreeNode *pHead)
{
if(pHead==NULL)
return;
BSTreeNode *pTmp;
cout<<"顺序遍历："< while(pHead!=NULL)
{
pTmp=pHead;
cout<value<<" ";
pHead=pHead->right;
}
cout< cout<<"逆序遍历："< while(pTmp!=NULL)
{
cout<value<<" ";
pTmp=pTmp->left;
}
cout< }
int _tmain(int argc, _TCHAR* argv[])
{
BSTreeNode *pRoot=NULL;
AddBSTreeNode(&pRoot,10);
AddBSTreeNode(&pRoot,6);
AddBSTreeNode(&pRoot,14);
AddBSTreeNode(&pRoot,4);
AddBSTreeNode(&pRoot,8);
AddBSTreeNode(&pRoot,12);
AddBSTreeNode(&pRoot,16);
InOrderAdjust(pRoot);
Print(pHead);
system("pause");
return 0;
}
[cpp] 运行结果：

运行结果：

二元查找树转有序的双向链表 (二)