二叉树-满二叉树、完全二叉树
满二叉树
一棵高度为h,并且含有 2 h − 1 2^{h}-1 2h−1个结点的二叉树称为满二叉树,即树中的每一层都含有最多的结点。满二叉树的叶子节点都集中在二叉树的最下一层,并且除叶子结点之外的每个结点度数均为2.(二叉树结点的度即为结点的孩子个数)。
特点:
只有最后一层有叶子结点。不存在度为1的结点。按层序从1开始编号,自上而下,自左向右。这样每个结点对应一个编号,对于编号为i的结点,如果有双亲,其双亲为 ⌊ i / 2 ⌋ \lfloor i/2\rfloor ⌊i/2⌋,如果有左孩子,则左孩子为 2 i 2i 2i,如果有右孩子,则有孩子为 2 i + 1 2i+1 2i+1。
完全二叉树
设一个高度为h, 有n个结点的二叉树,当且仅当其每一个结点都与高度为h的满二叉树中编号为 1... n 1 ... n 1...n的节点一一对应时,称为完全二叉树。
特点:
只有最后两层可能有叶子结点。最多只有一个度为1的结点,且该节点只有左孩子没有右孩子。若 i < = ⌊ n / 2 ⌋ i<=\lfloor n/2 \rfloor i<=⌊n/2⌋,则节点 i i i为分支结点,否则为叶子节点。按层序编号之后,一旦出现某节点(其编号为i)为叶子结点或只有左孩子,那么编号大于i的节点均为叶子结点。若n为奇数,则每个分支结点都有左孩子和右孩子;若n为偶数,则编号最大的分支结点(编号为n/2)只有左孩子没有右孩子,其余分支结点左右孩子都有。