二叉树的种类

欢迎大家来到IT世界,在知识的湖畔探索吧!

欢迎大家来到IT世界,在知识的湖畔探索吧!

树的基本说明

树形结构

二叉树

多叉树

树的基本概念

空树: 没有任何节点叫做空树

层数:如果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