数据结构【DS】特殊二叉树
完全二叉树
- 叶子结点只能出现在最下层和次下层, 最下层的叶子结点集中在树的左部
- 完全二叉树中, 度为1的节点数 = 0个或者1个【计算时可以用这个快速计算, 配合𝑛0=𝑛2+1】
- 若n为奇数，则分支节点每个都有左右孩子；若n为偶数，则编号最大的分支节点只有左孩子，没有右孩子。
线索二叉树
- 线索二叉树是一种物理结构
- 引入线索的目的是加快对二叉树的遍历
- n个节点的线索二叉树上含有线索数量为n+1个 ，来存放节点的前驱和后继信息
- 后序线索二叉树不能有效解决求后序后继的问题，后序线索树的遍历仍需要栈的支持
| ltag=0，表示指向节点的左孩子 | ltag=1，则表示lchild为线索，指向节点的直接前驱 |
| rtag=0，表示指向节点的右孩子 | rtag=1，则表示rchild为线索，指向节点的直接后继 |
平衡二叉树
平衡二叉树满足平衡的最少结点的情况是什么？
- 所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况：
