二叉树一种树形结构概念及特点
需积分: 0 62 浏览量
2023-10-30
11:18:16
上传
评论
收藏 67KB PDF 举报
二叉树
二叉树是一种树形结构，也是树形结构的一个重要类型，许多实际问题抽象出来的数据结构往
往是二叉树形式。
二叉树是 n 个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不
相交的、被分别称为左子树和右子树的二叉树组成，是有序树。
每个节点最多只有两个子节点，分别为左子节点和右子节点。
二叉树的特点是每个节点最多只有两棵子树，即二叉树不存在度大于 2 的节点。
二叉树的子树有左右之分，其子树的次序不能颠倒。
二叉树常被用于实现二叉查找树和二叉堆。二叉树有许多特殊的形式，如满二叉树和完全二叉
树。
满二叉树是每一层的节点数都达到最大值的二叉树，而完全二叉树是深度为 K 的，有 n 个节点
的二叉树，当且仅当其每一个节点都与深度为 K 的满二叉树中编号从 1 至 n 的节点一一对应时
称之为完全二叉树。
二叉树的存储结构有两种，一种是顺序存储结构，一种是链式存储结构。
顺序存储结构是将二叉树的节点按照层次遍历的顺序存储在一个数组中，而链式存储结构是通
过指针将每个节点连接起来。
资源评论
