概念

满二叉树

叶子节点全部在最底层,除了叶子节点,每个节点都有左右两个子节点。

完全二叉树

叶子节点在最底下两层,最后一层的叶子节点都靠左排列。除了最后一层,其它层的节点要达到最大。
图中(1)是二叉树,2)是满二叉树,3)是完全二叉树。
如果是满二叉树,高度为n的满二叉树节点个数是二叉树 - 图1,高度为n的完全二叉树,节点个数在:二叉树 - 图2
image.png
二叉树的存储有两种方式:数组存储和链表存储。对于完全二叉树(包括满二叉树),适合使用数组存储。

遍历方式分为以下几种:

  • 先序遍历

对于任意一个节点,先遍历当前节点,再遍历左子树,最后遍历右子树。

  • 中序遍历

对于任意一个节点,先遍历左子树,再遍历当前节点,最后遍历右子树。

  • 后序遍历

对于任意一个节点,先遍历左子树,再遍历右子树,最后遍历当前节点。