|
原帖地址：http://topic.csdn.net/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
在原作者的基础了作了些许改进：
#include<stdio.h>
#include<iostream>
using namespace std;
struct BSTreeNode;
struct BSTreeNode
{
int m_nValue;
BSTreeNode *m_pLeft;
BSTreeNode *m_pRight;
};
typedef BSTreeNode DoubleList;
DoubleList *pHead;//双向链表的头
DoubleList *pListIndex;//记录当前节点的前一个节点
void convertToDoubleList(BSTreeNode *pCurrent);
//创建二叉查找树
void addBSTreeNode(BSTreeNode *&pCurrent,int value)
{
if(NULL==pCurrent)
{
BSTreeNode *pBSTree=new BSTreeNode();
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);
else if((pCurrent->m_nValue)<value)
addBSTreeNode(pCurrent->m_pRight,value);
else
cout<<"repeat add node"<<endl;
}
}
//在中序遍历的过程中建立双向链表
void ergodicBSTree(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);
}
void convertToDoubleList(BSTreeNode* pCurrent)
{
/* 原文的方法
pCurrent->m_pLeft=pListIndex;
if(NULL!=pListIndex)
{
pListIndex->m_pRight=pCurrent;
pCurrent->m_pLeft=pListIndex;
}
else
pHead=pCurrent;
pListIndex=pCurrent;
cout<<pCurrent->m_nValue<<endl;*/
/*我的方法*/
if(pHead==NULL)//如果当前双向链表为空，当前节点为第一个节点
{
pHead=pCurrent;
pListIndex=pCurrent;
}
else
{
pCurrent->m_pLeft=pListIndex;//当前节点的左孩子指向前驱节点
pListIndex->m_pRight=pCurrent;//前驱节点的右孩子指向当前节点
pListIndex=pCurrent;//更新前驱节点
}
}
int main()
{
BSTreeNode *pRoot=NULL;
pListIndex=NULL;
pHead=NULL;
addBSTreeNode(pRoot,10);
addBSTreeNode(pRoot,4);
addBSTreeNode(pRoot,6);
addBSTreeNode(pRoot,8);
addBSTreeNode(pRoot,12);
addBSTreeNode(pRoot,14);
addBSTreeNode(pRoot,15);
addBSTreeNode(pRoot,16);
ergodicBSTree(pRoot);
pListIndex=pHead;
//验证双向链表
while(pListIndex->m_pRight)
{
cout<<pListIndex->m_nValue<<endl;
cout<<endl;
pListIndex=pListIndex->m_pRight;
}
//pListIndex=pListIndex->m_pLeft;
while(pListIndex)
{
cout<<pListIndex->m_nValue<<endl;
cout<<endl;
pListIndex=pListIndex->m_pLeft;
}
return 0;
}
| 
转播
