专栏首页Java阿呆java源码之树与二叉树

java源码之树与二叉树

树的定义

树(Tree)是n(n≥0) 个结点的有限集。n=0 时称为空树。在任意一棵非空树中:

1.有且仅有一个特定的称为根(Root)的结点; 2.当n>1 时,其余结点可分为m (m>0) 个互不相交的有限集T1 、T2、……、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。 下图就是一棵树:

相关概念

结点分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree) 。度为0的结点称为叶结点(Leaf) 或终端结点;度不为0 的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。

如下图所示,A结点为根节点,G、H、I、J、F为叶节点,其余节点则为内部节点,此树的度为3。

结点间关系

结点的子树的根称为该结点的孩子(Child),相应地,该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。反之,以某结点为根的子树中的任一结点都称为该结点的子孙。

深度

结点的层次(LeveI)从根开始定义起,根为第一层,根的孩子为第二层。若某结点在第L层,则其子树的根就在第L+1 层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度 。

有序树,无序树

如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称该树为有序树,否则称为无序树。

二叉树

二叉树(Binary Tree)是n(n ≥ 0) 个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树遍历

二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次旦仅被访问一次。

前序遍历

规则是若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树, 再前序遍历右子树。

如下图所示,遍历结果为:ABDGHCEIF。

中序遍历

规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点) ,中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树。

如下图所示,遍历结果为:GDHBAEICF。

后序遍历

规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点。

如下图所示,遍历结果为:GHDBIEFCA。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • java源码之二叉查找树与二叉平衡树

    二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树:

    Java阿呆
  • ORM与反射

    对象关系模型 关系模型(数据库表): 表、字段、字段类型 对象模型(java实体类):类、属性、属性类型 通过ORM框架解除模型之间的阻抗。

    Java阿呆
  • 浅谈ArrayList

    contains(Object o):判断ArrayList中是否包含指定元素,返回Boolean类型

    Java阿呆
  • 通过2-3-4树理解红黑树

    前言 红黑树是数据结构中比较复杂的一种,最近与它交集颇多,于是花了一周的空闲时间跟它死磕,终于弄明白并实现了红黑树。写文总结一下,希望能给试图理解红黑树的同学一...

    枕边书
  • BTree,B-Tree,B+Tree,B*Tree都是什么

           3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

    阳光岛主
  • 数据结构与算法 -树

    树型结构是一类重要的非线性结构,树型结构是结点之间有分支, 并且具有层次关系的结构,它非常类似于自然界中的树。

    越陌度阡
  • 30 张图带你彻底理解红黑树

    本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难...

    智能算法
  • 树型结构--树的定义和基本术语(十六)

    树是n(n>=0)个结点的有限集合T,当n=0时,称为空树,当n>0时,该集合满足如下条件: 1.其中必有一个称为根的特定结点,它没有直接前驱,但是有零个或多...

    花狗Fdog
  • 「学习笔记」树和二叉树

    由 n(n ≧ 0)个结点组成的有序集合,n = 0 时称为空二叉树;n > 0 的二叉树是由一个根节点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。...

    FoamValue
  • 从B 树、B+ 树、B* 树谈到R 树

    说明:本文从B树开始谈起,然后论述B+树、B*树,最后谈到R 树。其中B树、B+树及B*树部分由weedge完成,R 树部分由Frankie完成,全文最终由Ju...

    bear_fish

扫码关注云+社区

领取腾讯云代金券