当前位置：
  1. 首页
  2. 互联网
  3. 正文
本文介绍: 先找到根，然后开始按对应的序遍历，如果左右中存在不是叶子节点，则将该节点当作根节点继续按对应的序来遍历。寻找某个节点的父节点时，需要遍历整个数，依次判断是否某个节点的子节点为对应的节点。对应的二叉树即对应的孩子兄弟法表示的树且该二叉树的先序遍历与原树的先根遍历相同。对应的二叉树即对应的孩子兄弟法表示的树且该二叉树的中序遍历与原树的后根遍历相同。通过计算出节点对应左孩子或右孩子的节点数然后判断是否在n个节点的范围内。所以B的右孩子的遍历下去的所有右孩子为原来A节点的孩子。存在指向孩子链表的指针的元素。

文章目录

二叉树的存储结构

二叉树的顺序存储

在这里插入图片描述

i所在的层次可回顾上面二叉树的性质
在这里插入图片描述

通过计算出节点对应左孩子或右孩子的节点数然后判断是否在n个节点的范围内
在这里插入图片描述
当非完全二叉树时不适用了，如下图，节点与编号不对应了

在这里插入图片描述

所以，还是按照原来的对应图来存储。判断节点存不存在通过判断是否空的布尔值即可
在这里插入图片描述
弊端：会浪费部分节点
在这里插入图片描述

二叉树的链式存储

n个节点肯定会有n-1个指针域不为空，n+1个指针域为空。
n-1是有n-1条线连接两个节点，所以对应的指针域中也会有n-1个不为空的指针域
在这里插入图片描述
常用的操作
在这里插入图片描述
寻找某个节点的父节点时，需要遍历整个数，依次判断是否某个节点的子节点为对应的节点。
此时节点结构体中加上父节点指针可以避免遍历

在这里插入图片描述

小结

在这里插入图片描述
在这里插入图片描述

二叉树的先中后序遍历

在这里插入图片描述

感觉先中后序主要是根的遍历位置在前中后

在这里插入图片描述

有点递归的思想在里面
先找到根，然后开始按对应的序遍历，如果左右中存在不是叶子节点，则将该节点当作根节点继续按对应的序来遍历

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

例题

在这里插入图片描述

小结

在这里插入图片描述

二叉树的层次遍历

核心：队列非空则头节点出队并访问该节点且将其左，右孩子插入队尾（判断是否有，有的话则插入）
在这里插入图片描述
在这里插入图片描述

小结

在这里插入图片描述

由遍历序列构造二叉树

一个遍历序列即使给定了前中后序，也不能确定该二叉树的形态

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

可以确定的序列组合

在这里插入图片描述

前序+中序

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

后序+中序

都是先判断根结点
在这里插入图片描述
在这里插入图片描述

层序+中序

在这里插入图片描述
在这里插入图片描述

小结

核心：找根节点
在这里插入图片描述

若前序，后序，层序两两组合能吗？

在这里插入图片描述
无法确定，一定要有中序才行

树的存储结构

总览

在这里插入图片描述

树的逻辑结构

在这里插入图片描述

顺序存储（双亲表示法）

在这里插入图片描述
在这里插入图片描述

顺序+链式存储（孩子表示法）

存在指向孩子链表的指针的元素
在这里插入图片描述

链式存储（孩子兄弟表示法）

在这里插入图片描述
左孩子都是原本的孩子节点，右孩子都是原本的兄弟节点
所以B的右孩子的遍历下去的所有右孩子为原来A节点的孩子
在这里插入图片描述

森林和二叉树的转换（孩子兄弟表示法）

把兄弟节点都连起来，然后把兄弟节点与父节点的连线断了就成了
在这里插入图片描述

在这里插入图片描述

小结

在这里插入图片描述

树和森林的遍历

树的先根遍历

类似二叉树的先序遍历 根 左 右
对应的二叉树即对应的孩子兄弟法表示的树且该二叉树的先序遍历与原树的先根遍历相同
在这里插入图片描述

树的后根遍历

类似二叉树的后序遍历 左 右 根
对应的二叉树即对应的孩子兄弟法表示的树且该二叉树的中序遍历与原树的后根遍历相同
在这里插入图片描述

树的层次遍历

后根和先根遍历为深度优先遍历
层次遍历为广度优先遍历
在这里插入图片描述

森林的先序遍历

在这里插入图片描述
或把森林先转化为二叉树
在这里插入图片描述

森林的中序遍历

在这里插入图片描述
或转换为二叉树
在这里插入图片描述

小结

在这里插入图片描述

原文地址:https://blog.csdn.net/llovewuzhengzi/article/details/134490413

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_36154.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

上一篇 Apache solr XXE 漏洞（CVE-2017-12629）
下一篇 Elasticsearch：什么是大语言模型（LLM）？

相关文章

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

插入图片
浏览器会保存昵称、邮箱和网站cookies信息，下次评论时使用。