沈阳建站网页模板,网站要背代码?,传媒公司注册需要什么条件,女頻做的最好的网站文章目录 二叉树的存储结构二叉树的顺序存储二叉树的链式存储小结 二叉树的先中后序遍历例题小结 二叉树的层次遍历小结 由遍历序列构造二叉树一个遍历序列即使给定了前中后序#xff0c;也不能确定该二叉树的形态可以确定的序列组合前序中序后序中序层序中序 小结若前序… 文章目录 二叉树的存储结构二叉树的顺序存储二叉树的链式存储小结 二叉树的先中后序遍历例题小结 二叉树的层次遍历小结 由遍历序列构造二叉树一个遍历序列即使给定了前中后序也不能确定该二叉树的形态可以确定的序列组合前序中序后序中序层序中序 小结若前序后序层序两两组合能吗 树的存储结构总览树的逻辑结构顺序存储双亲表示法顺序链式存储孩子表示法链式存储孩子兄弟表示法森林和二叉树的转换孩子兄弟表示法小结 树和森林的遍历树的先根遍历树的后根遍历树的层次遍历森林的先序遍历森林的中序遍历小结 二叉树的存储结构
二叉树的顺序存储 i所在的层次可回顾上面二叉树的性质
通过计算出节点对应左孩子或右孩子的节点数然后判断是否在n个节点的范围内 当非完全二叉树时不适用了如下图节点与编号不对应了 所以还是按照原来的对应图来存储。判断节点存不存在通过判断是否空的布尔值即可 弊端会浪费部分节点
二叉树的链式存储
n个节点肯定会有n-1个指针域不为空n1个指针域为空。 n-1是有n-1条线连接两个节点所以对应的指针域中也会有n-1个不为空的指针域 常用的操作 寻找某个节点的父节点时需要遍历整个数依次判断是否某个节点的子节点为对应的节点。 此时节点结构体中加上父节点指针可以避免遍历 小结 二叉树的先中后序遍历 感觉先中后序主要是根的遍历位置在前中后 有点递归的思想在里面 先找到根然后开始按对应的序遍历如果左右中存在不是叶子节点则将该节点当作根节点继续按对应的序来遍历 例题 小结 二叉树的层次遍历
核心队列非空则头节点出队并访问该节点且将其左右孩子插入队尾判断是否有有的话则插入
小结 由遍历序列构造二叉树
一个遍历序列即使给定了前中后序也不能确定该二叉树的形态 可以确定的序列组合 前序中序 后序中序
都是先判断根结点
层序中序 小结
核心找根节点
若前序后序层序两两组合能吗 无法确定一定要有中序才行
树的存储结构
总览 树的逻辑结构 顺序存储双亲表示法 顺序链式存储孩子表示法
存在指向孩子链表的指针的元素
链式存储孩子兄弟表示法 左孩子都是原本的孩子节点右孩子都是原本的兄弟节点 所以B的右孩子的遍历下去的所有右孩子为原来A节点的孩子
森林和二叉树的转换孩子兄弟表示法
把兄弟节点都连起来然后把兄弟节点与父节点的连线断了就成了 小结 树和森林的遍历
树的先根遍历
类似二叉树的先序遍历 根 左 右 对应的二叉树即对应的孩子兄弟法表示的树且该二叉树的先序遍历与原树的先根遍历相同
树的后根遍历
类似二叉树的后序遍历 左 右 根 对应的二叉树即对应的孩子兄弟法表示的树且该二叉树的中序遍历与原树的后根遍历相同
树的层次遍历
后根和先根遍历为深度优先遍历 层次遍历为广度优先遍历
森林的先序遍历 或把森林先转化为二叉树
森林的中序遍历 或转换为二叉树
小结
