二叉树

介绍二叉树之前先说下树状结构,不同于线性结构只有前后两个方向,树状结构可以有多个方向。

tree.png
树的基本概念
  • 节点、根节点、父节点、子节点、兄弟节点
    如上图中的每个元素都一个节点,节点A是根节点,A是B和C的父节点,B和C是A的子节点,B和C互相是兄弟节点;

  • 一棵树可以没有任何节点,称为空树

  • 一棵树可以只有一个节点,即只有根节点

  • 子树、左子树、右字树
    如上图中,子树B是A的左子树,子树C是A的右子树

  • 节点的度
    子树的个数,等于节点的子节点数

  • 树的度
    所有节点度中的最大值

  • 叶子节点
    度为0的节点

  • 非叶子节点
    度不为0的节点

  • 层数
    根节点在第一层,根节点的子节点在第二次,依次往下类推

  • 节点的深度
    从根节点到当前节点唯一路径上的节点总数

  • 节点的高度
    从当前节点到最远叶子节点的路径上的节点总数

  • 树的深度
    所有节点深度中的最大值

  • 树的高度
    所有节点高度中的最大值

  • 树的深度等于树的高度

  • 有序树
    树中任意节点的子节点之间有顺序关系

  • 无序树
    树中任意节点之间没有顺序关系,也称“自由树”

  • 森林
    有n(n ≥0)课互不相交的树组成的集合

二叉树(BinaryTree)

每个节点的度最大为2,左子树和右子树是有序的,即使只有一颗子树也要区分左右的树是二叉树;


BinaryTree.png
二叉树的性质
  • 非空二叉树的第i层,最多有2^{i-1}个节点(i>=1)
  • 高度为h的二叉树上最多有2^{h -1}个节点(h>=1)
  • 对于任意一课非空二叉树,如果叶子节点个数为n0,度为2的节点数为n2
  • 若度为1的节点数为n1,二叉树的总结点数n = n0 + n1 + n2
  • 二叉树的总边数T = n1 + 2*n2 = n - 1 = n0 + n1 + n2 -1,因此 n0 = n2 + 1
真二叉树

所有节点的度要么为0,要么为2的二叉树称为真二叉树;

满二叉树

最后一层节点的度为0,其他节点的度都为2的二叉树称为满二叉树;


满二叉树.png
完全二叉树

对一棵具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树


完全二叉树.png
  • 叶子节点只会出现最后两层,最后一层的叶子节点都靠左对齐的二叉树

  • 从根节点至倒数第二层是一棵满二叉树

  • 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树

  • 度为1的节点只有左子树

  • 度为1的节点要么是1个,要么是0个

  • 同样节点数量的二叉树,完全二叉树的高度最小

  • 假设完全二叉树的高度为h(h≥1),那么
    至少有2^{h-1} 个节点(2^{0}+2^{1}+···+2^{h-2} + 1)
    最多有2^{h}- 1个节点(2^{0} +2^{1}+···+2^{h-1}) ,满二叉树)

  • 若总结点数为n
    2^{h-1} ≤ n < 2^{h} => h -1≤ {log_2{n}} < h => h = floor({log_2{n}}) + 1

  • 一棵有n个节点的完全二叉树(n>0),从上到下、从左到右对节点从1开始进行编号,对任意第i个节点

排序完全二叉树.png

若i=1,它是根节点
若i>1,它的父节点编号是floor(i/2)
若2i≤n,它的左子节点编号为2i
若 2i>n,它无左子节点
若2i+1 ≤n,它的右子节点编号为2i+1
若2i+1 >n,它无右子节点

从图中可以看到,对于节点i,它的左子节点等于2i,右子节点等于2i+1;

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 树的基本概念 节点,根节点,父节点,子节点,兄弟节点都是属于树的范涛; 一棵树可以没有任何节点,称为空树; 一棵树...
    coder_feng阅读 4,818评论 0 0
  • 介绍 二叉树的结构 二叉树常考的原因有如下几点1、它可以结合链表、栈、队列和字符串等数据结构出题2、需要熟练掌握图...
    雨住多一横阅读 3,214评论 0 1
  • 树形结构是一种十分重要的数据结构。二叉树、树与树林都属于树形结构。 树形结构每个结点最多只有一个前驱结点,但可以有...
    cain_huang阅读 6,112评论 0 11
  • 前言 树是数据结构中的重中之重,尤其以各类二叉树为学习的难点。一直以来,对于树的掌握都是模棱两可的状态,现在希望通...
    MrHorse1992阅读 354,415评论 51 536
  • 树的定义与基本术语   树型结构是一类重要的非线性数据结构,其中以树和二叉树最为常用,是以分支关系定义的层次结构。...
    java技术分享师阅读 4,801评论 0 1