定义

每个结点至多有两上孩子结点
n（n>=0）个结点的有限集合

  1. n= 0时， 二叉树为空树
  2. n>0时，由根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树也分别是一棵二叉树

基本形态

image.png

  • 二叉树的孩子结点有左右之分

二叉树与度为2的有序树区别？

  1. 二叉树可为空， 度为2的有序树至少有三个结点
  2. 二叉树的孩子结点始终有左右之分，而度为2的有序树孩子结点次序是相对的

image.png

特殊二叉树

二叉树 - 图3

满二叉树

image.png

给结点从上向下， 从左向右编号，有以下特性：

  • 结点为i，
    • 左孩子=2i
    • 右孩子= 2i + 1
  • 编号为i的结点，其双亲的编号， i/2 取下限

完全二叉树

设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一—对应时，称为完全二叉树。

image.png

  • 编号6的结点不对应， 不称为完全二叉树

性质

  1. 若 i <= (n/2)取下限，则结点i为分支结点，否则为叶子结点
  2. 叶子结点只可能在层次最大的两层上出现。对于最大层次的叶子结点，都依次排在最左边的位置上。

二叉排序树

一棵二叉树，若树非空则有如下性质：
对任意结点若存在左子树或者右子树，

  • 则其左子树上所有结点的关键字都 < 该结点，
  • 右子树上所有结点的关键字，都>该结点

image.png

平衡二叉树（红黑树）

树上任意结点的左子树和右子树的深度只差不超过1

image.png

二叉树性质

二叉树存储

  • 顺序存储： （适合完全二叉树）
  • 链式存储

顺序存储

用一组连续的存储单元依次自上而下、自左至右存储完全二又树上的结点元素

顺序存储-完全二叉树
性质：
在完全二叉树中依次编号，对于结点i：
若存在左孩子，则编号为2i；若存在右孩子，则编号为2i+1

image.png

  • arr[0] 可以用来存储结点总数
  • 以上顺序存储基于“完全二叉树”

顺序存储-不完全二叉树
image.png

链式存储

用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。
image.png

  • 含有n个结点的二叉链表中，有 n+1 个空链域 2n-(n-1)

场景

  1. 保存有序数据时，退化成