树形结构
树的基本概念
- 节点,根节点,父节点,子节点,兄弟节点
- 空树: 没有任何节点
- 只有一个节点的树, 也就是只有根节点
- 子树,左子树,右子树
- 节点的度: 子树的个数
- 树的度: 所有节点度中的最大值
- 叶子节点: 度为0的节点
- 层数: 根节点在第一层,根节点的子节点在第二层(以此类推)
- 节点的深度: 从根节点到当前节点的唯一路径上的节点个数
- 节点的高度: 从当前节点到最远的叶子节点的路径上的节点总数
- 树的深度: 所有节点深度中的最大值
- 树的高度: 所有节点高度中的最大值
- 树的深度等于高度
有序树,无序树,森林
有序树:
- 树中任意节点的子节点之间有顺序
无序树:
- 树中任意节点的子节点之间没有顺序关系
森林:
- 由m(m>=0)课互补相交的树组成的集合
二叉树(Binary Tree)
二叉树特点
- 每个节点的度的最大值为2(最多拥有2课子树)
- 左子树和右子树是有顺序的
- 即使某节点只有一颗子树,也要区分是左子树还是右子树
- 非空二叉树的第i层,最多有2^(i-1)个节点
- 在高度为h的二叉树上最多有2^h-1个节点
- 对于任何一颗非空二叉树,如果叶子节点个数为n0, 度为2的节点个数为n2,则有n0=n2+1
- 假设度为1的节点个数为n1,那么二叉树的节点总数为n=n0+n1+n2
- 二叉树的边数T=n1+2*n2=n-1=n0+n1+n2-1
真二叉树: 所有节点的度都是0或2
满二叉树: 是真二叉树,且所有的叶子节点都在最后一层
完全二叉树: 叶子节点只会出现在最后两层,且最后一层的叶子节点都靠左对齐
- 度为1的节点只有左子树
- 度为1的节点要么是1个要么是0个.
- 同样节点数量的二叉树,完全二叉树的高度最小
- 一颗有n个节点的完全二叉树(n>0),从上到下,从左到右对节点从1开始编号,对任意节点如果有i=1,它是更节点;如果i>1,它的父节点编号为floor(i/2); 如果2i<=n,它的左子节点编号为2i;如果2i>n,它无左子节点; 如果2i+1<=n,它的右子节点编号为2i+1; 如果2i+1>n,它无右子节点
二叉排序树
二叉排序树又称二叉搜索树
- 任意一个节点的值都大于其左子树所有节点的值
- 任意一个节点的值都小于其右子树所有节点的值
- 它的左右子树也符合二叉排序树
二叉搜索树可以大大提高搜索数据的效率
二叉搜索树存储的元素必须具备可比较性,不允许为空
二叉树的遍历
前序遍历
访问顺序:
根节点-前序遍历左子树-前序遍历右子树
中序遍历
访问顺序:
中序遍历左子树-根节点-中序遍历右子树
后序遍历
访问顺序:
后序遍历左子树-后序遍历右子树-根节点
层序遍历
访问顺序:
从上到下、从左到右依次访问每一个节点