频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
微软等数据结构与算法面试100题 第一题
2012-08-21 09:19:08      个评论      
收藏   我要投稿

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

点击复制链接 与好友分享!回本站首页
上一篇:后缀数组之最长公共子串 poj 2774
下一篇:微软等数据结构与算法面试100题 第二题
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站