数据结构 （19）二叉树
一、定义
二叉树（Binary Tree）是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。若集合为空，则称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。
二、基本形态
二叉树是递归定义的，其节点有左右子树之分。逻辑上，二叉树有五种基本形态：
- 空二叉树：没有任何节点。
- 只有一个根节点的二叉树。
- 只有左子树的二叉树。
- 只有右子树的二叉树。
- 完全二叉树（或满二叉树等其他形态）。
三、特殊类型
- 满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。满二叉树的每一层都完全填满，没有空缺。
- 完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。完全二叉树的特点是除了最后一层外，每一层都是满的，且最后一层的节点都靠左对齐。
四、性质
- 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个节点（i>0）。
- 若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大节点数是2^k-1（k>=0）。
- 对任何一棵二叉树，如果其叶节点个数为n0，度为2的非叶节点个数为n2，则有n0=n2+1。这个性质反映了二叉树中叶子节点和度为2的节点之间的关系。
- 具有n个节点的完全二叉树的深度k为log₂n的上取整再加1。这个性质说明了完全二叉树的深度与节点数之间的关系。
五、存储结构
- 顺序存储：将二叉树的节点按照某种规则（如层序遍历）存储在一个连续的存储空间中。这种方式适用于完全二叉树或近似完全二叉树，因为这样可以充分利用存储空间。
- 链式存储：使用链表的方式存储二叉树的节点。每个节点包含三个部分：数据域、左孩子指针域和右孩子指针域。这种方式适用于任意形态的二叉树，因为它可以灵活地表示节点的父子关系。
六、遍历
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。二叉树的遍历方式主要有四种：前序遍历、中序遍历、后序遍历和层序遍历。
- 前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。
- 中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。
- 后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。
- 层序遍历：按照从根节点开始的层次顺序，从上到下、从左到右依次访问每个节点。
七、应用
二叉树在计算机科学中有着广泛的应用。它们通过每个节点最多有两个子节点（通常称为左子节点和右子节点）的方式组织数据。二叉树特别适用于数据检索操作，特别是当数据以某种方式排序时。例如，在二叉搜索树（Binary Search Tree，BST）中，数据以中序遍历的方式（左-根-右）有序排列，使得查找、插入和删除操作都可以在对数时间复杂度内完成，这比线性表（如数组或链表）的效率要高得多。此外，二叉树还可以用于实现二叉堆、快速排序、堆排序等算法和数据结构。同时，二叉树也非常适合表达具有层级关系的数据，如家族树、组织架构图等。
结语
绚烂夏花是一种态度
秋叶静美是一份力量
！！！
原文地址：https://blog.csdn.net/m0_73399576/article/details/144163202
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！