树 二叉树 为什么需要树这种数据结构
数组存储方式的分析
优点:通过下标方式访问元素,速度快。对于有序数组,还可使用二分查找提高检索速度。
缺点:如果要检索具体某个值,或者插入值(按一定顺序)会整体移动,效率较低 [示意图]
链式存储方式的分析
优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点,只需要将插入节点,链接到链表中即可, 删除效率也很好)。
缺点:在进行检索时,效率仍然较低,比如(检索某个值,需要从头节点开始遍历)
树存储方式的分析
能提高数据存储,读取的效率, 比如利用 **二叉排序树(Binary Sort Tree)**,既可以保证数据的检索速度,同时也可以保证数据的插入,删除,修改的速度。
树示意图 * *
树的常用术语(结合示意图理解):
节点
根节点
父节点
子节点
叶子节点 (没有子节点的节点)
节点的权(节点值)
路径(从root节点找到该节点的路线)
层
子树
树的高度(最大层数)
森林 :多颗子树构成森林
二叉树的概念
树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。
二叉树的子节点分为左节点和右节点。
如果该二叉树的所有叶子节点都在最后一层,并且结点总数= 2^n -1 , n 为层数,则我们称为满二叉树。
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为完全二叉树
* *
二叉树遍历的说明
前序遍历: 先输出父节点,再遍历左子树和右子树
中序遍历: 先遍历左子树,再输出父节点,再遍历右子树
后序遍历: 先遍历左子树,再遍历右子树,最后输出父节点
小结: 看输出父节点的顺序,就确定是前序,中序还是后序
二叉树-遍历节点
创建一棵二叉树
前序遍历
先输出当前节点(初始时是root节点)
如果左子节点不为空,则递归继续前序遍历
如果右子节点不为空,则递归继续前序遍历
中序遍历
如果当前节点的左子节点不为空,则递归继续中序遍历
输出当前节点
如果当前节点的右子节点不为空,则递归继续中序遍历
后序遍历
如果当前节点的左子节点不为空,则递归继续后序遍历
如果当前节点的右子节点不为空,则递归继续后序遍历
输出当前节点
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 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 public class BinaryTreeDemo { public static void main (String[] args) { BinaryTree binaryTree=new BinaryTree (); HeroNode root = new HeroNode (1 ,"宋江" ); HeroNode node2 = new HeroNode (2 ,"吴用" ); HeroNode node3 = new HeroNode (3 ,"卢俊义" ); HeroNode node4 = new HeroNode (4 ,"林冲" ); HeroNode node5 = new HeroNode (5 ,"关胜" ); binaryTree.setRoot(root); root.setLeft(node2); root.setRight(node3); node3.setRight(node4); node3.setLeft(node5); System.out.println("前序遍历:" ); binaryTree.preOrder(); System.out.println("中序遍历:" ); binaryTree.infixOrder(); System.out.println("后序遍历:" ); binaryTree.postOrder(); } } class BinaryTree { private HeroNode root; public void setRoot (HeroNode root) { this .root = root; } public void preOrder () { if (this .root != null ) { this .root.preOrder(); } else { System.out.println("二叉树为空,无法遍历" ); } } public void infixOrder () { if (this .root != null ) { this .root.infixOrder(); } else { System.out.println("二叉树为空,无法遍历" ); } } public void postOrder () { if (this .root != null ) { this .root.postOrder(); } else { System.out.println("二叉树为空,无法遍历" ); } } } class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode (int no, String name) { super (); this .no = no; this .name = name; } public int getNo () { return no; } public void setNo (int no) { this .no = no; } public String getName () { return name; } public void setName (String name) { this .name = name; } public HeroNode getLeft () { return left; } public void setLeft (HeroNode left) { this .left = left; } public HeroNode getRight () { return right; } public void setRight (HeroNode right) { this .right = right; } @Override public String toString () { return "HeroNode [no=" + no + ", name=" + name + "]" ; } public void preOrder () { System.out.println(this ); if (this .left != null ) { this .left.preOrder(); } if (this .right != null ) { this .right.preOrder(); } } public void infixOrder () { if (this .left != null ) { this .left.infixOrder(); } System.out.println(this ); if (this .right != null ) { this .right.infixOrder(); } } public void postOrder () { if (this .left != null ) { this .left.postOrder(); } if (this .right != null ) { this .right.postOrder(); } System.out.println(this ); } }
二叉树-查找指定节点 前序查找
先判断当前节点的no是否等于要查找的节点
如果相等,则返回当前节点
如果不等,则判断当前节点的左子节点是否为空,如果不为空,则递归前序查找
如果左递归前序查找,找到节点,则返回,否则继续判断当前节点的右子节点是否为空,如果不为空,则继续向右递归前序查找
中序查找 先判断当前节点的左子节点是否为空,如果不为空,则递归中序查找
如果找到,则返回,如果没有找到,就和当前节点比较,如果是则返回当前节点,否则继续向右递归中序查找
如果右递归中序查找,找到就返回,否则返回null
后序查找 先判断当前节点的左子节点是否为空,如果不为空,则递归后序查找
如果找到,就返回,如果没有找到,就判断当前节点的右子节点是否为空,如果不为空,则右递归后序查找
如果找到就返回,否则就和当前节点进行比较,如果是就返回,否则返回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 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 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 public class BinaryTreeDemo { public static void main (String[] args) { BinaryTree binaryTree = new BinaryTree (); HeroNode root = new HeroNode (1 , "宋江" ); HeroNode node2 = new HeroNode (2 , "吴用" ); HeroNode node3 = new HeroNode (3 , "卢俊义" ); HeroNode node4 = new HeroNode (4 , "林冲" ); HeroNode node5 = new HeroNode (5 , "关胜" ); binaryTree.setRoot(root); root.setLeft(node2); root.setRight(node3); node3.setRight(node4); node3.setLeft(node5); System.out.println("前序遍历:" ); binaryTree.preOrder(); System.out.println("中序遍历:" ); binaryTree.infixOrder(); System.out.println("后序遍历:" ); binaryTree.postOrder(); System.out.println("前序遍历查找:" ); HeroNode resNode = binaryTree.preOrderSearch(5 ); if (resNode != null ) { System.out.printf("no=%d name=%s \n" , resNode.getNo(), resNode.getName()); } else { System.out.println("没有找到~" ); } System.out.println("中序遍历查找:" ); resNode = binaryTree.infixOrderSearch(5 ); if (resNode != null ) { System.out.printf("no=%d name=%s \n" , resNode.getNo(), resNode.getName()); } else { System.out.println("没有找到~" ); } System.out.println("后序遍历查找:" ); resNode = binaryTree.postOrderSearch(5 ); if (resNode != null ) { System.out.printf("no=%d name=%s \n" , resNode.getNo(), resNode.getName()); } else { System.out.println("没有找到~" ); } } } class BinaryTree { private HeroNode root; public void setRoot (HeroNode root) { this .root = root; } public void preOrder () { if (this .root != null ) { this .root.preOrder(); } else { System.out.println("二叉树为空,无法遍历" ); } } public void infixOrder () { if (this .root != null ) { this .root.infixOrder(); } else { System.out.println("二叉树为空,无法遍历" ); } } public void postOrder () { if (this .root != null ) { this .root.postOrder(); } else { System.out.println("二叉树为空,无法遍历" ); } } public HeroNode preOrderSearch (int no) { if (root != null ) { return root.preOrderSearch(no); } else { return null ; } } public HeroNode infixOrderSearch (int no) { if (root != null ) { return root.infixOrderSearch(no); } else { return null ; } } public HeroNode postOrderSearch (int no) { if (root != null ) { return root.postOrderSearch(no); } else { return null ; } } } class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode (int no, String name) { super (); this .no = no; this .name = name; } public int getNo () { return no; } public void setNo (int no) { this .no = no; } public String getName () { return name; } public void setName (String name) { this .name = name; } public HeroNode getLeft () { return left; } public void setLeft (HeroNode left) { this .left = left; } public HeroNode getRight () { return right; } public void setRight (HeroNode right) { this .right = right; } @Override public String toString () { return "HeroNode [no=" + no + ", name=" + name + "]" ; } public void preOrder () { System.out.println(this ); if (this .left != null ) { this .left.preOrder(); } if (this .right != null ) { this .right.preOrder(); } } public void infixOrder () { if (this .left != null ) { this .left.infixOrder(); } System.out.println(this ); if (this .right != null ) { this .right.infixOrder(); } } public void postOrder () { if (this .left != null ) { this .left.postOrder(); } if (this .right != null ) { this .right.postOrder(); } System.out.println(this ); } public HeroNode preOrderSearch (int no) { if (this .no == no) { return this ; } HeroNode resNode = null ; if (this .left != null ) { resNode = this .left.preOrderSearch(no); } if (resNode != null ) { return resNode; } if (this .right != null ) { resNode = this .right.preOrderSearch(no); } return resNode; } public HeroNode infixOrderSearch (int no) { HeroNode resNode = null ; if (this .left != null ) { resNode = this .left.infixOrderSearch(no); } if (resNode != null ) { return resNode; } if (this .no == no) { return this ; } if (this .right != null ) { resNode = this .right.infixOrderSearch(no); } return resNode; } public HeroNode postOrderSearch (int no) { HeroNode resNode = null ; if (this .left != null ) { resNode = this .left.postOrderSearch(no); } if (resNode != null ) { return resNode; } if (this .right != null ) { resNode = this .right.postOrderSearch(no); } if (resNode != null ) { return resNode; } if (this .no == no) { return this ; } return resNode; } }
二叉树-删除节点 规定
如果删除的节点是叶子节点,则删除节点
如果删除的是非叶子节点,则删除该子树
思路 首先考虑如果树是空树root,如果只有一个root节点则等价于将二叉树指空
因为我们的二叉树是单向的,所以我们是判断当前节点的子节点是否需要删除节点,而不能去判断当前这个节点是不是需要删除节点
如果当前节点的左子节点不为空,并且左子节点就是要删除的节点,就将this.left=null,并且返回(结束递归删除)
如果当前节点的右子节点不为空,并且右子节点就是要删除的节点,就将this.right=null,并且返回(结束递归删除)
如果第2、3步都没有删除节点,那么就需要向左子树进行递归删除
如果第4步也没有删除,则应该向右子树进行递归删除
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 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 public class BinaryTreeDemo { public static void main (String[] args) { BinaryTree binaryTree = new BinaryTree (); HeroNode root = new HeroNode (1 , "宋江" ); HeroNode node2 = new HeroNode (2 , "吴用" ); HeroNode node3 = new HeroNode (3 , "卢俊义" ); HeroNode node4 = new HeroNode (4 , "林冲" ); HeroNode node5 = new HeroNode (5 , "关胜" ); binaryTree.setRoot(root); root.setLeft(node2); root.setRight(node3); node3.setRight(node4); node3.setLeft(node5); System.out.println("前序遍历:" ); binaryTree.preOrder(); System.out.println("中序遍历:" ); binaryTree.infixOrder(); System.out.println("后序遍历:" ); binaryTree.postOrder(); System.out.println("前序遍历查找:" ); HeroNode resNode = binaryTree.preOrderSearch(5 ); if (resNode != null ) { System.out.printf("no=%d name=%s \n" , resNode.getNo(), resNode.getName()); } else { System.out.println("没有找到~" ); } System.out.println("中序遍历查找:" ); resNode = binaryTree.infixOrderSearch(5 ); if (resNode != null ) { System.out.printf("no=%d name=%s \n" , resNode.getNo(), resNode.getName()); } else { System.out.println("没有找到~" ); } System.out.println("后序遍历查找:" ); resNode = binaryTree.postOrderSearch(5 ); if (resNode != null ) { System.out.printf("no=%d name=%s \n" , resNode.getNo(), resNode.getName()); } else { System.out.println("没有找到~" ); } System.out.println("删除前,前序遍历" ); binaryTree.preOrder(); binaryTree.delNode(3 ); System.out.println("删除后,前序遍历" ); binaryTree.preOrder(); } } class BinaryTree { private HeroNode root; public void setRoot (HeroNode root) { this .root = root; } public void delNode (int no) { if (root != null ) { if (root.getNo() == no) { root = null ; } else { root.delNode(no); } } else { System.out.println("空树不能删除!" ); } } public void preOrder () { if (this .root != null ) { this .root.preOrder(); } else { System.out.println("二叉树为空,无法遍历" ); } } public void infixOrder () { if (this .root != null ) { this .root.infixOrder(); } else { System.out.println("二叉树为空,无法遍历" ); } } public void postOrder () { if (this .root != null ) { this .root.postOrder(); } else { System.out.println("二叉树为空,无法遍历" ); } } public HeroNode preOrderSearch (int no) { if (root != null ) { return root.preOrderSearch(no); } else { return null ; } } public HeroNode infixOrderSearch (int no) { if (root != null ) { return root.infixOrderSearch(no); } else { return null ; } } public HeroNode postOrderSearch (int no) { if (root != null ) { return root.postOrderSearch(no); } else { return null ; } } } class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode (int no, String name) { super (); this .no = no; this .name = name; } public int getNo () { return no; } public void setNo (int no) { this .no = no; } public String getName () { return name; } public void setName (String name) { this .name = name; } public HeroNode getLeft () { return left; } public void setLeft (HeroNode left) { this .left = left; } public HeroNode getRight () { return right; } public void setRight (HeroNode right) { this .right = right; } @Override public String toString () { return "HeroNode [no=" + no + ", name=" + name + "]" ; } public void delNode (int no) { if (this .left != null && this .left.no == no) { this .left = null ; return ; } if (this .right != null && this .right.no == no) { this .right = null ; return ; } if (this .left != null ) { this .left.delNode(no); } if (this .right != null ) { this .right.delNode(no); } } public void preOrder () { System.out.println(this ); if (this .left != null ) { this .left.preOrder(); } if (this .right != null ) { this .right.preOrder(); } } public void infixOrder () { if (this .left != null ) { this .left.infixOrder(); } System.out.println(this ); if (this .right != null ) { this .right.infixOrder(); } } public void postOrder () { if (this .left != null ) { this .left.postOrder(); } if (this .right != null ) { this .right.postOrder(); } System.out.println(this ); } public HeroNode preOrderSearch (int no) { if (this .no == no) { return this ; } HeroNode resNode = null ; if (this .left != null ) { resNode = this .left.preOrderSearch(no); } if (resNode != null ) { return resNode; } if (this .right != null ) { resNode = this .right.preOrderSearch(no); } return resNode; } public HeroNode infixOrderSearch (int no) { HeroNode resNode = null ; if (this .left != null ) { resNode = this .left.infixOrderSearch(no); } if (resNode != null ) { return resNode; } if (this .no == no) { return this ; } if (this .right != null ) { resNode = this .right.infixOrderSearch(no); } return resNode; } public HeroNode postOrderSearch (int no) { HeroNode resNode = null ; if (this .left != null ) { resNode = this .left.postOrderSearch(no); } if (resNode != null ) { return resNode; } if (this .right != null ) { resNode = this .right.postOrderSearch(no); } if (resNode != null ) { return resNode; } if (this .no == no) { return this ; } return resNode; } }
顺序存储二叉树
从数据存储来看,数组存储方式 和树 的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组,
看右面的示意图。** **
1)右图的二叉树的结点,要求以数组 的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6]
2)要求在遍历数组 arr时,仍然可以以前序遍历 ,中序遍历 和后序遍历 的 方式完成结点的遍历
1)顺序二叉树通常只考虑完全二叉树
2)第n个元素的左子节点为 2 * n + 1
3)第n个元素的右子节点为 2 * n + 2
4)第n个元素的父节点为 (n-1) / 2
5)n : 表示二叉树中的第几个元素(按0开始编号 如图所示)
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 public class ArrBinaryTreeDemo { public static void main (String[] args) { int [] arr = { 1 , 2 , 3 , 4 , 5 , 6 , 7 }; ArrBinaryTree arrBinaryTree = new ArrBinaryTree (arr); arrBinaryTree.postOrder(); } } class ArrBinaryTree { private int [] arr; public ArrBinaryTree (int [] arr) { this .arr = arr; } public void preOrder () { this .preOrder(0 ); } public void infixOrder () { this .infixOrder(0 ); } public void postOrder () { this .postOrder(0 ); } public void preOrder (int index) { if (arr == null || arr.length == 0 ) { System.out.println("数组为空,不能按照二叉树的前序遍历" ); } System.out.println(arr[index]); if ((index * 2 + 1 ) < arr.length) { preOrder(2 * index + 1 ); } if ((index * 2 + 1 ) < arr.length) { preOrder(2 * index + 2 ); } } public void infixOrder (int index) { if (arr == null || arr.length == 0 ) { System.out.println("数组为空,不能按照二叉树的前序遍历" ); } if ((index * 2 + 1 ) < arr.length) { preOrder(2 * index + 1 ); } System.out.println(arr[index]); if ((index * 2 + 1 ) < arr.length) { preOrder(2 * index + 2 ); } } public void postOrder (int index) { if (arr == null || arr.length == 0 ) { System.out.println("数组为空,不能按照二叉树的前序遍历" ); } if ((index * 2 + 1 ) < arr.length) { preOrder(2 * index + 1 ); } if ((index * 2 + 1 ) < arr.length) { preOrder(2 * index + 2 ); } System.out.println(arr[index]); } }
线索化二叉树 线索二叉树基本介绍
n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域,存放指向该 结 点 在某种遍历次序 下的前驱和后继结点的指针(这种附加的指针称为”线索”)
这种加上了线索的二叉链表称为线索链表 ,相应的二叉树称为线索二叉树 (Threaded BinaryTree )。根据线索性质的不同,线索二叉树可分为前序线索二叉树 、中序线索二叉树 和后序线索二叉树 三种
一个结点的前一个结点,称为前驱 结点
一个结点的后一个结点,称为后继 结点
说明: 当线索化二叉树后,Node节点的 属性 left 和 right ,有如下情况:
left 指向的是左子树,也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点.
right指向的是右子树,也可能是指向后继节点,比如 ① 节点right 指向的是右子树,而⑩ 节点的right 指向的是后继节点.
遍历线索化二叉树 说明 :对前面的中序线索化的二叉树, 进行遍历
分析 :因为线索化后,各个结点指向有变化,因此原来的遍历方式不能使用 ,这时需要使用新的方式遍历线索化二叉树 ,各个节点可以通过线型方式遍历,因此无需使用递归方式,这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致 。
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 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 public class ThreadedBinaryTredemo { public static void main (String[] args) { HeroNode root = new HeroNode (1 , "tom" ); HeroNode node2 = new HeroNode (3 , "jack" ); HeroNode node3 = new HeroNode (6 , "smith" ); HeroNode node4 = new HeroNode (8 , "mary" ); HeroNode node5 = new HeroNode (10 , "king" ); HeroNode node6 = new HeroNode (14 , "dim" ); root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree (); threadedBinaryTree.setRoot(root); threadedBinaryTree.threadedNodes(); HeroNode leftNode = node5.getLeft(); HeroNode rightNode = node5.getRight(); System.out.println("10号节点的前驱结点是" + leftNode); System.out.println("10号节点的前驱结点是" + rightNode); System.out.println("使用线索化的方式遍历线索化二叉树" ); threadedBinaryTree.threadedList(); } } class ThreadedBinaryTree { private HeroNode root; private HeroNode pre = null ; public void setRoot (HeroNode root) { this .root = root; } public void threadedNodes () { this .threadedNodes(root); } public void threadedList () { HeroNode node = root; while (node != null ) { while (node.getLeftType() == 0 ) { node = node.getLeft(); } System.out.println(node); while (node.getRightType() == 1 ) { node = node.getRight(); System.out.println(node); } node = node.getRight(); } } public void threadedNodes (HeroNode node) { if (node == null ) { return ; } threadedNodes(node.getLeft()); if (node.getLeft() == null ) { node.setLeft(pre); node.setLeftType(1 ); } if (pre != null && pre.getRight() == null ) { pre.setRight(node); pre.setRightType(1 ); } pre = node; threadedNodes(node.getRight()); } public void delNode (int no) { if (root != null ) { if (root.getNo() == no) { root = null ; } else { root.delNode(no); } } else { System.out.println("空树不能删除!" ); } } public void infixOrder () { if (this .root != null ) { this .root.infixOrder(); } else { System.out.println("二叉树为空,无法遍历" ); } } public HeroNode infixOrderSearch (int no) { if (root != null ) { return root.infixOrderSearch(no); } else { return null ; } } } class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; private int leftType; private int rightType; public int getLeftType () { return leftType; } public void setLeftType (int leftType) { this .leftType = leftType; } public int getRightType () { return rightType; } public void setRightType (int rightType) { this .rightType = rightType; } public HeroNode (int no, String name) { super (); this .no = no; this .name = name; } public int getNo () { return no; } public void setNo (int no) { this .no = no; } public String getName () { return name; } public void setName (String name) { this .name = name; } public HeroNode getLeft () { return left; } public void setLeft (HeroNode left) { this .left = left; } public HeroNode getRight () { return right; } public void setRight (HeroNode right) { this .right = right; } @Override public String toString () { return "HeroNode [no=" + no + ", name=" + name + "]" ; } public void delNode (int no) { if (this .left != null && this .left.no == no) { this .left = null ; return ; } if (this .right != null && this .right.no == no) { this .right = null ; return ; } if (this .left != null ) { this .left.delNode(no); } if (this .right != null ) { this .right.delNode(no); } } public void infixOrder () { if (this .left != null ) { this .left.infixOrder(); } System.out.println(this ); if (this .right != null ) { this .right.infixOrder(); } } public HeroNode infixOrderSearch (int no) { HeroNode resNode = null ; if (this .left != null ) { resNode = this .left.infixOrderSearch(no); } if (resNode != null ) { return resNode; } if (this .no == no) { return this ; } if (this .right != null ) { resNode = this .right.infixOrderSearch(no); } return resNode; } }
堆排序
堆排序是利用堆 这种数据结构而设计的一种排序算法,堆排序是一种选择排序, 它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。
堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
大顶堆举例说明
大顶堆特点:arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] // i 对应第几个节点,i从0开始编号
小顶堆举例说明
小顶堆:arr[i] <=arr[2*i+1] && arr[i] <= arr[2*i+2] // i 对应第几个节点,i从0开始编号
一般升序采用大顶堆 ,降序采用小顶堆
堆排序的基本思想 堆排序的基本思想是:
将待排序序列构造成一个大顶堆
此时,整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换,此时末尾就为最大值。
然后将剩余n-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 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 import java.util.Arrays;public class HeapSort { public static void main (String[] args) { int [] arr = new int [8000000 ]; for (int i = 0 ; i < arr.length; i++) { arr[i] = (int ) (Math.random() * 80000000 ); } long startTime = System.currentTimeMillis(); heapSort(arr); long endTime = System.currentTimeMillis(); System.out.println("运行时间:" + (endTime - startTime)); } public static void heapSort (int arr[]) { int temp = 0 ; System.out.println("堆排序!" ); for (int i = arr.length / 2 - 1 ; i >= 0 ; i--) { adjustHeap(arr, i, arr.length); } for (int j = arr.length - 1 ; j > 0 ; j--) { temp = arr[j]; arr[j] = arr[0 ]; arr[0 ] = temp; adjustHeap(arr, 0 , j); } } public static void adjustHeap (int [] arr, int i, int length) { int temp = arr[i]; for (int k = i * 2 + 1 ; k < length; k = k * 2 + 1 ) { if (k + 1 < length && arr[k] < arr[k + 1 ]) { k++; } if (arr[k] > temp) { arr[i] = arr[k]; i = k; } else { break ; } } arr[i] = temp; } }
赫夫曼树 基本介绍
给定n个权值作为n个叶子结点 ,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树 ,也称为哈夫曼树 (Huffman Tree), 还有的书翻译为霍夫曼树 。
赫夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
赫夫曼树几个重要概念和举例说明
路径和路径长度:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1
结点的权及带权路径长度: 若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度 为:从根结点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度: 树的带权路径长度规定为所有叶子结点 的带权路径长度之和,记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
WPL最小的就是赫夫曼树
构成赫夫曼树的步骤
从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树
取出根节点权值最小的两颗二叉树
组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理,就得到一颗赫夫曼树
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 import java.util.ArrayList;import java.util.Collection;import java.util.Collections;import java.util.List;public class HuffmanTree { public static void main (String[] args) { int [] arr = {13 , 7 , 8 , 3 , 29 , 6 , 1 }; Node root=createHuffmanTree(arr); root.preOrder(); } public static void preOrder (Node root) { if (root!=null ){ root.preOrder(); }else { System.out.println("空树,不能遍历~" ); } } public static Node createHuffmanTree (int [] arr) { List<Node> nodes = new ArrayList <Node>(); for (int value : arr) { nodes.add(new Node (value)); } while (nodes.size() > 1 ) { Collections.sort(nodes); Node leftNode = nodes.get(0 ); Node rightNode = nodes.get(1 ); Node parent = new Node (leftNode.value + rightNode.value); parent.left = leftNode; parent.right = rightNode; nodes.remove(leftNode); nodes.remove(rightNode); nodes.add(parent); } return nodes.get(0 ); } } class Node implements Comparable <Node> { int value; Node left; Node right; public void preOrder () { System.out.println(this ); if (this .left!=null ){ this .left.preOrder(); } if (this .right!=null ){ this .right.preOrder(); } } public Node (int value) { this .value = value; } @Override public String toString () { return "Node{" + "value=" + value + '}' ; } @Override public int compareTo (Node o) { return this .value - o.value; } }
赫夫曼编码 基本介绍
赫夫曼编码也翻译为 哈夫曼 编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法
赫夫曼编码是赫夫曼树在电讯通信中的经典的应用之一。
赫夫曼编码广泛地用于数据文件压缩。其**压缩率通常在20%~90%**之间
赫夫曼码是可变字长 编码(VLC)的一种。Huffman于1952年提出一种编码方法,称之为最佳编码
原理剖析 Ø通信领域中信息的处理方式1-定长编码
i like like like java do you like a java // 共40个字符(包括空格)
105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 //对应Ascii码
↓↓↓
01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //对应的二进制
按照二进制来传递信息,总的长度是 359 (包括空格)
在线转码 工具 :https://www.mokuge.com/tool/asciito16 /
Ø通信领域中信息的处理方式2-变长编码
i like like like java do you like a java // 共40个字符(包括空格)
d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d 说明:按照各个字符出现的次数进行编码,原则是出现次数越多的,则编码越小,比如 空格出现了9 次, 编码为0 ,其它依次类推.
按照上面给各个字符规定的编码,则我们在传输 “i like like like java do you like a java” 数据时,编码就是 10010110100…
字符的编码都不能是其他字符编码的前缀,符合此要求的编码叫做前缀编码, 即不能匹配到重复的编码
Ø通信领域中信息的处理方式3-赫夫曼编码
i like like like java do you like a java // 共40个字符(包括空格)
d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值.(图后)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 //根据赫夫曼树,给各个字符 //规定编码 , 向左的路径为0 //向右的路径为1 , 编码如下: o: 1000 u: 10010 d: 100110 y: 100111 i: 101 a : 110 k: 1110 e: 1111 j: 0000 v: 0001 l: 001 : 01 按照上面的赫夫曼编码,我们的"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩) 1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 长度为 : 133 说明: 1. 原来长度是 359 , 压缩了 (359-133) / 359 = 62.9% 2. 此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性
注意, 这个赫夫曼树根据排序方法不同,也可能不太一样,这样对应的赫夫曼编码也不完全一样,但是wpl 是一样的,都是最小的, 比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个,则生成的二叉树为:
最佳实践-数据压缩(创建赫夫曼树)
将给出的一段文本,比如 “i like like like java do you like a java” , 根据前面的讲的赫夫曼编码原理,对其进行数据压缩处理 ,形式如 “1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110”
步骤:根据赫夫曼编码压缩数据的原理,需要创建 “i like like like java do you like a java” 对应的赫夫曼树.
最佳实践-数据压缩(生成赫夫曼编码和赫夫曼编码后的数据)
我们已经生成了 赫夫曼树, 下面我们继续完成任务
1)生成赫夫曼树对应的赫夫曼编码 , 如下表: =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
2)使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码,将”i like like like java do you like a java” 字符串生成对应的编码数据, 形式如下. 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
最佳实践-数据解压(使用赫夫曼编码解码)
使用赫夫曼编码来解码数据,具体要求是
1)前面我们得到了赫夫曼编码和对应的编码 byte[] , 即:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
2)现在要求使用赫夫曼编码, 进行解码,又重新得到原来的字符串”i like like like java do you like a java”
赫夫曼编码压缩文件注意事项
1)如果文件本身就是经过压缩处理的,那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件 [举例压一个 .ppt]
2)赫夫曼编码是按字节来处理的,因此可以处理所有的文件(二进制文件、文本文件) [举例压一个.xml文件]
3)如果一个文件中的内容,重复的数据不多,压缩效果也不会很明显.
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 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.InputStream;import java.io.ObjectInputStream;import java.io.ObjectOutputStream;import java.io.OutputStream;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.HashMap;import java.util.List;import java.util.Map;public class HuffmanCode { public static void main (String[] args) { String zipFile = "d://Uninstall.zip" ; String dstFile = "d://Uninstall2.xml" ; unZipFile(zipFile, dstFile); System.out.println("解压成功!" ); } public static void unZipFile (String zipFile, String dstFile) { InputStream is = null ; ObjectInputStream ois = null ; OutputStream os = null ; try { is = new FileInputStream (zipFile); ois = new ObjectInputStream (is); byte [] huffmanBytes = (byte []) ois.readObject(); Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject(); byte [] bytes = decode(huffmanCodes, huffmanBytes); os = new FileOutputStream (dstFile); os.write(bytes); } catch (Exception e) { System.out.println(e.getMessage()); } finally { try { os.close(); ois.close(); is.close(); } catch (Exception e2) { System.out.println(e2.getMessage()); } } } public static void zipFile (String srcFile, String dstFile) { OutputStream os = null ; ObjectOutputStream oos = null ; FileInputStream is = null ; try { is = new FileInputStream (srcFile); byte [] b = new byte [is.available()]; is.read(b); byte [] huffmanBytes = huffmanZip(b); os = new FileOutputStream (dstFile); oos = new ObjectOutputStream (os); oos.writeObject(huffmanBytes); oos.writeObject(huffmanCodes); } catch (Exception e) { System.out.println(e.getMessage()); } finally { try { is.close(); oos.close(); os.close(); } catch (Exception e) { System.out.println(e.getMessage()); } } } private static byte [] decode(Map<Byte, String> huffmanCodes, byte [] huffmanBytes) { StringBuilder stringBuilder = new StringBuilder (); for (int i = 0 ; i < huffmanBytes.length; i++) { byte b = huffmanBytes[i]; boolean flag = (i == huffmanBytes.length - 1 ); stringBuilder.append(byteToBitString(!flag, b)); } Map<String, Byte> map = new HashMap <String, Byte>(); for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) { map.put(entry.getValue(), entry.getKey()); } List<Byte> list = new ArrayList <>(); for (int i = 0 ; i < stringBuilder.length(); ) { int count = 1 ; boolean flag = true ; Byte b = null ; while (flag) { String key = stringBuilder.substring(i, i + count); b = map.get(key); if (b == null ) { count++; } else { flag = false ; } } list.add(b); i += count; } byte b[] = new byte [list.size()]; for (int i = 0 ; i < b.length; i++) { b[i] = list.get(i); } return b; } private static String byteToBitString (boolean flag, byte b) { int temp = b; if (flag) { temp |= 256 ; } String str = Integer.toBinaryString(temp); if (flag) { return str.substring(str.length() - 8 ); } else { return str; } } private static byte [] huffmanZip(byte [] bytes) { List<Node> nodes = getNodes(bytes); Node huffmanTreeRoot = createHuffmanTree(nodes); Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot); byte [] huffmanCodeBytes = zip(bytes, huffmanCodes); return huffmanCodeBytes; } private static byte [] zip(byte [] bytes, Map<Byte, String> huffmanCodes) { StringBuilder stringBuilder = new StringBuilder (); for (byte b : bytes) { stringBuilder.append(huffmanCodes.get(b)); } int len; if (stringBuilder.length() % 8 == 0 ) { len = stringBuilder.length() / 8 ; } else { len = stringBuilder.length() / 8 + 1 ; } byte [] huffmanCodeBytes = new byte [len]; int index = 0 ; for (int i = 0 ; i < stringBuilder.length(); i += 8 ) { String strByte; if (i + 8 > stringBuilder.length()) { strByte = stringBuilder.substring(i); } else { strByte = stringBuilder.substring(i, i + 8 ); } huffmanCodeBytes[index] = (byte ) Integer.parseInt(strByte, 2 ); index++; } return huffmanCodeBytes; } static Map<Byte, String> huffmanCodes = new HashMap <Byte, String>(); static StringBuilder stringBuilder = new StringBuilder (); private static Map<Byte, String> getCodes (Node root) { if (root == null ) { return null ; } getCodes(root.left, "0" , stringBuilder); getCodes(root.right, "1" , stringBuilder); return huffmanCodes; } private static void getCodes (Node node, String code, StringBuilder stringBuilder) { StringBuilder stringBuilder2 = new StringBuilder (stringBuilder); stringBuilder2.append(code); if (node != null ) { if (node.data == null ) { getCodes(node.left, "0" , stringBuilder2); getCodes(node.right, "1" , stringBuilder2); } else { huffmanCodes.put(node.data, stringBuilder2.toString()); } } } private static void preOrder (Node root) { if (root != null ) { root.preOrder(); } else { System.out.println("赫夫曼树为空" ); } } private static List<Node> getNodes (byte [] bytes) { ArrayList<Node> nodes = new ArrayList <Node>(); Map<Byte, Integer> counts = new HashMap <>(); for (byte b : bytes) { Integer count = counts.get(b); if (count == null ) { counts.put(b, 1 ); } else { counts.put(b, count + 1 ); } } for (Map.Entry<Byte, Integer> entry : counts.entrySet()) { nodes.add(new Node (entry.getKey(), entry.getValue())); } return nodes; } private static Node createHuffmanTree (List<Node> nodes) { while (nodes.size() > 1 ) { Collections.sort(nodes); Node leftNode = nodes.get(0 ); Node rightNode = nodes.get(1 ); Node parent = new Node (null , leftNode.weight + rightNode.weight); parent.left = leftNode; parent.right = rightNode; nodes.remove(leftNode); nodes.remove(rightNode); nodes.add(parent); } return nodes.get(0 ); } } class Node implements Comparable <Node> { Byte data; int weight; Node left; Node right; public Node (Byte data, int weight) { this .data = data; this .weight = weight; } @Override public int compareTo (Node o) { return this .weight - o.weight; } public String toString () { return "Node [data = " + data + " weight=" + weight + "]" ; } public void preOrder () { System.out.println(this ); if (this .left != null ) { this .left.preOrder(); } if (this .right != null ) { this .right.preOrder(); } } }
二叉排序树(BST树) 先看一个需求
给你一个数列 (7, 3, 10, 12, 5, 1, 9),要求能够高效的完成对数据的查询和添加。
解决方案分析
Ø使用数组
数组未排序, 优点:直接在数组尾添加,速度快。 缺点:查找速度慢.
数组排序,优点:可以使用二分查找,查找速度快,缺点:为了保证数组有序,在添加新数据时,找到插入位置后,后面的数据需整体移动,速度慢。
Ø使用链式存储-链表 不管链表是否有序,查找速度都慢,添加数据速度比数组快,不需要数据整体移动。
Ø使用二叉排序树
基本介绍 二叉排序树:BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。
特别说明 :如果有相同的值,可以将该节点放在左子节点或右子节点
比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ,对应的二叉排序树为:
* *
↓↓插入2↓↓
* *
删除节点 二叉排序树的删除情况比较复杂,有下面三种情况需要考虑:
1)删除叶子节点 (比如:2, 5, 9, 12)
2)删除只有一颗子树的节点 (比如:1)
3)删除有两颗子树的节点. (比如:7, 3,10 )
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 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 第一种情况: 删除叶子节点 (比如:2 , 5 , 9 , 12 ) 思路 (1 ) 需求先去找到要删除的结点 targetNode (2 ) 找到targetNode 的 父结点 parent (3 ) 确定 targetNode 是 parent的左子结点 还是右子结点 (4 ) 根据前面的情况来对应删除 左子结点 parent.left = null 右子结点 parent.right = null ; 第二种情况: 删除只有一颗子树的节点 比如 1 思路 (1 ) 需求先去找到要删除的结点 targetNode (2 ) 找到targetNode 的 父结点 parent (3 ) 确定targetNode 的子结点是左子结点还是右子结点 (4 ) targetNode 是 parent 的左子结点还是右子结点 (5 ) 如果targetNode 有左子结点 5. 1 如果 targetNode 是 parent 的左子结点parent.left = targetNode.left; 5.2 如果 targetNode 是 parent 的右子结点parent.right = targetNode.left; (6 ) 如果targetNode 有右子结点 6.1 如果 targetNode 是 parent 的左子结点parent.left = targetNode.right; 6.2 如果 targetNode 是 parent 的右子结点parent.right = targetNode.right 情况三 : 删除有两颗子树的节点. (比如:7 , 3 ,10 ) 思路 (1 ) 需求先去找到要删除的结点 targetNode (2 ) 找到targetNode 的 父结点 parent (3 ) 从targetNode 的右子树找到最小的结点 (4 ) 用一个临时变量,将 最小结点的值保存 temp = 11 (5 ) 删除该最小结点 (6 ) targetNode.value = temp public class BinarySortTreeDemo { public static void main (String[] args) { int [] arr = {7 , 3 }; BinarySortTree binarySortTree = new BinarySortTree (); for (int i = 0 ; i < arr.length; i++) { binarySortTree.add(new Node (arr[i])); } binarySortTree.delNode(7 ); binarySortTree.infixOrder(); } } class BinarySortTree { private Node root; public Node search (int value) { if (root == null ) { return null ; } else { return root.search(value); } } public Node searchParent (int value) { if (root == null ) { return null ; } else { return root.searchParent(value); } } public int delRightTreeMin (Node node) { Node target = node; while (target.left != null ) { target = target.left; } delNode(target.value); return target.value; } public void delNode (int value) { if (root == null ) { return ; } else { Node targetNode = search(value); if (targetNode == null ) { return ; } if (root.left == null && root.right == null ) { root = null ; return ; } Node parent = searchParent(value); if (targetNode.left == null && targetNode.right == null ) { if (parent.left != null && parent.left.value == value) { parent.left = null ; } else if (parent.right != null && parent.right.value == value) { parent.right = null ; } } else if (targetNode.left != null && targetNode.right != null ) { int minVal = delRightTreeMin(targetNode.right); targetNode.value = minVal; } else { if (targetNode.left != null ) { if (parent != null ) { if (parent.left.value == value) { parent.left = targetNode.left; } else { parent.right = targetNode.left; } } else { root = targetNode.left; } } else { if (parent != null ) { if (parent.left.value == value) { parent.left = targetNode.right; } else { parent.right = targetNode.right; } } else { root = targetNode.right; } } } } } public void add (Node node) { if (root == null ) { root = node; } else { root.add(node); } } public void infixOrder () { if (root != null ) { root.infixOrder(); } else { System.out.println("二叉排序树为空,不能遍历~" ); } } } class Node { int value; Node left; Node right; public Node (int value) { this .value = value; } public Node search (int value) { if (value == this .value) { return this ; } else if (value < this .value) { if (this .left == null ) { return null ; } return this .left.search(value); } else { if (this .right == null ) { return null ; } return this .right.search(value); } } public Node searchParent (int value) { if ((this .left != null && this .left.value == value) || (this .right != null && this .right.value == value)) { return this ; } else { if (value < this .value && this .left != null ) { return this .left.searchParent(value); } else if (value >= this .value && this .right != null ) { return this .right.searchParent(value); } else { return null ; } } } @Override public String toString () { return "Node{" + "value=" + value + '}' ; } public void add (Node node) { if (node == null ) { return ; } if (node.value < this .value) { if (this .left == null ) { this .left = node; } else { this .left.add(node); } } else { if (this .right == null ) { this .right = node; } else { this .right.add(node); } } } public void infixOrder () { if (this .left != null ) { this .left.infixOrder(); } System.out.println(this ); if (this .right != null ) { this .right.infixOrder(); } } }
平衡二叉树(AVL树) *** *左边BST存在的问题分析 :
左子树全部为空,从形式上看,更像一个单链表.
插入速度没有影响
查询速度明显降低(因为需要依次比较), 不能发挥BST 的优势,因为每次还需要比较左子树,其查询速度比 单链表还慢
解决方案-平衡二叉树(AVL)
基本介绍
平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树, 可以保证查询效率较高 。
具有以下特点 :它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树 、AVL 、替罪羊树 、Treap 、伸展树 等。
举例说明, 看看下面哪些AVL树, 为什么?
左旋转
创建一个新的节点newNode,值等于当前根节点的值
把新节点的左子树设置了当前节点的左子树newNode.left=left
把新节点的右子树设置成当前节点的右子树的左子树newNode.right=right.left
把当前节点的值换成右子节点的值value=right.value
把当前节点的右子树设置成右子树的右子树right=right.right
把当前节点的左子树设置成新节点left=newNode
右旋转
创建一个新的节点newNode,值等于当前根节点的值
把新节点的右子树设置了当前节点的右子树newNode.right=right
把新节点的左子树设置成当前节点的左子树的右子树newNode.left=left.right
把当前节点的值换成左子节点的值value=left.value
把当前节点的左子树设置成左子树的左子树left=left.left
把当前节点的右子树设置成新节点right=newNode
问题分析
当符合右旋转的条件时
如果它的左子树的右子树高度大于它的左子树的左子树的高度
先对当前这个结点的左节点进行左旋转
在对当前结点进行右旋转的操作即可
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 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 public class AVLTreeDemo { public static void main (String[] args) { int [] arr = {10 , 11 , 7 , 6 , 8 , 9 }; AVLTree avlTree = new AVLTree (); for (int i = 0 ; i < arr.length; i++) { avlTree.add(new Node (arr[i])); } avlTree.infixOrder(); System.out.println("平衡处理后" ); System.out.println("树的高度" + avlTree.getRoot().height()); System.out.println("树的左子树高度" + avlTree.getRoot().leftHeight()); System.out.println("树的右子树高度" + avlTree.getRoot().rightHeight()); } } class AVLTree { private Node root; public Node getRoot () { return root; } public Node search (int value) { if (root == null ) { return null ; } else { return root.search(value); } } public Node searchParent (int value) { if (root == null ) { return null ; } else { return root.searchParent(value); } } public int delRightTreeMin (Node node) { Node target = node; while (target.left != null ) { target = target.left; } delNode(target.value); return target.value; } public void delNode (int value) { if (root == null ) { return ; } else { Node targetNode = search(value); if (targetNode == null ) { return ; } if (root.left == null && root.right == null ) { root = null ; return ; } Node parent = searchParent(value); if (targetNode.left == null && targetNode.right == null ) { if (parent.left != null && parent.left.value == value) { parent.left = null ; } else if (parent.right != null && parent.right.value == value) { parent.right = null ; } } else if (targetNode.left != null && targetNode.right != null ) { int minVal = delRightTreeMin(targetNode.right); targetNode.value = minVal; } else { if (targetNode.left != null ) { if (parent != null ) { if (parent.left.value == value) { parent.left = targetNode.left; } else { parent.right = targetNode.left; } } else { root = targetNode.left; } } else { if (parent != null ) { if (parent.left.value == value) { parent.left = targetNode.right; } else { parent.right = targetNode.right; } } else { root = targetNode.right; } } } } } public void add (Node node) { if (root == null ) { root = node; } else { root.add(node); } } public void infixOrder () { if (root != null ) { root.infixOrder(); } else { System.out.println("二叉排序树为空,不能遍历~" ); } } } class Node { int value; Node left; Node right; public Node (int value) { this .value = value; } public int leftHeight () { if (left == null ) { return 0 ; } return left.height(); } public int rightHeight () { if (right == null ) { return 0 ; } return right.height(); } public int height () { return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1 ; } private void leftRotate () { Node newNode = new Node (value); newNode.left = left; newNode.right = right.left; value = right.value; right = right.right; left = newNode; } private void rightRotate () { Node newNode = new Node (value); newNode.right = right; newNode.left = left.right; value = left.value; left = left.left; right = newNode; } public Node search (int value) { if (value == this .value) { return this ; } else if (value < this .value) { if (this .left == null ) { return null ; } return this .left.search(value); } else { if (this .right == null ) { return null ; } return this .right.search(value); } } public Node searchParent (int value) { if ((this .left != null && this .left.value == value) || (this .right != null && this .right.value == value)) { return this ; } else { if (value < this .value && this .left != null ) { return this .left.searchParent(value); } else if (value >= this .value && this .right != null ) { return this .right.searchParent(value); } else { return null ; } } } @Override public String toString () { return "Node{" + "value=" + value + '}' ; } public void add (Node node) { if (node == null ) { return ; } if (node.value < this .value) { if (this .left == null ) { this .left = node; } else { this .left.add(node); } } else { if (this .right == null ) { this .right = node; } else { this .right.add(node); } } if (rightHeight() - leftHeight() > 1 ) { if (right != null && right.rightHeight() < right.leftHeight()) { right.rightRotate(); leftRotate(); } else { leftRotate(); } return ; } if (leftHeight() - rightHeight() > 1 ) { if (left != null && left.rightHeight() > left.leftHeight()) { left.leftRotate(); rightRotate(); } else { rightRotate(); } return ; } } public void infixOrder () { if (this .left != null ) { this .left.infixOrder(); } System.out.println(this ); if (this .right != null ) { this .right.infixOrder(); } } }
二叉树与B树 二叉树的问题分析
1)二叉树需要加载到内存的,如果二叉树的节点少,没有什么问题,但是如果二叉树的节点很多(比如1亿), 就存在如下问题:
2)问题1:在构建二叉树时,需要多次进行i/o操作(海量数据存在数据库或文件中),节点海量,构建二叉树时,速度有影响
3)问题2:节点海量,也会造成二叉树的高度很大,会降低操作速度.
多叉树 1.在二叉树中,每个节点有数据项,最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点 ,就是多叉树(multiway tree)
2. 后面我们讲解的2-3树,2-3-4树就是多叉树,多叉树通过重新组织节点,减少树的高度,能对二叉树进行优化。
3. 举例说明(下面2-3树就是一颗多叉树)
B树的基本介绍 B树通过重新组织节点,降低树的高度,并且减少i/o读写次数来提升效率。
1)如图B树通过重新组织节点, 降低了树的高度.
2)*文件系统及数据库系统的设计者利用了磁盘预读原理,将一个节点的大小设为等于一个页(**页得大小通常为4k),**这样每个节点只需要一次I/O就可以完全载入 *
3)将树的度M设置为1024,在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素, B树(B+)广泛应用于文件存储系统以及数据库系统中
2-3树 2-3树特点 2-3树是最简单的B树结构, 具有如下特点:
1)2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件)
2)有两个子节点的节点叫二节点,二节点要么没有子节点,要么有两个子节点.
3)有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点.
4)2-3树是由二节点和三节点构成的树。
2-3树应用案例 将数列{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 构建成2-3树,并保证数据插入的 大小顺序。(演示一下构建2-3树的过程.)
1 2 3 4 5 6 7 插入规则: 1 、2 -3 树的所有叶子节点都在同一层.(只要是B树都满足这个条件)2 、有两个子节点的节点叫二节点,二节点要么没有子节点,要么有两个子节点.3 、有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点4 、当按照规则插入一个数到某个节点时,不能满足上面三个要求,就需要拆,先向上拆,如果上层满,则拆本层,拆后仍然需要满足上面3 个条件。 5 、对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则
其它说明 除了23树,还有234树等,概念和23树类似,也是一种B树。 如图:
B树、B+树和B*树 B树的介绍 B-tree 树即B树 ,B即Balanced,平衡的意思。有人把B-tree翻译成B-树,容易让人产生误解。会以为B-树是一种树,而B树又是另一种树。实际上,B-tree就是指的B树。
前面已经介绍了2-3树和2-3-4树,他们就是B树(英语:B-tree 也写成B-树),这里我们再做一个说明,我们在学习Mysql时,经常听到说某种类型的索引是基于B树或者B+树的,如图:
1 2 3 4 5 6 7 B树的说明: 1 、B树的阶:节点的最多子节点个数。比如2 -3 树的阶是3 ,2 -3 -4 树的阶是4 2 、B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点3 、关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据.4 、搜索有可能在非叶子结点结束5 、其搜索性能等价于在关键字全集内做一次二分查找
B+树的介绍 B+树是B树的变体,也是一种多路搜索树。
1 2 3 4 5 6 7 B+树的说明: 1 、B+树的搜索与B树也基本相同,区别是B+树只有达到叶子结点才命中(B树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找2 、所有关键字都出现在叶子结点的链表中(即数据只能在叶子节点【也叫稠密索引】),且链表中的关键字(数据)恰好是有序的。3 、不可能在非叶子结点命中4 、非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层5 、更适合文件索引系统6 、B树和B+树各有自己的应用场景,不能说B+树完全比B树好,反之亦然.
B *树的介绍 B*树是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针。
1 2 3 4 B*树的说明: 1 、B*树定义了非叶子结点关键字个数至少为(2 /3 )*M,即块的最低使用率为2 /3 ,而B+树的块的最低使用率为1 /2 。2 、从第1 个特点我们可以看出,B*树分配新结点的概率比B+树要低,空间使用率更高