我们之前学习了二叉树相关的概念，那么我们今天来分析下二叉树中的一些经典面试题。1、单度结点的删除— 编写一个函数用于删除二叉树中的所有单度结点；— 要求：结点删除后，其唯一的子结点替代它的位置。示例如下a> 那么在我们的结点中包含指向父结点的指针。定义功能：delOld1(node)，删除 node 为根结点的二叉树中的单度结点；实现思路如下我们来看看具体代码怎么写我们在其中构建的是上图中的二叉树，来运行看看结果我们看到运行的结果和我们想象的是一致的，前序遍历完后的结果为 6 0 7 2 8。b> 结点中只包含左右孩子指针。定义功能：delOld2(node) // node 为结点指针的引用；删除 node 为根结点的二叉树中的单度结点；实现思路如下图所示我们来看看具体的源码编写测试代码如下我们来看看运行结果结果还是和之前的是一样的，证明我们写的是正确的。2、中序线索化二叉树— 编写一个函数用于中序线索化二叉树— 要求：不允许使用其他数据结构示例如下a> 在中序遍历的同时进行线索化思路：使用辅助指针，在中序遍历时指向当前结点的前驱结点；访问当前结点时，连接与前驱结点的先后次序；示例如下定义功能：inOrderThread(node, pre) ，node 为根结点，也是中序访问的结点；pre 为中序遍历时的前驱结点指针。实现思路如下我们来看看具体源码是怎么写的 测试代码如下
运行结果如下b> 中序遍历的结案次序正好是结点的水平次序思路：使用辅助指针，指向转换后双向链表的头结点和尾结点；跟结点与左右子树转换的双向链表连接，成为完整的双向链表。示例如下定义功能：inOrderThread(node, head, tail)； node 为根结开发云主机域名点，也是中序访问的结点；head 为转换成功后指向双向链表的首结点；tail 为转换成功后指向双向链表的尾结点。实现思路如下具体源码实现测试代码运行结果如下我们看到两中算法的遍历结果是一样的。关于二叉树的面试题分析，我们就到这了，后面继续学习相关的数据结构。
相关推荐: 图解 Spring：HTTP 请求的处理流程与机制【3】
在穿越了 Web 容器之后，HTTP 请求将被投送到 Web 应用，我们继续以 Tomcat 为例剖析后续流程。Web 容器与 Web 应用的衔接是通过配置文件 web.xml 完成的。web.xml 是遵循 Java Servlet 标准规范的配置文件，我们…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
