把二叉查找树转变成排序的双向链表

2013/04/03  in Postgraduate by Jacky Wei

---

题目：

输入一棵二叉查找树，将该二叉查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

         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 “stdafx.h”

#include <stdio.h>

#include <stdlib.h>

struct BSTreeNode

{

int m_iValue;

BSTreeNode *m_pLeft;

BSTreeNode *m_pRight;

};

BSTreeNode *pHead=NULL;   //指向双向链表的头结点

BSTreeNode *pLast=NULL;    //在建立双向链表的过程中，始终指向双向链表的最后一个节点。

void AddBSTreeNode(BSTreeNode *&root, int value)  //建立二叉排序树

{

if(root==NULL)

{

root = new BSTreeNode;

root->m_iValue = value;

root->m_pLeft=NULL;

root->m_pRight=NULL;

return ;

}

if(value<root->m_iValue)

AddBSTreeNode(root->m_pLeft,value);

else if(value > root->m_iValue)

AddBSTreeNode(root->m_pRight,value);

}

void AdjustPointer(BSTreeNode *pCurrent)//要调整当前节点的指向

{

if(pLast==NULL)  //最后一个节点不存在，说明双向链表还没有建立起来。

{

pHead=pCurrent;

}

else                       //最后一个节点存在

pLast->m_pRight=pCurrent;

pCurrent->m_pLeft = pLast;

pLast=pCurrent;

}

void MidTraverseBSTree(BSTreeNode *root)

{

BSTreeNode *p;

if(root==NULL) 

return;

if(root->m_pLeft!=NULL)

MidTraverseBSTree(root->m_pLeft);

AdjustPointer(root);

if(root->m_pRight!=NULL)

MidTraverseBSTree(root->m_pRight);

}

int _tmain(int argc, _TCHAR* argv[])

{

BSTreeNode *root=NULL;

AddBSTreeNode(root,10);

AddBSTreeNode(root,6);

AddBSTreeNode(root,14);

AddBSTreeNode(root,4);

AddBSTreeNode(root,8);

AddBSTreeNode(root,12);

AddBSTreeNode(root,16);

MidTraverseBSTree(root);

BSTreeNode *p;

//验证，遍历双向链表，应该等于二叉查找树的中序遍历

for( p=pHead ; p!=NULL; p=p->m_pRight)

printf(“%d,”,p->m_iValue);

printf(“\n”);

return 0;

}

---

---