前言

经过前几天的学习，我们对树这个基本数据结构也有了初步的了解，今天让我们一起来看树中比较难的二叉树，有句玩笑话叫”大学有俩棵树，上面挂了好多人，一棵二叉树，一棵高数“，也可以看出二叉树的难度，但是遇难我们更强，开始今天的学习！

二叉树定义

特点：

  - 每个结点'最多'有俩棵子树  - 左右子树都是有顺序的，不能任意颠倒  - 即使只有一棵子树，也要区分它是左子树还是右子树

一般情况下，有以下几种基本形态

• 空二叉树，没有办法画图了

• 只有一个根结点

  
  
  

• 根结点只有左子树

  
  
  

• 根结点只有右子树

  
  
  

• 根结点既有左子树又有右子树

  
  再思考一下，如果有三个结点的二叉树，又有几种形态呢？5 种，怎么来的？先看图
  
  
  

由于他必须是有序的所以要单个计算，左右分开，加起来就是 5 种下面来说几个特殊的二叉树：

• 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 K，且结点总数是(2^k) -1 ，则它就是满二叉树。

• 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

• 斜树：有点像线性表，这个斜可以不分左右，所以更像线性表了

如何判断完全二叉树，下面是它的特征：

• 叶子结点只能出现在最下俩层、

• 最下层的叶子一定集中在左部的连续位置

• 倒数俩层，若有叶子结点，一定都在右部连续位置

• 如果结点度为一，则该结点只有左孩子

• 同样结点数的二叉树，完全二叉树的深度最小

树的几种遍历方式

• 前序遍历

• 中序遍历

• 后序遍历

数据结构——二叉树先序、中序、后序及层次四种遍历（C语言版）

刷题巩固

二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树的最大深度