概念
满二叉树
叶子节点全部在最底层,除了叶子节点,每个节点都有左右两个子节点。
完全二叉树
叶子节点在最底下两层,最后一层的叶子节点都靠左排列。除了最后一层,其它层的节点要达到最大。
图中(1)是二叉树,2)是满二叉树,3)是完全二叉树。
如果是满二叉树,高度为n的满二叉树节点个数是,高度为n的完全二叉树,节点个数在:
二叉树的存储有两种方式:数组存储和链表存储。对于完全二叉树(包括满二叉树),适合使用数组存储。
遍历方式分为以下几种:
- 先序遍历
对于任意一个节点,先遍历当前节点,再遍历左子树,最后遍历右子树。
- 中序遍历
对于任意一个节点,先遍历左子树,再遍历当前节点,最后遍历右子树。
- 后序遍历
对于任意一个节点,先遍历左子树,再遍历右子树,最后遍历当前节点。