A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set.[1] Some authors allow the binary tree to be the empty set as well.
前言 二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树 二叉树介绍:
二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点。然而,没有足够的信息来区分左结点和右结点。如果不考虑连通性,允许图中有多个连通分量,这样的结构叫做森林。常见的树有一般二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B树。
二叉树特点:
由二叉树定义以及图示分析得出二叉树有以下特点: 1)每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点。 2)左子树和右子树是有顺序的,次序不能任意颠倒。 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 public class BinaryTreeDemo { public static void main (String[] args) { HeroNode root = new HeroNode(1 , "宋江" ); BinaryTree binaryTree = new BinaryTree(root); HeroNode node2 = new HeroNode(2 , "吴用" ); HeroNode node3 = new HeroNode(3 , "卢俊" ); HeroNode node4 = new HeroNode(4 , "林冲" ); HeroNode node5 = new HeroNode(5 , "关胜" ); root.setLeftHeroNode(node2); root.setRightHeroNode(node3); node3.setRightHeroNode(node4); node3.setLeftHeroNode(node5); binaryTree.preOrder(root); System.out.println("==========删除节点后==========" ); binaryTree.deleteHeroNode(3 ); binaryTree.preOrder(root); } } class BinaryTree { private HeroNode root; public BinaryTree (HeroNode root) { this .root = root; } public void preOrder (HeroNode root) { if (root == null ) { System.out.println("该树为空树" ); } else { root.preOrder(); } } public void midOrder (HeroNode root) { if (root == null ) { System.out.println("该树为空树" ); } else { root.midOrder(); } } public void posOrder (HeroNode root) { if (root == null ) { System.out.println("该树为空树" ); } else { root.posOrder(); } } public HeroNode preOrderSearch (int no) { if (root == null ) { System.out.println("该树为空树" ); } else { return root.preOrderSearch(no); } return null ; } public HeroNode midOrderSearch (int no) { if (root == null ) { System.out.println("该树为空树" ); } else { return root.midOrderSearch(no); } return null ; } public HeroNode posOrderSearch (int no) { if (root == null ) { System.out.println("该树为空树" ); } else { return root.posOrderSearch(no); } return null ; } public void deleteHeroNode (int no) { if (root != null ) { if (root.getNo() == no) { root = null ; } else { root.deleteHeroNode(no); } } else { System.out.println("空树无法删除" ); } } } class HeroNode { private int no; private String name; private HeroNode leftHeroNode; private HeroNode rightHeroNode; public HeroNode (int no, String name) { this .no = no; this .name = name; } public void preOrder () { System.out.println(this ); if (this .getLeftHeroNode() != null ) { this .getLeftHeroNode().preOrder(); } if (this .getRightHeroNode() != null ) { this .getRightHeroNode().preOrder(); } } public void midOrder () { if (this .getLeftHeroNode() != null ) { this .getLeftHeroNode().midOrder(); } System.out.println(this ); if (this .getRightHeroNode() != null ) { this .getRightHeroNode().midOrder(); } } public void posOrder () { if (this .getLeftHeroNode() != null ) { this .getLeftHeroNode().posOrder(); } if (this .getRightHeroNode() != null ) { this .getRightHeroNode().posOrder(); } System.out.println(this ); } public HeroNode preOrderSearch (int no) { HeroNode resHero = null ; if (this .getNo() == no) { return this ; } if (this .getLeftHeroNode() != null ) { resHero = this .getLeftHeroNode().preOrderSearch(no); } if (resHero != null ) { return resHero; } if (this .getRightHeroNode() != null ) { resHero = this .getRightHeroNode().preOrderSearch(no); } return resHero; } public HeroNode midOrderSearch (int no) { HeroNode resHero = null ; if (this .getLeftHeroNode() != null ) { resHero = this .getLeftHeroNode().midOrderSearch(no); } if (resHero != null ) { return resHero; } if (this .getNo() == no) { return this ; } if (this .getRightHeroNode() != null ) { resHero = this .getRightHeroNode().midOrderSearch(no); } return resHero; } public HeroNode posOrderSearch (int no) { HeroNode resHero = null ; if (this .getLeftHeroNode() != null ) { resHero = this .getLeftHeroNode().posOrderSearch(no); } if (resHero != null ) { return resHero; } if (this .getRightHeroNode() != null ) { resHero = this .getRightHeroNode().posOrderSearch(no); } if (resHero != null ) { return resHero; } if (this .getNo() == no) { return this ; } return resHero; } public void deleteHeroNode (int no) { if (this .getLeftHeroNode() != null && this .getLeftHeroNode().getNo() == no) { this .setLeftHeroNode(null ); return ; } if (this .getRightHeroNode() != null && this .getRightHeroNode().getNo() == no) { this .setRightHeroNode(null ); return ; } if (this .getLeftHeroNode() != null ) { this .getLeftHeroNode().deleteHeroNode(no); } if (this .getRightHeroNode() != null ) { this .getRightHeroNode().deleteHeroNode(no); } } 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 getLeftHeroNode () { return leftHeroNode; } public void setLeftHeroNode (HeroNode leftHeroNode) { this .leftHeroNode = leftHeroNode; } public HeroNode getRightHeroNode () { return rightHeroNode; } public void setRightHeroNode (HeroNode rightHeroNode) { this .rightHeroNode = rightHeroNode; } @Override public String toString () { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}' ; } }
顺序存储二叉树 顺序存储二叉树的概念
从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组,看下面的示意图。
要求: 1)右图的二叉树的结点,要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 7];
2)要求在遍历数组 arr时,仍然可以以前序遍历,中序遍历和后序遍历的方式完成结点的遍历。
顺序存储二叉树的特点:
1)顺序二叉树通常只考虑完全二叉树; 2)第n个元素的左子节点为 2 * n + 1; 3)第n个元素的右子节点为 2 * n + 2; 4)第n个元素的父节点为 (n-1) / 2。
顺序存储二叉树图解:
顺序存储二叉树代码:
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 public class ArrayBinaryTreeDemo { public static void main (String[] args) { int [] arr = {1 , 2 , 3 , 4 , 5 , 6 , 7 }; ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr); System.out.println("========前序遍历========" ); arrayBinaryTree.preOrder(0 ); System.out.println("" ); System.out.println("========中序遍历========" ); arrayBinaryTree.midOrder(0 ); System.out.println("" ); System.out.println("========后序遍历========" ); arrayBinaryTree.posOrder(0 ); } } class ArrayBinaryTree { private int [] arr; public ArrayBinaryTree (int [] arr) { this .arr = arr; } public void preOrder (int index) { if (arr == null || arr.length == 0 ) { System.out.println("空数组" ); return ; } System.out.print(arr[index] + " " ); if ((2 * index + 1 ) < arr.length) { preOrder(2 * index + 1 ); } if ((2 * index + 2 ) < arr.length) { preOrder(2 * index + 2 ); } } public void midOrder (int index) { if (arr == null || arr.length == 0 ) { System.out.println("空数组" ); return ; } if ((2 * index + 1 ) < arr.length) { preOrder(2 * index + 1 ); } System.out.print(arr[index] + " " ); if ((2 * index + 2 ) < arr.length) { preOrder(2 * index + 2 ); } } public void posOrder (int index) { if (arr == null || arr.length == 0 ) { System.out.println("空数组" ); return ; } if ((2 * index + 1 ) < arr.length) { preOrder(2 * index + 1 ); } if ((2 * index + 2 ) < arr.length) { preOrder(2 * index + 2 ); } System.out.print(arr[index] + " " ); } }
线索化二叉树 线索二叉树基本介绍:
1)n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为”线索”); 2)这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种; 3)一个结点的前一个结点,称为前驱结点; 4)一个结点的后一个结点,称为后继结点。
当线索化二叉树后,Node节点的 属性 left 和 right ,有如下情况: 1)left 指向的是左子树,也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点; 2)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 public class ThreadedBinaryTreeDemo { public static void main (String[] args) { HeroNode root = new HeroNode(1 , "America" ); HeroNode node2 = new HeroNode(3 , "Clinton" ); HeroNode node3 = new HeroNode(6 , "Bush" ); HeroNode node4 = new HeroNode(8 , "Obama" ); HeroNode node5 = new HeroNode(10 , "Trump" ); HeroNode node6 = new HeroNode(14 , "Biden" ); root.setLeftHeroNode(node2); root.setRightHeroNode(node3); node2.setLeftHeroNode(node4); node2.setRightHeroNode(node5); node3.setLeftHeroNode(node6); ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree(root); threadedBinaryTree.setMidOrderThreadedBinaryTree(root); HeroNode leftNode = node5.getLeftHeroNode(); HeroNode rightNode = node5.getRightHeroNode(); System.out.println("10号结点的前驱结点是 =" + leftNode); System.out.println("10号结点的后继结点是=" + rightNode); System.out.println("使用线索化的方式遍历 线索化二叉树" ); threadedBinaryTree.midOrderThreadedList(); } } class ThreadedBinaryTree { private HeroNode root; private HeroNode pre = null ; public ThreadedBinaryTree (HeroNode root) { this .root = root; } public void midOrderThreadedList () { HeroNode node = root; while (node != null ) { while (node.getLeftType() == 0 ) { node = node.getLeftHeroNode(); } System.out.println(node); while (node.getRightType() == 1 ) { node = node.getRightHeroNode(); System.out.println(node); } node = node.getRightHeroNode(); } } public void setMidOrderThreadedBinaryTree (HeroNode node) { if (node == null ) { return ; } setMidOrderThreadedBinaryTree(node.getLeftHeroNode()); if (node.getLeftHeroNode() == null ) { node.setLeftHeroNode(pre); node.setLeftType(1 ); } if (pre != null && pre.getRightHeroNode() == null ) { pre.setRightHeroNode(node); pre.setRightType(1 ); } pre = node; setMidOrderThreadedBinaryTree(node.getRightHeroNode()); } } class HeroNode { private int no; private String name; private HeroNode leftHeroNode; private HeroNode rightHeroNode; private int leftType; private int rightType; public HeroNode (int no, String name) { 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 getLeftHeroNode () { return leftHeroNode; } public void setLeftHeroNode (HeroNode leftHeroNode) { this .leftHeroNode = leftHeroNode; } public HeroNode getRightHeroNode () { return rightHeroNode; } public void setRightHeroNode (HeroNode rightHeroNode) { this .rightHeroNode = rightHeroNode; } 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; } @Override public String toString () { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}' ; } }
树的常用术语
树的常用术语(结合示意图理解): 1)节点 2)根节点 3)父节点 4)子节点 5)叶子节点 (没有子节点的节点) 6)节点的权(节点值) 7)路径(从root节点找到该节点的路线) 8)层 9)子树 10)树的高度(最大层数) 11)森林 :多颗子树构成森林
延伸 二叉树基础 二叉树-百度百科 韩顺平数据结构和算法 Data Structure and Algorithms - Tree