相关知识点:
- 结点拥有的子树数称为结点的度
- 树的度是树内各结点度的最大值
- 树中结点的最大层数称为树的高度或深度
根结点:无双亲,唯一
叶结点:无孩子,可以多个
中间结点:一个双亲多个孩子
二叉树的特点:
- 每个结点最多有两棵子树
- 左子树和右子树是由顺序的
特殊二叉树:
- 斜树,每层只有一个结点,结点个数与二叉树的深度相同
- 满二叉树
- 完全二叉树
二叉树的性质:
- 二叉树的第i层上最多有2i-1个结点(i>=1)
- 深度为k的二叉树最多有2k-1个结点(k>=1)
- 任意一棵二叉树,终端结点数为n0,度为2的节点数为n2,则n0=n2+1
- 具有n个结点的完全二叉树的深度为【log2n】+1,【x】代表不大于x的最大整数
二叉树的遍历:
深度优先(栈来实现)
- 前序遍历:中左右
- 中序遍历:左中右
- 后序遍历:左右中
广度优先(队列实现)
- 层次遍历
二叉搜索树
左小于根,右大于根
平衡二叉搜索树
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1
C++中map、set、multimap,multiset的底层实现都是平衡二叉搜索树
标签:结点,遍历,数为,二叉,二叉树,深度 From: https://www.cnblogs.com/gaishuobulao/p/17384923.html