二叉树的种类


    树的基本说明

    树形结构

    二叉树

    多叉树

    树的基本概念

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

    原文链接:,转发请注明来源!