首页 > 代码库 > 数据结构——二叉树

数据结构——二叉树

1、二叉树

  特点:每个结点至多有2颗子树,并且子树有左右之分。

  性质:

  • 在二叉树的第i层至多有2i-1个结点;
  • 深度为k的二叉树至多有2k-1个结点;
  •  对任何一颗二叉树而言,若其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1。

  二叉树的存储结构:

  顺序存储结构(仅适用于完全二叉树)

  链式存储结构(二叉链表):每个结点至少包含三个域,数据域和左、右指针域。

2、满二叉树,完全二叉树

 

3、二叉查找树

  •   若它的左子树不为空,则左子树上所有结点的值均小于它的根节点的值;
  •   若它的右子树不为空,则左子树上所有结点的值均大于于它的根节点的值;
  •   它的左、右子树也分别是二叉查找树;

4、平衡二叉树(AVL树)

  是二叉查找树的一个进化体。平衡二叉树要求对于每一个结点来说,它的左右子树的高度之差不能超过1。

5、红黑树

  红黑树,是一种二叉查找树。

  特点:

  •   每个结点要么是红的,要么是黑的。
  •   根结点是黑的。
  •   每个叶结点,即空结点(NIL)是黑的。
  •   如果一个结点是红的,那么它的俩个儿子都是黑的。
  •   对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

 

数据结构——二叉树