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

完全二叉树

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

线索二叉树

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

ltag=0，表示指向节点的左孩子	ltag=1，则表示lchild为线索，指向节点的直接前驱
rtag=0，表示指向节点的右孩子	rtag=1，则表示rchild为线索，指向节点的直接后继

平衡二叉树

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

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