// 二元查找樹轉有序的雙向鏈表.cpp : Defines the entry point for the console application.
//http://www.linuxidc.com
//題目：把二元查找樹轉變成排序的雙向鏈表
//要求：輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。
//要求不能創建任何新的結點，只調整指針的指向。
/* 將下面這個二元查找樹轉化成
10
/ \
6 14
/\ /\
4 8 12 16
4=6=8=10=12=14=16 這個雙向鏈表
*/
/*
什麼是二元查找樹？
二元查找樹： 它首先要是一棵二元樹，在這基礎上它或者是一棵空樹；
或者是具有下列性質的二元樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
（3）左、右子樹也分別為二元查找樹
如何構造一個二元查找樹？
和一般二叉樹構造方式類似，只是需要滿足上述條件
元素插入時利用遞歸，找到合適的插入位置
定義樹節點結構
struct BSTreeNode
{
int value；
BTreeNode *left;
BTreeNode *right;
}
思路：通過觀察可以發現，二元查找樹的中序遍歷結果就是一個有序的數列，
這樣只需要對樹進行一次中序遍歷，同時調整指針成為一個雙向鏈表即可
*/
#include "stdafx.h"
#include <iostream>
using namespace std;
struct BSTreeNode
{
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<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<<"順序遍歷："<<endl;
while(pHead!=NULL)
{
pTmp=pHead;
cout<<pHead->value<<" ";
pHead=pHead->right;
}
cout<<endl;
cout<<"逆序遍歷："<<endl;
while(pTmp!=NULL)
{
cout<<pTmp->value<<" ";
pTmp=pTmp->left;
}
cout<<endl;
}
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;
}
運行結果：