`

【100题】第一题

 
阅读更多

1.二元查找树转变成排序的双向链表
题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。

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 <stdio.h>
struct BSTreeNode //结构体
{
int m_nValue; // 节点值
BSTreeNode *m_pLeft; // 左孩子
BSTreeNode *m_pRight; // 右孩子
};
typedef BSTreeNode DoubleList; //用typedef声明自定义类型

DoubleList * pHead;
DoubleList * pListIndex;
void convertToDoubleList(BSTreeNode * pCurrent); //转换为 双向链表
// 创建二元查找树
void addBSTreeNode(BSTreeNode * & pCurrent, int value)
{
if (NULL == pCurrent) //采用尾部插入法
{
BSTreeNode * pBSTree = new BSTreeNode();//声明
pBSTree->m_pLeft = NULL;
pBSTree->m_pRight = NULL;
pBSTree->m_nValue = value;
pCurrent = pBSTree;//让创建的节点等于 最后一个空指针
}
else
{
if ((pCurrent->m_nValue) > value) //小的放到左边
{
addBSTreeNode(pCurrent->m_pLeft, value);//递归调用
}
else if ((pCurrent->m_nValue) < value)//大的放到右边
{
addBSTreeNode(pCurrent->m_pRight, value);
}
else
{
printf("重复加入节点");
//cout<<"重复加入节点"<<endl;
}
}
}

void ergodicBSTree(BSTreeNode * pCurrent) //中序递归遍历
{
if (NULL == pCurrent)
{
return;
}
ergodicBSTree(pCurrent->m_pLeft);
convertToDoubleList(pCurrent); // 节点接到链表尾部
ergodicBSTree(pCurrent->m_pRight);
}

void convertToDoubleList(BSTreeNode * pCurrent)// 二叉树转换成双向链表
{
pCurrent->m_pLeft = pListIndex;
if (NULL != pListIndex)//双向链表中含有元素
{
pListIndex->m_pRight = pCurrent;
}
else
{
pHead = pCurrent;
}
pListIndex = pCurrent;//这一步是关键,保证每一步之后 都是插入双链表最后
printf("%d\n",pCurrent->m_nValue);//输出插入的当前节点值
}
int main()
{
BSTreeNode * pRoot = NULL;
pListIndex = NULL;
pHead = NULL;
addBSTreeNode(pRoot, 10);
addBSTreeNode(pRoot, 4);
addBSTreeNode(pRoot, 6);
addBSTreeNode(pRoot, 8);
addBSTreeNode(pRoot, 12);
addBSTreeNode(pRoot, 14);
addBSTreeNode(pRoot, 15);
addBSTreeNode(pRoot, 16);
ergodicBSTree(pRoot);//中序遍历树,同时建立链表,并按照遍历顺序输出每个节点
return 0;
}

///////////////////////////////////////////////
4
6
8
10
12
14
15
16
Press any key to continue
//////////////////////////////////////////////

--------------------------------------------------------------
同样是上道题,给各位看一段简洁的代码,领悟一下c的高效与美:
void change(Node *p, Node *&last) //中序遍历
{
if (!p)
return;
change(p->left, last);
if (last)
last->right = p;
p->left = last;

last = p;
change(p->right, last);
}

void main()
{
Node *root = create();
Node *tail = NULL;
change(root, tail);
while (tail)
{
cout << tail->data << " ";
tail = tail->left;
}
cout << endl;
}

--------------------------以下为第二种写法------------------------
#include <iostream>
using namespace std;

class Node{
public:
int data;
Node *left;
Node *right;

Node(int d = 0, Node *lr = 0, Node *rr = 0):data(d), left(lr), right(rr){}
};

Node *create()
{
Node *root;
Node *p4 = new Node(4);
Node *p8 = new Node(8);
Node *p6 = new Node(6, p4, p8);

Node *p12 = new Node(12);
Node *p16 = new Node(16);
Node *p14 = new Node(14, p12, p16);

Node *p10 = new Node(10, p6, p14);
root = p10;

return root;
}

Node *change(Node *p, bool asRight)
{
if (!p)
return NULL;
Node *pLeft = change(p->left, false);
if (pLeft)
pLeft->right = p;
p->left = pLeft;

Node *pRight = change(p->right, true);
if (pRight)
pRight->left = p;
p->right = pRight;

Node *r = p;
if (asRight)
{
while (r->left)
r = r->left;
}else{
while (r->right)
r = r->right;
}
return r;
}

void main(){
Node *root = create();
Node *tail = change(root, false);
while (tail)
{
cout << tail->data << " ";
tail = tail->left;
}
cout << endl;

root = create();
Node *head = change(root, true);
while (head)
{
cout << head->data << " ";
head = head->right;
}
cout << endl;
}

分享到:
评论

相关推荐

    [最新答案V0.4版]微软等数据结构+算法面试100题[第41-60题答案]

    [第1题-60题汇总]微软等数据结构+算法面试100题 http://download.csdn.net/source/2826690答案系列: 5.[最新答案V0.3版]微软等数据结构+算法面试100题[第21-40题答案] http://download.csdn.net/source/28328626 ...

    软考网络考前冲刺100题.rar

    01第-章第二章p1-p29.rar 网盘文件永久链接 02第三章第四章D30-p59.ram 03第五章第五章P60-P85.rar 04第六章第章第八章P85-P8113.ram 05第九章第十章p114-P137.rar 06第十章第章P138-P165....网络工程师考前中刺100题

    软考网络工程师考前冲刺100题-全面精讲精炼视频.zip

    01 第一章 第二章P1-P29 02 第三章 第四章P30-P59 03 第五章 第五章P60-P85 04 第六章 第七章第八章P85-P8113 05 第九章 第十章P114-P137 06 第十一章 第十二章P138-P165 07 第十二章 第十二章P165-P185 08 第十三章...

    网络工程师考前冲刺100题

    《网络工程师考前冲刺100题》内容简介:一直以来,计算机技术与软件专业技术资格(水平)考试(以下简称“软考”)是国内难度最高的计算机专业资格考试之一,其平均通过率在10%左右。自网络工程师开考以来,其通过率...

    超经典图形100题

    2. **数字序列**:第1题中,去掉图形的左边一半,剩下的右边部分依次为1234,推断出下一个数字是5,这属于数字序列推理,考察的是数列规律。 3. **组合与排除**:第2题和第10题需要通过比较图形间的相似性和差异,...

    [第二部分]精选微软等公司结构+算法面试100题[41-60题]

    入队时直接将元素压入第一个栈,出队时将第一个栈中的元素依次弹出并压入第二个栈,再从第二个栈中弹出元素。 ### 第58题:链表中删除特定值的节点 **题目描述**:给定一个链表和一个值,删除链表中所有值为该值的...

    C语言编程实例100题.pdf

    第一题涉及到排列组合,目标是计算出1、2、3、4四个数字可以组成多少个互不相同且无重复数字的三位数。程序通过三重循环实现所有可能的排列组合,并通过条件判断排除重复的数字,确保生成的三位数不重复。 第二题是...

    python基础练习题100.pdf

    * 问题描述:输入某年某月某日,判断这一天是这一年的第几天? * 解决方案:判断是否是闰年,计算日历,考虑二月多加一天的情况。 实例 005:三数排序题目 * 知识点:三数排序、冒泡排序、排序算法 * 问题描述:...

    计算机C语言编程题库(100题)

    第1题 函数fun的功能是将低于平均分的人作为函数值返回,将低于平均分的分数放在below所指定的函数中。知识点: * 数组的使用 * 函数的定义和调用 * 平均值的计算 * 条件语句的使用 第2题 函数fun的功能是求出1到...

    猿人学第二届第一题解题小记

    猿人学第二届第一题解题小记

    系统集成项目管理工程师必背100题.pdf

    系统集成项目管理工程师必背100题.pdf

    国家二级C语言南开100题

    1. **第一题**:这道题要求编写一个函数`fun`,用于找出低于平均分的分数并存储到指定数组中。这个题目涉及了数组操作、循环遍历、计算平均值以及条件判断。在C语言中,数组是一种数据结构,可以用来存储同类型的...

    计算机三级网络技术机试南开100题题目与答案

    - **第一种方案**(无忧id14、id27):使用了一个辅助函数`isP()`来判断一个数是否为素数。然后通过循环遍历大于`m`的所有数,并利用`isP()`函数来检查每个数是否为素数,如果是,则将其添加到结果数组中。 ```c ...

    JAVA编程题全集(100题).doc

    1. Java 程序设计总复习题 1: 编写一个 Java 程序在屏幕上输出“你好!”。 2. Java 程序设计总复习题 2: 编写一个 Java 程序,用 if-else 语句判断某年份是否为闰年。 3. Java 程序设计总复习题 3: 编写一个 Java ...

    【计算】100道小学一年级奥数题.doc

    1. **加减法**:大部分题目都涉及到简单的加减运算,例如第1题、第2题、第3题、第4题等,通过这些问题,孩子们可以学习基本的加减法并理解数量的变化。 2. **比较和排序**:如第5题和第10题,孩子们需要比较不同...

    python面试面试宝典100题

    python 面试宝典 100 题 本资源为 python 面试宝典,共收录 100 道题目,涵盖了 python 语言的多个方面,从基础知识到高级应用,覆盖了 python 开发者在实际工作中常见的问题和挑战。本资源适合 python 开发者、...

    高中联赛难度几何题100道(精华双图版) 51页.pdf

    高中联赛难度几何题100道(精华双图版) 本资源包含100道高中联赛难度的几何题,涵盖圆、线、角、点等基本几何元素的性质和关系。本资源可以帮助学生深入理解几何知识,提高解题能力和空间想象力。 知识点: 1. ...

    南开100题三级网络技术

    背题当然就是背前面说的...第1章简单看一下就可以了;另外,虽说指针、文件输入输出等不考,但还是建议看一下,至少要知道fopen、fclose是打开、关闭函数,因为这些在给出的代码中会出现的,看到了要知道是怎么回事。

    13-15届蓝桥杯EDA模拟题和真题

    第十四届蓝桥杯EDA赛模拟题一 第十四届蓝桥杯EDA赛模拟题二 第十四届蓝桥杯EDA省赛真题 第十五届蓝桥杯EDA赛模拟试题一(嘉立创EDA提供) 第十五届蓝桥杯EDA赛模拟试题二(嘉立创EDA提供) 4T十五届模拟三

Global site tag (gtag.js) - Google Analytics