树的基本说明
树形结构
二叉树
多叉树
树的基本概念
节点 : 所有的元素都是,1,2,3,4,5,6,7,21...221,222,223
根节点: 1
父节点: 2的父节点是1,21的父节点是2
子节点: 1的子节点是2,3,4,5,6,2的子节点是21,22
兄弟节点: 同一个父节点的节点,都是兄弟节点.2的兄弟节点是:3,4,5,6
空树: 没有任何节点叫做空树
子树: 比如1.下面的 2,3,4,5,6 各自都可以成为一个树.都是1的子树
左子树:一般是在二叉树里面. 比如2 的左子树是21
右子树:同左子树.只是是右边的树.比如2的右子树是22
节点的度:子树的个数 , 比如1的度是:5(2,3,4,5,6) , 2的度是2(21,22),21的度是0
树的度: 所有节点度中最大的值. 1的度是5,其他度都不超过5, 所以整棵树的度是5
叶子节点: 度为0的节点. 比如4, 21,31,51,52,61,221,222,223
非叶子节点:度不为0的节点
层数:如果1.为第一层的话.图中有4层.如果1,为第0层的话.图中有3层
节点的深度: 从根节点到当前节点的路径经过的节点数,比如21的深度.就是1,2,21. 所以深度为3
节点的高度: 从当前节点到最远叶子节点的路径的节点数, 比如1的高度.要经过1,2,22,221. 所以高度为4
树的深度:所有节点深度最大的值. 4
树的高度:所有节点高度中最大的值. 4
树的深度 = 树的高度
有序树
树种的任何节点之间有顺序排序
无序树
树中节点之间没有顺序关系
森林
多个没有香蕉的树组成的就是森林
二叉树
特点
- 每个节点的度最大为2(最多拥有2棵子树)
- 左子树和右子树是有顺序的
- 即使只有一颗子树,也要区分左右子树
- 二叉树是有序树
性质
- 非空二叉树的第i层,最多有2^(i-1)个节点(i≥1)
- 在高度为h的二叉树上最多有2^h - 1 个节点(h≥1)
- 对于任何一颗非空二叉树,如果叶子节点个数为n0,度为2的节点个数为n2, 则:n0 = n2 + 1
- 假设度为1的节点个数为n1,二叉树的节点总数n = n0 + n1 + n2
- 二叉树的边数T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 -1
二叉树的种类
真二叉树(Proper Binary Tree , 完满二叉树(Full Binary Tree))
所有节点的度都要嘛是0,要么是2
满二叉树(Full Binary Tree , 完美二叉树(Perfect Binary Tree))
- 所有节点的度要么为0,要么为2.且所有的叶子节点都在最后一层
- 在同样高度的二叉树中,满二叉树的叶子节点数量最多,总结点数量最多
- 满二叉树一定是真二叉树,真二叉树不一定是满二叉树
性质
- 假设满二叉树的高度为h(h > 0)
- 第i层的节点数量:2^(i-1)
- 叶子节点数量: 2^(h-1)
- 总结点数量n = 2^h - 1 = 2^0 + 2^1 + 2^2 + ... + 2 ^(h-1)
- h = log2(n+1)
完全二叉树(Complete Binary Tree)
- 叶子节点只会出现最后2层,且最后1层的叶子节点都靠左对齐
- 完全二叉树从根节点至倒数第二层是一颗满二叉树
- 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树
性质
- 度为1的节点只有左子树
- 度为1的节点要么是1个,要么是0个
- 同样节点数量的二叉树,完全二叉树的高度最小
- 假设完全二叉树的高度为h(h>0),
- 至少有2^(h-1) 个节点 (2^0 + 2^1 + 2^2 + ... + 2^(h-2) + 1)
- 最多有2^h - 1个节点(满二叉树)
- 总节点数量是n , h = floor(log2n) + 1
- 一颗有n个节点的完全二叉树(n>0),从上到下,从左到右对节点从1开始编号.对任意第i个节点
- 如果i = 1 , 他的根节点
- 如果i > 1, 他的父节点编号floor(i / 2)
- 如果2i ≤ n, 他的左子节点编号为2i
- 如果2i > n, 他没有左子节点
- 如果2i + 1 ≤ n, 他的右子节点编号2i + 1
- 如果2i + 1 > n, 他没有右子节点
- 一颗有n个节点的完全二叉树(n>0),从上到下,从左到右对节点从0开始编号.对任意第i个节点
- 如果i = 0 , 他的根节点
- 如果i > 0, 他的父节点编号floor((i-1) / 2)
- 如果2i + 1 ≤ n - 1, 他的左子节点编号为2i + 1
- 如果2i + 1 > n - 1, 他没有左子节点
- 如果2i + 2 ≤ n - 1, 他的右子节点编号2i + 2
- 如果2i + 2 > n - 1, 他没有右子节点
参考
M了个J : https://www.cnblogs.com/mjios