15.1 二叉树

二叉树的概念

  • 15.1 二叉树 - 图1

二叉树的特性二叉树有几个重要的特性：

  • n0 = n2 + 1 15.1 二叉树 - 图2

完美二叉树

  • 满二叉树
  • 15.1 二叉树 - 图3

完全二叉树

  • 且最后一层从左向右的叶节点连续存在，只缺右侧若干节点
  • 下面不是完全二叉树 15.1 二叉树 - 图4

二叉树的存储二叉树的存储常见的方式是数组和链表。

  • 15.1 二叉树 - 图5
  • 15.1 二叉树 - 图6

链表存储

  • 15.1 二叉树 - 图7

二叉搜索树二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。二叉搜索树是一颗二叉树，可以为空；如果不为空，满足以下性质：

  3. 下面那些是二叉搜索树，哪些不是？15.1 二叉树 - 图8图一：这里非空右子树键值不大于根部节点，所以不是二叉搜索树。图二：图三：
    二叉搜索树的特点：

  • 下面是一个二叉搜索树15.1 二叉树 - 图9这样数据结构的好处