二進制查找樹轉有序雙向連結清單

// 二進制查找樹轉有序的雙向連結清單.cpp : Defines the entry point for the console application.
//
//題目：把二進制查找樹轉變成排序的雙向連結清單
//要求：輸入一棵二進制查找樹，将該二進制查找樹轉換成一個排序的雙向連結清單。
//要求不能建立任何新的結點，隻調整指針的指向。
/* 将下面這個二進制查找樹轉化成
			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;
}
           

運作結果：