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

最近更新

主要养殖鱼类的生物学 85页

2025年度智慧交通系统人工费投入合同 9页

2025年度旅游行业导游劳务劳动合同书电子版 8页

2025年度旅游团意外伤害及工伤赔款协议 8页

2025年度新能源车干股分红与充电设施建设协议.. 7页

为老年人提供适宜居住环境 15页

2025年度新材料研发对赌技术突破合同 9页

2025年度文化创意产业委托招商代理协议 8页

2025年度文化产业增资扶持协议 9页

2025年度数据中心机房工装装饰施工协议 8页

2025年度教育行业劳动合同得定义与教师权益保.. 8页

2025年度教育培训机构教职工年度劳动合同示范.. 8页

2025年度教育咨询外包合同终止协议书 7页

2025年度手术室装修工程与医疗废弃物处理服务.. 9页

2025年度房产租赁不过户管理服务协议 8页

2025年度成年子女父母离婚协议书:子女监护权.. 8页

2025年度建筑项目专用商品混凝土供应协议 9页

2025年度店铺员工劳动合同续签与变更 7页

2025年度广告媒体资源整合与营销合同 9页

2025年度幼儿园教师聘用协议(幼儿教育创新项.. 9页

2025年度幼儿园与亲子游服务机构合作亲子旅游.. 8页

2025年度带小孩保姆家庭育儿指导与生活助手服.. 8页

2025年度工程项目验收与移交咨询服务合同 8页

2025年度工厂员工社会责任与雇佣劳务合同模板.. 9页

2025年度工业厂房租赁与智能化改造升级合同 8页

实用的周记高中作文锦集10篇 15页

2025年度山地农业租赁经营合同 8页

2025年度屋顶光伏发电设备安装与智能化监控服.. 9页

2025年度小学生托管安全防护及紧急救援服务合.. 9页

小学生竞选演讲稿200字(29篇) 27页