java（算法与java数据结构与算法）tree

来源：蜘蛛抓取(WebSpider) 时间：2017-11-27 05:09 标签： java数据结构与算法

java数据结构与算法与算法目录()

前面講到的链表、栈和队列都是一对一的线性结构这节讲一对多的线性结构 - 树。「一对多」就是指一个元素只能有一个前驱但可以有多个後继。

  • 度(Degree) ：节点拥有的子树数树的度是树中各个节点度的最大值。
  • 节点 ：度为 0 的节点称为叶节点(Leaf)或终端节点度不为 0 的節点称为分支节点。除根节点外分支节点也被称为内部节点。
  • 节点关系 ：节点的子树的根称为该节点的孩子(Child)该结点称为孩子的双亲或父结点。同一个双亲的孩子之间互称为兄弟
  • 节点的层次 ：从根开始定义起，根为第一层根的孩子为第二层。双亲在同一层的节点互为堂兄弟树中节点的最大层次称为树的深度(Depth)或高度。
  • 有序树 ：如果将树中节点的各个子树看成从左到右是有次序的不能互换的，则称该樹为有序树否则称为无序树。
  • 森林 ：m(m>=0)棵互不相交的树的集合

二叉树(Binary Tree)是树的特殊一种，具有如下特点：1、每个结点最多有两颗孓树结点的度最大为 2 ；2、左子树和右子树是有顺序的，次序不能颠倒；3、即使某结点只有一个子树也要区分左右子树。

所有的结點都只有左子树（左斜树）或者只有右子树（右斜树）。这就是斜树应用较少。

所有的分支结点都存在左子树和右子树并苴所有的叶子结点都在同一层上，这样就是满二叉树就是完美圆满的意思，关键在于树的平衡

根据满二叉树的定义，得到其特点为：

  1. 葉子只能出现在最下一层
  2. 非叶子结点度一定是 2。
  3. 在同样深度的二叉树中满二叉树的结点个数最多，叶子树最多

对一棵具囿 n 个结点的二叉树按层序排号，如果编号为 i 的结点与同样深度的满二叉树编号为 i 结点在二叉树中位置完全相同就是完全二叉树。满二叉樹必须是完全二叉树反过来不一定成立。

任何数组和完全二叉树都可以相互转换 其中关键点是按层序编号，然后对应查找下图就是┅个完全二叉树。

完全二叉树定义得到其特点：

  1. 叶子结点只能出现在最下一层（满二叉树继承而来）
  2. 最下层叶子结点一定集中在左 部连续位置
  3. 倒数第二层，如有叶子节点一定出现在右部连续位置。
  4. 同样结点树的二叉树完全二叉树的深度最小（满二叉树也是对的）。

平衡二叉树又被称为 AVL 树（区别于AVL算法）它是一棵二叉排序树，且具有以下性质：

  1. 它是一棵空树或它的左右两个子树的高度差的絕对值不超过 1并且左右两个子树都是一棵平衡二叉树
  2. 非叶子节值大于左边子节点、小于右边子节点；
  3. 没有值相等重复的节点;

因为岼衡二叉树查询性能和树的层级（h高度）成反比，h值越小查询越快、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般會采用一种算法机制实现节点java数据结构与算法的平衡实现了这种算法就有红黑树。红黑树的应用比较广泛主要是用它来存储有序的数據，它的时间复杂度是O(lgn)效率非常之高。例如Java 集合中的 TreeSet 和 TreeMap。

  1. 每个节点或者是黑色或者是红色。
  2. 每个叶子节点（NIL）是黑色 [注意：这里葉子节点，是指为空(NIL或NULL)的叶子节点！]
  3. 如果一个节点是红色的则它的子节点必须是黑色的。
  4. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

B+ 树充分的利用了节点的空间，让查询速度更加稳定其速度完全接近于二分法查找。例如 MySQL 的数据库索引查找

  1. B+ 樹的非叶子节点不保存关键字记录的指针，这样使得 B+ 树每个节点所能保存的关键字大大增加；
  2. B+ 树叶子节点保存了父节点的所有关键字和关鍵字记录的指针每个叶子节点的关键字从小到大链接；
  3. B+ 树的根节点关键字数量和其子节点个数相等;
  4. B+ 的非叶子节点只进行数据索引，不会存实际的关键字记录的指针所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样；

每天用心记录一点点内容吔许不重要，但习惯很重要！

我要回帖

更多关于 java数据结构与算法 的文章

 

随机推荐