二叉树的定义和特点以及术语

二叉树定义

度大于等于0且小于等于2的树(每个结点没有子结点或至多2个子结点)

二叉树的五种形态

• 空树(根结点也没有)

• 只有根结点

• 根节点只有左子树

• 根结点只有右子树

• 根结点既有左子树又有右子树

斜二叉树

定义：所有结点都只有左子树称为左斜二叉树；所有结点都只有右子树称为右斜二叉树；

• 左斜二叉树

  

• 右斜二叉树

  

满二叉树

定义：所有分支结点都存在左子树和右子树并且所有叶子结点都在同一层

完全二叉树

定义：对完全二叉树按层序编号，各个结点的编号和同样深度的满二叉树的结点的编号一致

特点：

• 满二叉树一定是完全二叉树
• 叶子结点只出现在最下两层
• 最下层的叶子结点都集中在二叉树左侧连续位置
• 如果有度是1的结点，只能有一个，且该结点只有左孩子