![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/langzh-hans-640px-Binary_tree.svg.png&w=640&q=50)
二叉树
计算机科学中一种数据结构 / 维基百科,自由的 encyclopedia
在电脑科学中,二元树(英语:Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构[1]。通常分支被称作“左子树”或“右子树”。二元树的分支具有左右次序,不能随意颠倒。
![]() |
![]() |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/192px-Binary_tree.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Binary_tree.png/640px-Binary_tree.png)
二元树的第层至多拥有
个节点;深度为
的二元树至多总共有
个节点(定义根节点所在深度
),而总计拥有节点数符合的,称为“满二元树”;深度为
有
个节点的二元树,当且仅当其中的每一节点,都可以和深度
的满二元树,序号1到
的节点一对一对应时,称为完全二元树。对任何一棵非空的二元树
,如果其叶片(终端节点)数为
,分支度为2的节点数为
,则
。
与普通树不同,普通树的节点个数至少为1,而二元树的节点个数可以为0;普通树节点的最大分支度没有限制,而二元树节点的最大分支度为2;普通树的节点无左、右次序之分,而二元树的节点有左、右次序之分。
二元树通常作为资料结构应用,典型用法是对节点定义一个标记函数,将一些值与每个节点相关联。这样标记的二元树就可以实现二元搜寻树和二元堆积,并应用于高效率的搜索和排序。