什么是binary tree

二叉树（Binary Tree）是一种树状数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

从定义来看，它可递归定义为两种情况：一是空集（即没有节点）；二是包含一个根节点，该根节点连接着两个不相交的二叉树，分别为左子树和右子树，而这两个子树也属于二叉树。

二叉树的关键概念包含多个方面。节点包含数据以及指向左右子节点的指针；根节点处于树的最顶层，没有父节点；叶子节点是没有子节点的节点；子树则是节点的左或右子节点及其所有后代节点构成的集合。

二叉树有多种常见类型。满二叉树的每个节点要么有 0 个子节点，要么有 2 个子节点；完全二叉树除了最后一层，其他层的节点都是满的，且最后一层的节点从左到右依次排列；二叉搜索树中，任意节点的左子树节点值都小于该节点值，右子树节点值都大于该节点值。

在实际应用中，二叉搜索树常用于高效的查找和插入操作；堆（基于完全二叉树）可用于实现优先级队列；平衡的二叉搜索树（如红黑树）可用于实现 map 和 set 等数据结构。

热门标签