Data Structure Binary Sort Tree
Tree sort is a sorting algorithm that is based on Binary Search Tree data structure. It first creates a binary search tree from the elements of the input list or array and then performs an in-order traversal on the created binary search tree to get the elements in sorted order.
前言 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),也称二叉搜索树。二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;(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 public class BinarySortTreeDemo { public static void main (String[] args) { int [] arr = {7 , 3 , 10 , 12 , 5 , 1 , 9 }; BinarySortTree binarySortTree = new BinarySortTree(); for (int i : arr) { binarySortTree.addNode(new Node(i)); } System.out.println("二叉排序树前序遍历" ); binarySortTree.preOrder(); System.out.println("删除节点后前序遍历" ); binarySortTree.deleteNode(7 ); binarySortTree.preOrder(); System.out.println("root节点:" + binarySortTree.getRoot()); } } class BinarySortTree { private Node root; public BinarySortTree () { } public Node getRoot () { return root; } public Node searchTargetNode (int value) { if (root == null ) { return null ; } else { return root.searchTargetNode(value); } } public Node searchParentNode (int value) { if (root == null ) { return null ; } else { return root.searchParentNode(value); } } public int delRightTreeMin (Node node) { Node target = node; while (target.leftNode != null ) { target = target.leftNode; } deleteNode(target.value); return target.value; } public void deleteNode (int value) { if (root == null ) { System.out.println("空树无法删除" ); return ; } else { Node targetNode = searchTargetNode(value); if (targetNode == null ) { System.out.println("该结点不存在,无法删除" ); return ; } if (root.leftNode == null && root.rightNode == null ) { root = null ; return ; } Node parentNode = searchParentNode(value); if (targetNode.leftNode == null && targetNode.rightNode == null ) { if (parentNode.leftNode != null && parentNode.leftNode.value == value) { parentNode.leftNode = null ; } else if (parentNode.rightNode != null && parentNode.rightNode.value == value) { parentNode.rightNode = null ; } } else if (targetNode.leftNode != null && targetNode.rightNode != null ) { int minVal = delRightTreeMin(targetNode.rightNode); targetNode.value = minVal; } else { if (targetNode.leftNode != null ) { if (parentNode != null ) { if (parentNode.leftNode.value == value) { parentNode.leftNode = targetNode.leftNode; } else { parentNode.rightNode = targetNode.leftNode; } } else { root = targetNode.leftNode; } } else { if (parentNode != null ) { if (parentNode.leftNode.value == value) { parentNode.leftNode = targetNode.rightNode; } else { parentNode.leftNode = targetNode.rightNode; } } else { root = targetNode.rightNode; } } } } } public void addNode (Node node) { if (node == null ) { return ; } if (root == null ) { root = node; } else { root.addNode(node); } } public void preOrder () { if (root == null ) { System.out.println("空树无法遍历" ); return ; } root.preOrder(); } } class Node { int value; Node leftNode; Node rightNode; public Node (int value) { this .value = value; } public Node searchParentNode (int value) { if ((this .leftNode != null && this .leftNode.value == value) || (this .rightNode != null && this .rightNode.value == value)) { return this ; } else { if (value > this .value && this .rightNode != null ) { return this .rightNode.searchParentNode(value); } else if (value < this .value && this .leftNode != null ) { return this .leftNode.searchParentNode(value); } else { return null ; } } } public Node searchTargetNode (int value) { if (this .value == value) { return this ; } else if (this .value > value) { if (this .leftNode == null ) { return null ; } else { return this .leftNode.searchTargetNode(value); } } else { if (this .rightNode == null ) { return null ; } else { return this .rightNode.searchTargetNode(value); } } } public void addNode (Node node) { if (this .value > node.value) { if (this .leftNode == null ) { this .leftNode = node; } else { this .leftNode.addNode(node); } } else { if (this .rightNode == null ) { this .rightNode = node; } else { this .rightNode.addNode(node); } } } public void preOrder () { System.out.println(this ); if (this .leftNode != null ) { this .leftNode.preOrder(); } if (this .rightNode != null ) { this .rightNode.preOrder(); } } @Override public String toString () { return "Node{" + "value=" + value + '}' ; } }
延伸 二叉排序树 深入学习 二叉排序树 韩顺平数据结构和算法 Data Structure - Binary Search Tree
<
Data Structure AVL Tree
Data Structure Huffman Tree
>