二叉树
计算机科学中一种数据结构 / 维基百科,自由的 encyclopedia
在计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构[1]。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。
此条目或许包含不重要、多余或偏颇的范例。 (2015年4月8日) |
本条目有隐藏内容,或许有碍读者阅览。请协助改善条目,以符合维基百科标准。 (2015年3月2日) |
二叉树的第层至多拥有个节点;深度为的二叉树至多总共有个节点(定义根节点所在深度 ),而总计拥有节点数符合的,称为“满二叉树”;深度为有个节点的二叉树,当且仅当其中的每一节点,都可以和深度的满二叉树,序号1到的节点一对一对应时,称为完全二叉树。对任何一棵非空的二叉树,如果其叶片(终端节点)数为,分支度为2的节点数为,则。
与普通树不同,普通树的节点个数至少为1,而二叉树的节点个数可以为0;普通树节点的最大分支度没有限制,而二叉树节点的最大分支度为2;普通树的节点无左、右次序之分,而二叉树的节点有左、右次序之分。
二叉树通常作为数据结构应用,典型用法是对节点定义一个标记函数,将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆,并应用于高效率的搜索和排序。