定义
每个结点至多有两上孩子结点
n(n>=0)个结点的有限集合
- n= 0时, 二叉树为空树
- n>0时,由根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树也分别是一棵二叉树
基本形态
- 二叉树的孩子结点有左右之分
二叉树与度为2的有序树区别?
- 二叉树可为空, 度为2的有序树至少有三个结点
- 二叉树的孩子结点始终有左右之分,而度为2的有序树孩子结点次序是相对的
特殊二叉树
满二叉树
给结点从上向下, 从左向右编号,有以下特性:
- 结点为i,
- 左孩子=2i
- 右孩子= 2i + 1
- 编号为i的结点,其双亲的编号, i/2 取下限
完全二叉树
设一个高度为h、有n个结点的二叉树,当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一—对应时,称为完全二叉树。
- 编号6的结点不对应, 不称为完全二叉树
性质
- 若 i <= (n/2)取下限,则结点i为分支结点,否则为叶子结点
- 叶子结点只可能在层次最大的两层上出现。对于最大层次的叶子结点,都依次排在最左边的位置上。
二叉排序树
一棵二叉树,若树非空则有如下性质:
对任意结点若存在左子树或者右子树,
- 则其左子树上所有结点的关键字都 < 该结点,
- 右子树上所有结点的关键字,都>该结点
平衡二叉树(红黑树)
树上任意结点的左子树和右子树的深度只差不超过1
二叉树性质
二叉树存储
- 顺序存储: (适合完全二叉树)
- 链式存储
顺序存储
用一组连续的存储单元依次自上而下、自左至右存储完全二又树上的结点元素
顺序存储-完全二叉树
性质:
在完全二叉树中依次编号,对于结点i:
若存在左孩子,则编号为2i;若存在右孩子,则编号为2i+1
- arr[0] 可以用来存储结点总数
- 以上顺序存储基于“完全二叉树”
顺序存储-不完全二叉树
链式存储
用链表来存放一棵二叉树,二叉树中每个结点用链表的一个链结点来存储。
- 含有n个结点的二叉链表中,有 n+1 个空链域
2n-(n-1)
场景
- 保存有序数据时,退化成