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


题目:
输入一棵二叉查找树,将该二叉查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
         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;
}

Leave a comment

Your email address will not be published. Required fields are marked *