哈尔滨网站建设设计公司,怎么做网站内部链接的优化,ppt简洁模板整套免费,高淳哪家做网站不错1 基本二叉树
二叉树是一种树形数据结构#xff0c;其中每个节点最多有两个子节点#xff0c;通常称为“左子节点”和“右子节点”。 二叉树的根是唯一没有父节点的节点#xff0c;而所有其他节点都有一个父节点和零个或两个子节点。
1.1 基础术语
节点#xff08;Node其中每个节点最多有两个子节点通常称为“左子节点”和“右子节点”。 二叉树的根是唯一没有父节点的节点而所有其他节点都有一个父节点和零个或两个子节点。
1.1 基础术语
节点Node: 二叉树的基本单位。每个节点都有一个关键字或称为“键值”或“数据”。根节点Root Node: 没有父节点的节点。叶节点Leaf Node: 没有子节点的节点。子树Subtree: 任何节点都可以视为其下的所有节点组成的一个新树。深度Depth: 从根节点到某一节点的简单路径上的边数。d层Level: 树中所有深度为d的节点的集合。 1.2 二叉树的遍历
以如下二叉树为例 1.2.1 前序遍历 先访问根节点然后访问左子树再访问右子树 ABDHIEJCFKG
1.2.2 中序遍历
先访问左子树再访问根节点最后访问右子树
HDIBEJAFKCG 1.2.3 后序排列 先访问左子树再访问右子树最后访问根节点
HIDJEBKFGCA 1.2.4 层次遍历
逐层的从根节点开始每层从左至右遍历
ABCDEFGHIJK 2 斜二叉树
只有左子节点或只有右子节点的二叉树称为斜二叉树 3 满二叉树
所有的分支要么左右子节点都有要么没有子节点且所有叶子结点都在同一层上 4 完全二叉树
除了最后一层外每一层都是完全填满的并且所有节点都尽量向左填充 完全二叉树特点
叶子结点只能出现在最下两层最下层的叶子结点一定集中在左边并且连续若结点度为1则该节点只有左子节点完全二叉树的深度为 (n是树中节点的数量在高度为h的完全二叉树中节点数最少为最多为对于个索引为i的点索引从1开始计数 父节点若存在的索引是左子节点若存在的索引是2i右子节点若存在的索引是2i1
满二叉树一定是完全二叉树而完全二叉树不一定是满二叉树 5 线索二叉树
线索二叉树是一种对二叉树的改进旨在通过线索也就是额外的指针加速对树的遍历操作在普通的二叉树中每个节点有两个子节点左子节点和右子节点。但有些节点的子节点可能为空这些空指针字段不存储任何信息 线索二叉树通过利用这些空指针字段来存储与当前节点在某种遍历顺序如前序、中序或后序下相邻的节点。 这样在遍历树时就不需要使用栈或递归从而提高了遍历的速度在线索二叉树中每个节点有两个额外的标志位分别表示左指针和右指针是否被用作线索 如果左子节点为空则左指针字段存储该节点在某种遍历顺序下的前驱节点如果右子节点为空则右指针字段存储该节点在某种遍历顺序下的后继节点 5.1 创建线索二叉树
创建线索二叉树通常需要两次遍历
第一次遍历是普通的前序、中序或后序遍历用于建立二叉树的基本结构。第二次遍历用于添加线索。这通常通过保存前一个访问的节点并在访问下一个节点时更新其线索来完成。
5.2 优缺点
优点
遍历更快由于已经存储了前驱和后继信息遍历操作更加高效。不需要额外的数据结构不需要使用栈或递归。
缺点
额外的存储开销需要额外的字段来存储线索和标志位。修改复杂插入或删除节点时需要更新相应的线索这使得操作更加复杂。、 参考内容数据结构与算法八-二叉树斜二叉树、满二叉树、完全二叉树、线索二叉树-腾讯云开发者社区-腾讯云 (tencent.com)
