笔灵AI论文写作三步搞定，GO>>
二叉树的遍历脑图思维导图
免费下载
免费使用文件
生杀予夺 浏览量：102023-11-20 14:37:37
已被使用0次
二叉树的数据结构三种方法内容介绍
树图思维导图提供 二叉树的遍历脑图 在线思维导图免费制作，点击“编辑”按钮，可对 二叉树的遍历脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：77f2021f98dcd854b528059488e3fb58
思维导图大纲
二叉树遍历思维导图模板大纲
三种方法
先序：根左右
中序：左根右
后序：左右根
空间复杂度O(h)
路过法
先序：第一次路过时访问
中序：第二次路过时访问
后序：第三次路过时访问
层序遍历
初始化一个辅助队列
根节点入队
若队列非空，队头出队，左右孩子依次入队
重复上述直至队列空
由二叉树遍历序列构造二叉树
前序 or 后序 or 层序 + 中序 = 唯一确定二叉树
前序、层序、后序两两组合无法唯一确定一棵二叉树
方法
先通过前（后）（层）序找到树的根节点
根据中序序列划分左右子树，再继续找左右子树根节点
补充内容
前序序列和后序序列的关系
若前序序列恰与后序序列相反
说明是一棵单支树，即每层只有一个结点
任意节点左右子树不同时存在
只有一个叶结点
结点数 == 树高
若前序序列和后序序列相同
只有一个根节点
前后关系不同的结点必是父子关系
前后关系相同的结点必互为兄弟关系
前序与中序序列关系
以前序序列入栈，不同的出栈序列必是一个中序序列
给前序判断中序搭不搭就这么判断
后序非递归
重要特性
后序非递归栈中元素全是当前结点的祖先
从栈顶到栈底辈分逐渐变大
因此可以用来找m到n的路径（其中m是n的祖先）
沪公网安备 31011502019485号
上海工商