题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表: 4=6=8=10=12=14=16。
首先我们定义的二元查找树节点的数据结构如下：
struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node };
主要考察:二叉树的中序遍历算法的思想.
代码如下:
#include<iostream> #include<stdio.h> using namespace std; struct BSTreeNode { int m_nValue; BSTreeNode *m_pleft; BSTreeNode *m_pright; }; typedef struct BSTreeNode DoubleList; DoubleList *pHead, *pListIndex; void convertToDoubleList(BSTreeNode *pCurrent); void addBSTreeNode(BSTreeNode *&pCurrent, int value); void ergodicBSTree(BSTreeNode *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); return 0; } void addBSTreeNode(BSTreeNode *&pCurrent, int value) { if(pCurrent == NULL) { BSTreeNode *pBSTree = new BSTreeNode(); pBSTree->m_nValue = value; pBSTree->m_pleft = NULL; pBSTree->m_pright = NULL; pCurrent = pBSTree; } else { if((pCurrent->m_nValue) > value) addBSTreeNode(pCurrent->m_pleft, value); else if((pCurrent->m_nValue) < value) addBSTreeNode(pCurrent->m_pright, value); } } void ergodicBSTree(BSTreeNode *pCurrent) { if(pCurrent == NULL) return ; if(pCurrent->m_pleft != NULL) ergodicBSTree(pCurrent->m_pleft); convertToDoubleList(pCurrent); if(pCurrent->m_pright != NULL) ergodicBSTree(pCurrent->m_pright); } void convertToDoubleList(BSTreeNode *pCurrent) { pCurrent->m_pleft = pListIndex; if(pListIndex != NULL) pListIndex->m_pright = pCurrent; else pHead = pCurrent; pListIndex = pCurrent; cout<<pCurrent->m_nValue<<endl; }
