什么是树?
树是n个节点的有限集合。当n==0时为空树,n>0时为非空树;
- 树只有一个根节点
- 除了根结点的其他所有节点又是一个新树,称为根节点的子树。
树的示例:
树的层次:
树的根节点为第一层,根节点的孩子为第二层,以此类推。(示例图共四层)
树的度:
树的度,即子节点的个数;(如图中A节点的度为:2,D的度为:3,G的度为0)
叶子:
度数为0的节点;(如:G,H,I,J,F)
二叉树??
二叉树的性质
- 在二叉树的第i层至多含有个节点
- 深度为k的二叉树最多含有个节点
- 对于任意一个二叉树,度为0的节点个数=度为2节点个数+1
满二叉树
- 深度为k,且含有个节点的二叉树成为满二叉树;
- 每一层节点数都为最大节点数
完全二叉树
- 叶子节点只能在层次最大的两成出现
- 具有n个节点的完全二叉树深度为:⌊log₂n⌋+1
- 对于一个含有n个节点的完全二叉树,对于任意一个节点i:
- 如果 i=1,则i节点为根节点
- 如果 i>1,则i节点的双亲节点为:
- 如果 2i>n,则i节点为叶子节点(无子节点),否则,i节点的左孩子节点为2i
- 如果2i+1>n,则i节点无右子节点,否则,右子节点为2i+1
二叉树的遍历
请移步博文:数据结构-二叉树的遍历(二)
TonyChenn
2018-10-17
2018-10-17