二叉树可以有几种基本形态（二叉树的种类）

二叉树可以有几种基本形态（二叉树的种类）节点的高度: 从当前节点到最远叶子节点的路径的节点数 比如1的高度.要经过1 2 22 221. 所以高度为4节点的深度: 从根节点到当前节点的路径经过的节点数 比如21的深度.就是1 2 21. 所以深度为3节点的度:子树的个数 比如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层

树的基本说明树形结构二叉树

多叉树

树的基本概念

节点 : 所有的元素都是 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