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年意外保险合同范本 33页

二零二五年度个人轿车买卖合同模板 9页

二零二五年度个人车辆代驾租赁服务协议 7页

2025年想要学习交谊舞应该怎么开始 2页

二零二五年度个人车位租赁合同协议书(含车位.. 8页

二零二五年度个人车位出租与停车场智能停车诱.. 8页

2025年儿童血液病护理实用指南与技巧 94页

2025年儿童营养补给攻略 67页

二零二五年度个人购房贷款合同(含物业费减免.. 8页

2025年惊蛰节气有哪些风俗 6页

2025年儿童脑瘫预防攻略全方位呵护宝宝健康 46页

2025年惊蛰的拼音是什么 2页

二零二五年度个人职业定位顾问服务合同 8页

2025年惊蛰吃什么传统食物习俗 6页

2025年惊蛰养生吃什么水果蔬菜 5页

二零二五年度个人租车合同,含驾驶培训课程 9页

二零二五年度个人租赁汽车作为公司客户接待用.. 8页

二零二五年度个人租房合同协议书——租赁房产.. 8页

2025年情人节高级单身文案 11页

二零二五年度个人知识产权交易居间合同 9页

2025年儿童病例分析与治疗策略 27页

2025年情人节营销文案推文精选5句 11页

二零二五年度个人猪场品牌授权及营销推广合同.. 8页

二零二五年度个人消费贷款服务协议 8页

二零二五年度个人消费信用贷款合同模板 8页

二零二五年度个人汽车租赁及维护服务合同 8页

2025年安徽省初中学业水平考试名校联考(一)数.. 2页

鞋子销售员工聘用协议 5页

我的大学梦主题班会 29页

2024年江苏泰州兴化市事业单位招考公开招聘历.. 241页