数据结构【DS】特殊二叉树

完全二叉树

• 叶子结点只能出现在最下层和次下层, 最下层的叶子结点集中在树的左部
• 完全二叉树中, 度为1的节点数 = 0个或者1个【计算时可以用这个快速计算, 配合𝑛0=𝑛2+1】
• 
• 
• 
• 
• 若n为奇数，则分支节点每个都有左右孩子；若n为偶数，则编号最大的分支节点只有左孩子，没有右孩子。

线索二叉树

• 线索二叉树是一种物理结构
• 引入线索的目的是加快对二叉树的遍历
• n个节点的线索二叉树上含有线索数量为n+1个 ，来存放节点的前驱和后继信息
• 后序线索二叉树不能有效解决求后序后继的问题，后序线索树的遍历仍需要栈的支持

平衡二叉树

平衡二叉树满足平衡的最少结点的情况是什么？

• 所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况：
  • 
  • 
  •