- 1Python实现微信自动回复信息的功能（根据不同信息回复对应的信息），手把手搭建加代码分析_python自动回复微信消息
- 2基于IMX6ULL的嵌入式Linux开发学习笔记——（1）总体简述_嵌入式开发 虚拟机 切换目录
- 3MAC10.15.4无法开启ToDesk屏幕录制权限_todesk录屏功能开启
- 4Verilog | 分频电路实现_verilog分频
- 5Python 基础教程【2】：条件语句和循环语句_python 条件语句 写法
- 6Engineering Applications of Artificial Intelligence（EAAI）投稿过程
- 7国际绝对音名标准频率定义（32位无符号整型精度、十二等律体系、A4=440.01000Hz）_a0频率
- 8分布式数据库Redis的简介、安装与设置使用指令_、redis csdn
- 9DAY24：信息搜集_ksubdomain +fscan
- 10Linux系统安装Hadoop步骤详解_linux安装hadoop
数据结构之树的详细介绍_treenode是什么数据类型
赞
踩
树的介绍
定义
树（tree）是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。
- 它是由 n（n >= 0）个有限节点通过连接它们的边组成一个具有层次关系的集合。
- n = 0 时称为空树。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
- 当n>1时，其余节点可以分为m（m>0）个互不相交的有限集合，其中每一个集合本身又是一棵树，称为结点的子树。
如下图就是一颗树：
树的基本概念
- 树的结点：由一个数据元素和若干个指向其子树的分支组成。
- 结点的度：结点所拥有的子树的个数（即分支数）称为该结点的度。
- 叶子结点：度为0的结点称为叶子结点，或者称为终端结点。
- 分支结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点由叶子结点和分支结点组成。
孩子、双亲、兄弟：树中一个结点的子树的根结点称为这个结点的孩子；这个结点称为它孩子结点的双亲；具有同一个双亲的孩子结点互称为兄弟。 - 路径、路径长度：如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（i为1~k，不等于k的值），就把n1,n2,…,nk称为一条由n1至nk的路径。路径长度是指路径上经过的边的数量，所以这条路径的长度是k-1。
- 祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。
- 结点的层数：规定树的根结点的层数为1，其余结点的层数等于它双亲结点的层数加1。
- 树的深度（高度）：树中所有结点中的最大层数称为树的深度。
- 树的度：树中各结点中度的最大值称为该树的度。
- 有序树、无序树：如果一棵树中结点的各子树从左到右都是有次序的，不能交换的，称这棵树为有序树；反之为无序树。
- 森林：ｍ（ｍ＞＝０）棵互不相交的树的集合。
- 同构：对于两棵树，若通过对各结点适当重命名，就可以使这两棵树完全相等（结点对应相等，结点关系也相等），称这两棵树同构。
- 层序编号：将书中结点按照从上层到下层、同层从左到右的次序依次给它们编号１开始的自然数。
树的存储结构及实现
父结点（双亲）表示法
树，是由节点组成，而除根节点的每个节点一定只有一个父节点，所以可以利用每个节点只有一个父节点的特性，使用父节点来构造树。
如下图所示：
代码示例如下：
public class TreeNodeWithParrent<T> { private T data; private TreeNodeWithParrent parent; public T getData(){ return data; } public void setData(T data){ this.data = data; } public TreeNodeWithParrent getParent(){ return parent; } public void TreeNodeWithParrent(TreeNodeWithParrent parent){ this.parent = parent; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
孩子表示法
由于双亲表示法获取某结点的所有后代有点麻烦，我们索性让每个结点记住他所有的孩子。但是由于一个结点拥有的孩子个数是一个不确定的值，虽然最多只有树的度那么多，但是大多数结点的孩子个数并没有那么多，如果用数组来存放所有孩子，对于大多数结点来说太浪费空间了。自然我们容易想到用一个可变容量的表来存，选用Java内置的LinkedList是个不错的选择。先用一个数组存放所有的结点信息，该链表只需存储结点在数组中的下标就行了。
代码示例如下：
public class TreeNodeWithChild<T> { private T data; private List<TreeNodeWithChild> children; public TreeNodeWithChild(T data) { this.data = data; this.children = new LinkedList<>(); } public TreeNodeWithChild(T data, TreeNodeWithChild child) { this.data = data; this.children = new LinkedList<>(); this.children.add(child); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
孩子兄弟表示法
还有一种表示法，关注某结点的孩子结点之间的关系，他们互为兄弟。一个结点可能有孩子，也有可能有兄弟，也可能两者都有，或者两者都没。基于这种思想，可以用具有两个指针域（一个指向当前结点的孩子，一个指向其兄弟）的链表实现，**这种链表又称为二叉链表。特别注意的是，双亲表示法和孩子结点表示法，都使用了数组存放每一个结点的信息，若稍加分析，使用数组是有必要的。**但在这种结构中，我们摒弃了数组，根结点可以作为头指针，以此开始可以遍历到树的全部结点——根结点肯定是没有兄弟的（根结点如果有兄弟这棵树就有两个根结点了），如果它没有孩子，则这棵树只有根结点；若有孩子，就如下图，它的nextChild的指针域就不为空，现在看这个左孩子，有兄弟（实际就是根结点的第二个孩子）还有孩子，则左孩子的两个指针域都不为空，再看这个左孩子的nextSib，他有个孩子…一直这样下去，对吧，能够访问到树的全部结点的。
代码示例如下：
public class TreeNodeWithBro<T> { private T data; private List<TreeNodeWithChild> children; private TreeNodeWithBro<T> bro; public T getData() { return data; } public TreeNodeWithBro(T data) { this.data = data; } public List<TreeNodeWithChild> getChild() { return children; } public TreeNodeWithBro<T> getBro() { return bro; } public void addChild(TreeNodeWithChild child) { children.add(child); } public void setBro(TreeNodeWithBro bro) { this.bro = bro; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
树的分类
二叉树
-
线索化二叉树
对于一个有n个节点的二叉链表，每个节点有指向左右节点的2个指针域，整个二叉链表存在2n个指针域。而n个节点的二叉链表有n-1条分支线，那么空指针域的个数=2n-(n-1) = n+1个空指针域。利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的（一个节点的前一个节点称为前驱节点）前驱和后继节点（一个节点的后一个节点称为后继节点）的指针（ 这种附加的指针称为“线索”）。加上了这种指针的二叉链表称为线索链表，相应的二叉树称为线索二叉树（ThreadBinaryTree）。根据线索性质的不同，线索二叉树可分为前序线索二叉树，中序线索二叉树，后序线索二叉树这三种。
-
二叉排序树
二叉查找树是一种动态查找表（图a），具有这些性质：
1）若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值；
2）若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值；
3）其他的左右子树也分别为二叉查找树；
4）二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。 -
平衡二叉树
含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树（图b），具有以下性质：
（1）要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1；
（2）其左右子树也都是平衡二叉树；
（3）二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。 -
赫夫曼树
给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为赫夫曼树或者哈夫曼树。
定义:
路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权值。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权值的乘积。
树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
-
红黑树
红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：
（1）根节点只能是黑色；
（2）红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色；
（3）其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间；
（4）在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。
多叉树
-
B树
B-树是一种平衡多路查找树，它在文件系统中很有用。一棵m阶B-树（图d为4阶B-树），具有下列性质：
（1）树中每个节点至多有m棵子树；
（2）若根节点不是叶子节点，则至少有2棵子树；
（3）除根节点之外的所有非终端节点至少有
棵子树；
（4）每个节点中的信息结构为（A0,K1,A1,K2…Kn,An），其中n表示关键字个数，Ki为关键字，Ai为指针；
（5）所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。 -
B+树
B+数是B-树的一种变形，它与B-树的差别在于（图e为3阶B+树）：
（1）有n棵子树的节点含有n个关键字；
（2）所有的叶子节点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子节点本身按关键字大小自小到大顺序链接；
（3）所有非终端节点可以看成是索引部分，节点中仅含有其子树（根节点）中最大（或最小）关键字，所有B+树更像一个索引顺序表；
（4）对B+树进行查找运算，一是从最小关键字起进行顺序查找，二是从根节点开始，进行随机查找。 -
字典树（trie树/前缀树/单词查找树）
字典树是一种以树形结构保存大量字符串。以便于字符串的统计和查找，经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。具有以下特点（图f）：
（1）根节点为空；
（2）除根节点外，每个节点包含一个字符；
（3）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
（4）每个字符串在建立字典树的过程中都要加上一个区分的结束符，避免某个短字符串正好是某个长字符串的前缀而淹没。 -
后缀树
所谓后缀树，就是包含一则字符串所有后缀的压缩了的字典树。先说说后缀的定义。给定一长度为n的字符串S=S1S2…Si…Sn，和整数i，1 <= i <= n，子串SiSi+1…Sn都是字符串S的后缀。以字符串S=XMADAMYX为例，它的长度为8，所以S[1…8], S[2…8], … , S[8…8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀。对于后缀S[i…n]，我们说这项后缀起始于i。
- S[1…8], XMADAMYX， 也就是字符串本身，起始位置为1
- S[2…8], MADAMYX，起始位置为2
- S[3…8], ADAMYX，起始位置为3
- S[4…8], DAMYX，起始位置为4
- S[5…8], AMYX，起始位置为5
- S[6…8], MYX，起始位置为6
- S[7…8], YX，起始位置为7
- S[8…8], X，起始位置为8
- 空字串。记为$。
所有这些后缀字符串组成一棵字典树。
-
广义后缀树
广义后缀树是好几个字符串的的所有后缀组成的字典树，同样每个字符串的所有后缀都具有一个相同的结束符，不同字符串的结束符不同。
传统的后缀树只能处理一个单词的所有后缀。广义后缀树存储任意多个单词的所有后缀。例如字符串“abab”和“baba”，首先将它们使用特殊结束符链接起来，如表示成“ababbaba#”,然后求连接后的新字符的后缀树，遍历所得后缀树，如遇到特殊字符，如“
”,"#"等则去掉以该节点为跟的子树，最后所得后缀树即为原字符串组的广义后缀树。其实质是将两个字符串的所有后缀，即：abab,b*a*b**,ab,b,baba#,aba#,ba#,a#,组成字典树，再进行压缩处理。广义后缀树的一个常应用就是判断两个字符串的相识度。
二叉树
二叉树的定义
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。
如下图所示：
static final class Entry<T extends Comparable<T>>{ //保存的数据 private T item; //左子树 private Entry<T> left; //右子树 private Entry<T> right; //父节点 private Entry<T> parent; //根节点，可选 private Entry<T> root; //数据量，可选 private int size = 0; Entry(T item,Entry<T> parent){ this.item = item; this.parent = parent; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
二叉树添加元素
public T put(T item){ //每次添加数据的时候都是从根节点向下遍历 Entry<T> t = root; if (t == null){ //当前的叉树树的为空，将新节点设置为根节点，父节点为null root = new Entry<>(item,null); size++; return root.item; } //自然排序结果，如果传入的数据小于当前节点返回-1，大于当前节点返回1，否则返回0 int ret = 0; //记录父节点 Entry<T> p = t; while (t != null){ //与当前节点比较 ret = item.compareTo(t.item); p = t; //插入节点比当前节点小，把当前节点设置为左子节点，然后与左子比较，以此类推找到合适的位置 if (ret < 0) t = t.left; //大于当前节点 else if (ret > 0) t = t.right; else { //相等就把旧值覆盖掉 t.item = item; return t.item; } } //创建新节点 Entry<T> e = new Entry<>(item,p); //根据比较结果将新节点放入合适的位置 if (ret < 0) p.left = e; else p.right = e; size++; return e.item; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
二叉树删除数据
/** * 删除元素 * 删除元素如果细分的话，可以分为4中：没有子节点，只有左节点，只有右节点，有两个子节点 * 1）没有子节点这种情况比较简单，直接删除就可以了 * 2）只有左节点或右节点，这两种情况处理方式是一致的，只是方向相反，所以在一起讲了， * 将删除节点的父节点的左节点（右节点）指向删除节点的子节点，将左节点（右节点）指向删除节点的父节点 * 3）有两个子节点，这种情况相对来说比较复杂一点： * 找到删除节点的前驱节点或后继节点，然后将前驱或后继节点的值赋给删除节点，然后将前驱或后继节点删除。本质是删除前驱或后继节点 * 前驱节点的特点： * 1）删除的左子节点没有右子节点，那么左子节点即为前驱节点 * 2）删除节点的左子节点有右子节点，那么最右边的最后一个节点即为前驱节点 * 后继节点的特点： * 与前驱节点刚好相反，总是右子节点，或则右子节点的最左子节点;例如：删除节点为c ，那么前驱节点为 m，后继节点为n * a * / \ * b c * / \ / \ * d e f g * / \ / \ / \ / \ * @param item 删除元素 h i j k l m n o * @return 删除结果 */ public boolean remove(T item){ //获取删除节点 Entry<T> delEntry = getEntry(item); if (delEntry == null) return false; //删除节点的父节点 Entry<T> p = delEntry.parent; size--; //情况1：没有子节点 if (delEntry.left == null && delEntry.right == null){ //删除节点为根节点 if (delEntry == root){ root = null; }else {//非根节点 //删除的是父节点的左节点 if (delEntry == p.left){ p.left = null; }else {//删除右节点 p.right = null; } } //情况2：删除的节点只有左节点 }else if (delEntry.right == null){ Entry<T> lc = delEntry.left; //删除的节点为根节点，将删除节点的左节点设置成根节点 if (p == null) { lc.parent = null; root = lc; } else {//非根节点 if (delEntry == p.left){//删除左节点 p.left = lc; }else {//删除右节点 p.right = lc; } lc.parent = p; } //情况3：删除节点只有右节点 }else if (delEntry.left == null){ Entry<T> rc = delEntry.right; //删除根节点 if (p == null) { rc.parent = null; root = rc; }else {//删除非根节点 if (delEntry == p.left) p.left = rc; else p.right = rc; rc.parent = p; } //情况4：删除节点有两个子节点 }else {//有两个节点,找到后继节点，将值赋给删除节点，然后将后继节点删除掉即可 Entry<T> successor = successor(delEntry);//获取到后继节点 delEntry.item = successor.item; //后继节点为右子节点 if (delEntry.right == successor){ //右子节点有右子节点 if (successor.right != null) { delEntry.right = successor.right; successor.right.parent = delEntry; }else {//右子节点没有子节点 delEntry.right = null; } }else {//后继节点必定是左节点 successor.parent.left = null; } return true; } //让gc回收 delEntry.parent = null; delEntry.left = null; delEntry.right = null; return true; } /** * 获取节点节点 * @param item 获取节点 * @return 获取到的节点，可能为null */ private Entry<T> getEntry(T item){ Entry<T> t = root; int ret; //从根节点开始遍历 for (;t != null;){ ret = item.compareTo(t.item); if (ret < 0) t = t.left; else if (ret > 0) t = t.right; else return t; } return null; } /** * 查找后继节点 * @param delEntry 删除节点 * @return 后继节点 */ private Entry<T> successor(Entry<T> delEntry) { Entry<T> r = delEntry.right;//r节点必定不为空 while (r.left != null){ r = r.left; } return r; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
二叉树查询节点
/** * 判断是否存在该元素 * @param item 查找元素 * @return 结果 */ public boolean contains(T item){ return getEntry(item) != null; } /** * 获取节点节点 * @param item 获取节点 * @return 获取到的节点，可能为null */ private Entry<T> getEntry(T item){ Entry<T> t = root; int ret; //从根节点开始遍历 for (;t != null;){ ret = item.compareTo(t.item); if (ret < 0) t = t.left; else if (ret > 0) t = t.right; else return t; } return null; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
