微软等数据结构与算法面试100题 第一题
第一题
题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的节点，只能调整指针的指向。 参考了July的整理。表示感谢。
分析：
由上面的例子可以看到，在对于树进行遍历的时候使用了中序遍历方法，依次修改树中节点的前指向和后指向。
因为是要求不能创建新的节点，因为在中序遍历修改指向的时候，需要一个指针指向上次遍历的那个节点的地址，以便于
当前指针的指向，因此需要一个指针。（这个应该不算是节点的创建吧？）
因此，程序主要分为两个部分，一个是树的构建（节点的插入函数），另一个是在树的中序遍历，并且在中序遍历的过程中，修改
当前遍历的节点的前指向和后指向。
代码如下：
[cpp]
#include<iostream>
#include<stdio.h>
using namespace std;
typedef struct BSTreeNode
{
float value;
BSTreeNode * NodeLeft;
BSTreeNode * NodeRight;
}DoubleList;
DoubleList * listHead;
DoubleList * listIndex;
void convert2DoubleLIST(BSTreeNode * nodeCurrent);
void InOrder(BSTreeNode * root)
{
if(NULL==root)
{
return;
}
if(root->NodeLeft!=NULL)
{
InOrder(root->NodeLeft);
}
convert2DoubleLIST(root);
if(NULL!=root->NodeRight)
{
InOrder(root->NodeRight);
}
}
void convert2DoubleLIST(BSTreeNode * nodeCurrent)
{
//listIndex存储上次的记录
nodeCurrent->NodeLeft = listIndex;
if(NULL==listIndex)
{
listHead = nodeCurrent;
}
else
//这里面都是对地址进行操作
{
//上次处理的节点
listIndex->NodeRight = nodeCurrent;
}
listIndex = nodeCurrent;
cout<<nodeCurrent->value<<endl;
}
void addBSTreeNode(BSTreeNode * & root, float value){
//创建二叉搜索树
if(NULL==root)//这样写是因为root==NULL容易写成root=NULL
{
BSTreeNode *paddNode = new BSTreeNode();
paddNode->value = value;
paddNode->NodeLeft = NULL;
paddNode->NodeRight = NULL;
root = paddNode;
}
else
{
if(value < root->value)
{
addBSTreeNode(root->NodeLeft,value);
}
else if(value > root->value)
{
addBSTreeNode(root->NodeRight,value);
}
else
{
cout<<"重复插入节点"<<endl;
}
}
}
int main(){
listIndex = NULL;
BSTreeNode * root = NULL;
addBSTreeNode(root,10);
addBSTreeNode(root,6);
addBSTreeNode(root,4);
addBSTreeNode(root,8);
addBSTreeNode(root,12);
addBSTreeNode(root,14);
addBSTreeNode(root,16);
addBSTreeNode(root,15);
InOrder(root);
return 0;
}
补充：软件开发 , C++ ,
