1 / 16
文档名称:

数据结构面试题精选.docx

格式:docx   大小:702KB   页数:16页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构面试题精选.docx

上传人:260933426 2017/9/4 文件大小:702 KB

下载得到文件列表

数据结构面试题精选.docx

文档介绍

文档介绍:特别说明:
本文中二叉树结构定义为:
struct Node {
Node* left;
Node* right;
int data;
};
定义:空二叉树的高度为-1,只有根节点的二叉树高度为0,根节点在0层,深度为0。
求二叉树中相距最远的两个节点之间的距离
两个节点的距离为两个节点间最短路径的长度。
求两节点的最远距离,实际就是求二叉树的直径。假设相距最远的两个节点分别为A、B,它们的最近共同父节点(允许一个节点是其自身的父节点)为C,则A到B的距离= A到C的距离+ B到C的距离。
节点A、B分别在C的左右子树下(假设节点C的左右两子树均包括节点C),不妨假设A在C的左子树上,由假设“A到B的距离最大”,先固定B点不动(即B到C的距离不变),根据上面的公式,可得A到C的距离最大,即点A是C左子树下距离C最远的点,即:
A到C的距离= C的左子树的高度。同理,  B到C的距离= C的右子树的高度。
因此,本问题可以转化为:“二叉树每个节点的左右子树高度和的最大值”。
判断二叉树是否平衡二叉树
根据平衡二叉树的定义:每个结点的左右子树的高度差小等于1,只须在计算二叉树高度时,同时判断左右子树的高度差即可。
二叉树的广度遍历(某层)
若需要对同一层的节点数据进行一些特殊操作(比如:打印完一层后换行、只打印某一层),可以记录某一层的最后一个节点,当遍历完该节点时(此时,队列的中的最后一个元素恰好就是下一层的最后一个节点),再进行这些特殊操作。
指定二叉树,给定两节点求其最近共同父节点
遍历二叉树时,只有先访问给定两节点A、B后,才可能确定其最近共同父节点C,因而采用后序遍历。
可以统计任一节点的左右子树“是否包含A、B中的某一个”(也可以直接统计“包含了几个A、B”)。当后序遍历访问到某个节点D时,可得到三条信息:节点D是否是A、B两节点之一、其左子树是否包含A、B两节点之一、其右子树是否包含A、B两节点之一。当三条信息中有两个为真时,就可以确定节点D的父节点(或节点D,如果允许一个节点是自身的父节点的话)就是节点A、B的最近共同父节点。另外,找到最近共同父节点C后应停止遍历其它节点。
上面的代码中需要特别注意的是:判断所访问时节点是否是两节点A、B时要写成
const int mid = (root == va) + (root == vb);
而不是: const int mid = (root == va) | (root == vb);
这样当va等于vb时,可以得到正确结果。
二叉树的高度
求二叉树中叶子节点的个数
交换二叉树的左右儿子
从根节点开始找到所有路径,使得路径上的节点值和为某一数值(路径不一定以叶子节点结束)
这道题要找到所有的路径,显然是用深度优先搜索(DFS)啦。但是我们发现DFS所用的栈和输出路径所用的栈应该不是一个栈,栈中的数据是相反的。看看代码:注意使用的两个栈。
二叉树“弓”字形遍历
题目描述:对二叉树进行“弓”字形遍历,即第一层从左往右遍历,第二层从右往左遍历,第三层从左往右遍历.....
思路:传统的广度优先遍历,只需一个队列即可,但只能实现每层从左往右遍历。这里可以设两个栈,分别存放相邻两层的节点,先将某层节点存入一个栈,对这个栈的每个节点进行访问和出栈操作,在出栈的同时把它的孩子节点存入另一个栈,当这层的每个节点都操作完毕后,同时也实现了下一层节点在另一个栈的入栈操作。要注意的是,相邻两层的节点入栈的顺序是相反的,这样才能实现“弓”字形遍历。
在这边可以控制一个flag状态量,当栈中为空时,判断flag是否等于0,如果等于0则从左到右,否则就是从右到左
平衡二叉树(AVL树)
是一棵二叉查找树(BST),任意一棵子树,其左右子树的高度差不大于1
四种变形
LL型
RR型
LR
RL
判断二叉树是不是完全二叉树
红黑树
一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:
1)每个结点要么是红的,要么是黑的。
2)根结点是黑的。
3)每个叶结点,即空结点(NIL)是黑的。
4)如果一个结点是红的,那么它的俩个儿子都是黑的。
5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
这些约束强制了红黑树的关键性质:最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据属性5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。
因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑

最近更新

2025年复合创伤护理实践探讨与查房教学 39页

2025年危重症患者静脉输注治疗的应用与实践 53页

减小主扇扩散弯道通风阻力的一种简单方法 2页

冷却机扬料板新型耐热抗磨材料的研究 2页

冰染染料应用于涤棉印花工艺的研究 2页

农村流动人口社会养老保险制度研究 2页

具有有限弹性变形部件的多体系统动力分析 2页

关于预应力管环向结构强度计算若干问题的探讨.. 2页

2025年防雾霾口罩挑选指南 16页

关于设计洪水计算方法的一些问题 2页

“流动电影”视域下的阿彼察邦·维拉斯哈古电.. 9页

关于科学技术进步统计学内容体系的初步设想 2页

关于电磁场对单摆运动控制的研究 2页

2025年肺血管内皮细胞瘤临床诊疗进展 14页

关于橡胶制品对样品污染的探讨 2页

关于整体道床在应用中的几个问题 2页

2025年生活垃圾焚烧发电项目发展计划 52页

2025年玻璃保温容器及其玻璃胆项目合作计划书.. 47页

关于家庭农场的规模与效益问题初探 2页

艺术舞蹈老师简历模板 1页

服装设计合作协议书 5页

煤炭资源地质勘查设计编写提纲 14页

硫酸铵生产硫酸钾的可行性方案 31页

2022年首都经济贸易大学工商管理专业《管理学.. 22页

学生5mm坐标纸(虚线 word版)直接打印 2页

(完整版)天津大学非线性信息处理技术 12页

中式烹调工艺 2页

燃烧器控制器LFL说明 10页

发展党员党员大会议程 3页