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所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。
因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑

最近更新

内蒙古重点小学一年级语文【上册】过关检测试.. 4页

内蒙古2019年保育员五级业务水平考试试题试卷.. 12页

内蒙古2018版保育员高级考试试题试卷(附答案).. 11页

2025年度奶制品行业展会参展与赞助合同 8页

2025年度大数据分析与应用合同确认签收单 9页

2025年度外籍专家引进与技术服务合同 8页

2025年度外卖配送服务质量提升合作协议 8页

2025年度基于业绩考核的企业内部股权转让合作.. 9页

2025年度城市综合体摊位租赁及商业配套服务合.. 8页

2025年度土石方中介代理与项目管理合同 9页

2025年度土地承包与乡村旅游开发合同 8页

2025年度国际物流运输合同交底记录新细则 9页

2025年度商铺装修工程室内外装饰设计与施工合.. 9页

2025年度商贸公司跨境电商支付结算合作协议书.. 7页

2025年度商务合同翻译原则与国际化服务标准规.. 9页

2025年度商业地产土地转让居间合作协议 8页

2025年度员工职业发展及晋升合同 7页

2025年度员工住宿安全与社区应急响应服务合同.. 9页

2025年度合同能源管理节能项目融资合同 9页

2025年度合伙经营特色饮品店合作协议 8页

2025年度可再生能源工程安全环保保障合同 9页

2025年度双方承诺协议书:教育产业合作框架协.. 9页

2025年度卫浴五金产品安全质量检测服务合同 8页

2025年度医院附属科研楼租赁合作合同 8页

2025年度医药研发竞业禁止安装合同范本 7页

2025年度医疗机构中医科耗材综合配套服务协议.. 9页

2023年社会工作实务初级重点知识点汇总 18页

“十三五”全国眼健康规划(2016-2020)实施自评.. 3页

2024年中小学教师信息技术能力考试试题库及答.. 24页

医院药房的药品采购与库存管理 26页