首页 > 代码库 > 数据结构——二叉树
数据结构——二叉树
1、二叉树
特点:每个结点至多有2颗子树,并且子树有左右之分。
性质:
- 在二叉树的第i层至多有2i-1个结点;
- 深度为k的二叉树至多有2k-1个结点;
- 对任何一颗二叉树而言,若其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1。
二叉树的存储结构:
顺序存储结构(仅适用于完全二叉树)
链式存储结构(二叉链表):每个结点至少包含三个域,数据域和左、右指针域。
2、满二叉树,完全二叉树
3、二叉查找树
- 若它的左子树不为空,则左子树上所有结点的值均小于它的根节点的值;
- 若它的右子树不为空,则左子树上所有结点的值均大于于它的根节点的值;
- 它的左、右子树也分别是二叉查找树;
4、平衡二叉树(AVL树)
是二叉查找树的一个进化体。平衡二叉树要求对于每一个结点来说,它的左右子树的高度之差不能超过1。
5、红黑树
红黑树,是一种二叉查找树。
特点:
- 每个结点要么是红的,要么是黑的。
- 根结点是黑的。
- 每个叶结点,即空结点(NIL)是黑的。
- 如果一个结点是红的,那么它的俩个儿子都是黑的。
- 对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
数据结构——二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。