[toc]
二叉排序树
给你一个数列 (7, 3, 10, 12, 5, 1, 9),要求能够高效的完成对数据的查询和添加
1. 二叉排序树介绍
- 二叉排序树:**
BST: (Binary Sort(Search) Tree)
**, 对于二叉排序树的 任何一个非叶子节点,要求 左子节点的值比当前节点的值小, 右子节点的值比当前节点的值大。
特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点
- 比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ,对应的二叉排序树为
2. 二叉排序树的创建
2.1 节点Node
创建
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
|
class Node{ int value; Node left; Node right;
public Node(int value) { this.value = value; }
@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(); } } }
|
2.2 BST
二叉排序树的创建
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
|
class BinarySortTree{ private Node root; public Node getRoot() { return root; }
public void setRoot(Node root) { this.root = root; }
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("二叉排序树为空不能遍历"); } } }
|
2.3 测试并创建的顺序二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {7,3,10,12,5,1,9,2}; BinarySortTree binarySortTree = new BinarySortTree(); for (int i = 0; i < arr.length; i++) { binarySortTree.add(new Node(arr[i])); } System.out.println("中序遍历二叉排序树"); binarySortTree.infixOrder(); } }
|
3. 二叉排序树的删除
二叉排序树的删除情况比较复杂,有下面三种情况需要考虑:
- 删除叶子节点 (比如:2, 5, 9, 12)
- 删除点 只有一颗子树的节点 (比如:1)
- 删除 有两颗子树的节点. (比如: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
|
第一种情况:删除叶子节点 (比如: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
|
3.1 Node类中添加以下方法
public Node search(int value);
public Node searchParent(int value);
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
|
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; } } }
|
3.2 BinarySortTree
类中添加以下方法
public Node search(int value);
public Node searchParent(int value);
public void delNode(int value);
public int delRightTreeMin(Node node)
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
|
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 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 parentNode = searchParent(value); if(targetNode.left == null && targetNode.right == null ) { if(parentNode.left != null && parentNode.left.value == value) { parentNode.left = null; }else if(parentNode.right != null && parentNode.right.value == value) { parentNode.right = null; } }else if(targetNode.left != null && targetNode.right != null) { int minVal = delRightTreeMin(targetNode.right); targetNode.value = minVal;
}else { if(targetNode.left != null) { if(parentNode != null) { if(parentNode.left.value == value) { parentNode.left = targetNode.left; }else { parentNode.right = targetNode.left; } }else { root = targetNode.left; } }else { if(parentNode != null) { if(parentNode.left.value == value) { parentNode.left = targetNode.right; }else { parentNode.right = targetNode.right; } }else { root = targetNode.right; } } } }
}
public int delRightTreeMin(Node node) { Node target = node; while(target.left != null) { target = target.left; } delNode(target.value); return target.value; }
|
☆