|
二叉树的基本定义 简而言之：二叉树就是度不能超过2的树（每个树只能有两个节点） 满二叉树：
一个二叉树，如果每一个层的结点树达到最大值，则在这个树就是满二叉树 完全二叉树：
叶结点只能出现在最下层和次下层，并且最下面那一层的结点都集中在该层最左边的若干位置的二叉树 二叉查找树
二叉查找树是一种特殊的二叉树，相对较小的值保存在左结点中，较大的值保存在右结点中。
根据对图的观察，我们发现二叉树其实就是由一个一个的结点及其之间的关系组成的，按照面向对象的思想，我们设计一个结点来描述结点这个事务。 首先我们先想着实现二叉树需要一些什么参数？ private static class Node{ public Node left; public Node right; public Integer key; public String value; public Node(Node left, Node right, Integer key, String value) { this.left = left; this.right = right; this.key = key; this.value = value; } }在上面我们定义了left，right，key，value四个参数，并且定义了这个类的构造方法 我们看插入方法put思想： - 如果当树中没有任何一个结点，则直接把新结点当根结点使用
- 如果当前树不为空，就从根结点开始
2-1：如果要查询的key，小于当前结点的key，则继续查找当前结点的左子结点
2-2：如果新结点的key大于当前结点的key，则继续找当前结点的右子结点
2-3：如果新结点的key等于当前结点的key，则树中已经存在这样的结点，替换该结点的value值就好
那么我们要怎么实现呢？ //向树中插入一个键值对 public void put(Integer key,String value){ root=put(root,key,value); } //给指定的数x添加一个键,添加一个键值对，并返回添加后的新数 private Node put(Node tree,Integer key,String value){ if(tree==null){ //个数加1 n++; //直接把新结点当成根结点使用 return new Node(null,null,key,value); } //比较key,如果新结点大于当前结点的key，继续寻找当前结点的右子结点 if(key > tree.key){ tree.right=put(tree.right,key,value); }else if(key<tree.key){ //新结点的key小于当前结点的key,继续找当前结点的左子结点 tree.left=put(tree.left,key,value); }else{ //新结点的key等于当前结点的key tree.value=value; } return tree; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
在上面的代码块中，我们定义了两个put方法，一个是给其他类操作的，一个是给自己类操作的，对于外部的用户来说，他只需要将键值对传递进来就好了，排序是我们程序员的事，所以，我们这里的put只有两个参数： public void put(Integer key,String value)然后我们通过这个put方法再去调用我们内部的put方法，在这个方法中，我们首先要把我们的根结点root传递进去，然后再将前端传给我们的key：value传递进去 private Node put(Node tree,Integer key,String value)这样，我们就可以在这个put上进行我们一开始定义的开发流程了： - 如果树中没有结点，就把当前插入的结点当成首节点使用：
if(tree==null){ //个数加1 n++; //直接把新结点当成根结点使用 return new Node(null,null,key,value); }- 如果树不为空，就从根结点开始遍历，也就是root结点
2-1. 如果要查询的key，小于当前结点的key，则继续查找当前结点的左子结点
//比较key,如果新结点大于当前结点的key，继续寻找当前结点的右子结点 if(key > tree.key){ tree.right=put(tree.right,key,value); }2-2. 如果新结点的key大于当前结点的key，则继续找当前结点的右子结点 else if(key<tree.key){ //新结点的key小于当前结点的key,继续找当前结点的左子结点 tree.left=put(tree.left,key,value); }2-3：如果新结点的key等于当前结点的key，则树中已经存在这样的结点，替换该结点的value值就好 else{ //新结点的key等于当前结点的key tree.value=value; }现在put方法就执行完毕了，我们把一个前端传递过来的值放入了二叉树中. 上面我们已经实现了二叉树中的put方法，按照我的习惯的话呢接下来我们还是先讲思想，讲get方法和delete方法： 查询方法get实现思想：
从根结点开始： - 如果要查询的key小于当前结点的key，则继续查找当前结点的左子结点
- 如果要查询的key大于当前结点的key，则继续找当前结点的右子结点
- 如果要查询的key等于当前结点的key，则树中返回当前结点的value
删除方法delete实现思想： - 找到被删除结点
- 找到被删除结点右子树的最小结点
- 删除右子树中的最小结点
- 让被删除结点的左子树称为最小结点的左子树，让被删除结点的右子树称为最小结点的子树
- 让被删除节点的父结点指向最小结点
按照从简单到困难的准则，我们先从简单的开始，get方法相对于delete而言要简单一点，所以我们先实现get方法 //从树中找到对应的值 public String get(Integer key){ return get(root,key); } private String get(Node tree,Integer key){ if(root==null){ return null; } //比较key,如果新结点大于当前结点的key，继续寻找当前结点的右子结点 if(key > tree.key){ return get(tree.right,key); }else if(key<tree.key){ //比较key,如果新结点大于当前结点的key，继续寻找当前结点的左子结点 return get(tree.left,key); }else{ //要查找的key和当前结点的key相等，返回value return tree.value; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
通过不停的递归调用get方法，我们就可以不断的查找树的左右结点，从而最终返回get到的结果值，这个非常简单，没什么好说的。 接下来比较重要的是delete方法： //从指定的树中，根据key删除键中的键值对 public void delete(Integer key){ root=delete(root,key); } private Node delete(Node tree,Integer key){ if(tree==null){ return null; } if(key > tree.key){ tree.right=delete(tree.right,key); }else if(key<tree.key){ tree.left=delete(tree.left,key); }else{ //待删除的key等于当前结点的key，说明当前结点就是要删除的结点 //1、如果当前结点的右子树不存在，则直接返回当前结点的左子结点 if(tree.right==null){ n--; return tree.left; } //2、如果当前结点的左子树不存在，则直接返回当前结点的右子结点 if(tree.left==null){ n--; return tree.right; } //当前结点的左右子树都存在 //找到右子树中的最小结点 Node minNode=tree.right; //二叉查找树的左结点一定比右结点小 if(minNode.left!=null){ minNode=minNode.left; } //到这里就找到了当前结点右子树中最小的结点minNode //删除右子树中最小的结点 Node node=tree.right; while (node.left!=null){ if(node.left.left==null){ //说明N的左结点就是我们要找的最小结点 node.left=null; }else{ node=node.left; } } //到这里，最小结点已经被删除了 //让被删除结点的左子树成为最小结点的左子树，让被删除结点的右子树，成为最小结点的右子树 minNode.left=tree.left; minNode.right=tree.right; //让被删除结点的父结点指向最小结点 tree=minNode; //个数减1 n--; } return tree; }- 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
上面的这段代码看着很长，且听我与你一一分解 首先我们通过public方法方便别的类调用，用户只需要传递key值进入我们的后台，我们就可以通过后台的查找方法来查找二叉树中的元素，然后对其进行删除。 这同样使用了递归的思想。通过不断的查找二叉树中的元素，找到要删除的那个数据。 if(key > tree.key){ tree.right=delete(tree.right,key); }else if(key<tree.key){ tree.left=delete(tree.left,key); }else{ //待删除的key等于当前结点的key，说明当前结点就是要删除的结点 //1、如果当前结点的右子树不存在，则直接返回当前结点的左子结点 if(tree.right==null){ n--; return tree.left; } //2、如果当前结点的左子树不存在，则直接返回当前结点的右子结点 if(tree.left==null){ n--; return tree.right; } //当前结点的左右子树都存在 //找到右子树中的最小结点 Node minNode=tree.right; //二叉查找树的左结点一定比右结点小 if(minNode.left!=null){ minNode=minNode.left; } //到这里就找到了当前结点右子树中最小的结点minNode //删除右子树中最小的结点 Node node=tree.right; while (node.left!=null){ if(node.left.left==null){ //说明N的左结点就是我们要找的最小结点 node.left=null; }else{ node=node.left; } } //到这里，最小结点已经被删除了 //让被删除结点的左子树成为最小结点的左子树，让被删除结点的右子树，成为最小结点的右子树 minNode.left=tree.left; minNode.right=tree.right; //让被删除结点的父结点指向最小结点 tree=minNode; //个数减1 n--; }- 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
如果当前递归到的这个结点的元素值小于我们用户传递进来的key的话我们将其往左进行递归 if(key > tree.key){ tree.right=delete(tree.right,key); }如果大于的话我们就往右进行递归 else if(key<tree.key){ tree.left=delete(tree.left,key); }如果说用户传递过来的key与当前结点的key值相等的话，那么说明当前的这个结点就是我们要删除的这个结点 else{ //待删除的key等于当前结点的key，说明当前结点就是要删除的结点 //1、如果当前结点的右子树不存在，则直接返回当前结点的左子结点 if(tree.right==null){ n--; return tree.left; } //2、如果当前结点的左子树不存在，则直接返回当前结点的右子结点 if(tree.left==null){ n--; return tree.right; } //当前结点的左右子树都存在 //找到右子树中的最小结点 Node minNode=tree.right; //二叉查找树的左结点一定比右结点小 if(minNode.left!=null){ minNode=minNode.left; } //到这里就找到了当前结点右子树中最小的结点minNode //删除右子树中最小的结点 Node node=tree.right; while (node.left!=null){ if(node.left.left==null){ //说明N的左结点就是我们要找的最小结点 node.left=null; }else{ node=node.left; } } //到这里，最小结点已经被删除了 //让被删除结点的左子树成为最小结点的左子树，让被删除结点的右子树，成为最小结点的右子树 minNode.left=tree.left; minNode.right=tree.right; //让被删除结点的父结点指向最小结点 tree=minNode; //个数减1 n--; } return tree; }- 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
现在又要研究二叉树中的删除方法中结点的性质了，我们既然要把这个元素进行删除操作的话，那么是不是，我们就要将他的子结点的层级往上提升一级，那么我们接着研究： //待删除的key等于当前结点的key，说明当前结点就是要删除的结点 //1、如果当前结点的右子树不存在，则直接返回当前结点的左子结点 if(tree.right==null){ n--; return tree.left; } //2、如果当前结点的左子树不存在，则直接返回当前结点的右子结点 if(tree.left==null){ n--; return tree.right; }如果当前结点的右子树不存在，那么我们就把该结点的左子树给他提上去
如果当前结点的左子树不存在，那么我们就把他的右子树提上去 如果说当前结点的左右子树都存在的话，那么就有点小麻烦了，那么我们就要从要被删除的这个结点的右子树中找到他的最小元素，然后把他的最小元素给他提上去。 //到这里就找到了当前结点右子树中最小的结点minNode //删除右子树中最小的结点 Node node=tree.right; while (node.left!=null){ if(node.left.left==null){ //说明N的左结点就是我们要找的最小结点 node.left=null; }else{ node=node.left; } } //到这里，最小结点已经被删除了 //让被删除结点的左子树成为最小结点的左子树，让被删除结点的右子树，成为最小结点的右子树 minNode.left=tree.left; minNode.right=tree.right; //让被删除结点的父结点指向最小结点 tree=minNode; //个数减1 n--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
最后在我们所有操作都已经执行完毕之后，我们只要返回这个改变之后的tree就好了 好了，现在我们创建一个外部类Test1来验证此程序的正确性 class Test1{ public static void main(String[ args) { BinaryTree tree=new BinaryTree(); tree.put(8,"鸡霸"); tree.put(7,"田七"); tree.put(9,"吴久"); tree.put(3,"张三"); tree.put(6,"陆远"); System.out.println(tree.get(7)); tree.delete(6); tree.delete(9); tree.delete(3); System.out.println(tree.size()); }}然后我放出全部代码方便大家实验： package com.gm.tree;public class BinaryTree { //记录一个根结点 private Node root; //记录树中的元素个数 private int n; public BinaryTree() { } //向树中插入一个键值对 public void put(Integer key,String value){ root=put(root,key,value); } //给指定的数x添加一个键,添加一个键值对，并返回添加后的新数 private Node put(Node tree,Integer key,String value){ if(tree==null){ //个数加1 n++; //直接把新结点当成根结点使用 return new Node(null,null,key,value); } //比较key,如果新结点大于当前结点的key，继续寻找当前结点的右子结点 if(key > tree.key){ tree.right=put(tree.right,key,value); }else if(key<tree.key){ //新结点的key小于当前结点的key,继续找当前结点的左子结点 tree.left=put(tree.left,key,value); }else{ //新结点的key等于当前结点的key tree.value=value; } return tree; } //从树中找到对应的值 public String get(Integer key){ return get(root,key); } private String get(Node tree,Integer key){ if(root==null){ return null; } //比较key,如果新结点大于当前结点的key，继续寻找当前结点的右子结点 if(key > tree.key){ return get(tree.right,key); }else if(key<tree.key){ //比较key,如果新结点大于当前结点的key，继续寻找当前结点的左子结点 return get(tree.left,key); }else{ //要查找的key和当前结点的key相等，返回value return tree.value; } } //从指定的树中，根据key删除键中的键值对 public void delete(Integer key){ root=delete(root,key); } private Node delete(Node tree,Integer key){ if(tree==null){ return null; } if(key > tree.key){ tree.right=delete(tree.right,key); }else if(key<tree.key){ tree.left=delete(tree.left,key); }else{ //待删除的key等于当前结点的key，说明当前结点就是要删除的结点 //1、如果当前结点的右子树不存在，则直接返回当前结点的左子结点 if(tree.right==null){ n--; return tree.left; } //2、如果当前结点的左子树不存在，则直接返回当前结点的右子结点 if(tree.left==null){ n--; return tree.right; } //当前结点的左右子树都存在 //找到右子树中的最小结点 Node minNode=tree.right; //二叉查找树的左结点一定比右结点小 if(minNode.left!=null){ minNode=minNode.left; } //到这里就找到了当前结点右子树中最小的结点minNode //删除右子树中最小的结点 Node node=tree.right; while (node.left!=null){ if(node.left.left==null){ //说明N的左结点就是我们要找的最小结点 node.left=null; }else{ node=node.left; } } //到这里，最小结点已经被删除了 //让被删除结点的左子树成为最小结点的左子树，让被删除结点的右子树，成为最小结点的右子树 minNode.left=tree.left; minNode.right=tree.right; //让被删除结点的父结点指向最小结点 tree=minNode; //个数减1 n--; } return tree; } public int size(){ return n; } private static class Node{ public Node left; public Node right; public Integer key; public String value; public Node(Node left, Node right, Integer key, String value) { this.left = left; this.right = right; this.key = key; this.value = value; } }}class Test1{ public static void main(String[ args) { BinaryTree tree=new BinaryTree(); tree.put(8,"雷霸天"); tree.put(7,"田七"); tree.put(9,"吴久"); tree.put(3,"张三"); tree.put(6,"陆远"); System.out.println(tree.get(7)); tree.delete(6); tree.delete(9); tree.delete(3); System.out.println(tree.size()); }}- 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
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
感谢观看！ 学习视频资料：http://www.makeru.com.cn/live/1392_1164.html?s=143793
|
/2 
|手机版|OpenEdv-开源电子网
( 粤ICP备12000418号-1 )
发表于 2020-11-25 17:17:55
