二叉搜索树(BinarySearchTree)的定义
实现代码
| 1 | // 定义树节点 |
| 2 | public class BTreeNode { |
| 3 | public BTreeNode left; // 左子树 |
| 4 | public BTreeNode right; // 右子树 |
| 5 | |
| 6 | public int key; |
| 7 | public Object value; |
| 8 | |
| 9 | public BTreeNode(int key) { |
| 10 | this(key,null,null,null); |
| 11 | } |
| 12 | |
| 13 | public BTreeNode(int key,Object value) { |
| 14 | this(key,value,null,null); |
| 15 | } |
| 16 | |
| 17 | public BTreeNode(int key,Object value,BTreeNode left,BTreeNode right) { |
| 18 | this.key = key; |
| 19 | this.value = value; |
| 20 | this.left = left; |
| 21 | this.right= right; |
| 22 | } |
| 23 | } |
二叉搜索数实现类
| 1 | public class BTreeSort { |
| 2 | // 树的根节点 |
| 3 | private BTreeNode root; |
| 4 | |
| 5 | // 打印节点信息 |
| 6 | public void printNode(BTreeNode root) { |
| 7 | System.out.print(" " + root.key + " "); |
| 8 | } |
| 9 | |
| 10 | // 计数树高 |
| 11 | public int height(BTreeNode root) { |
| 12 | if (null == root) { |
| 13 | return 0; |
| 14 | } |
| 15 | return Math.max(height(root.left), height(root.right)) + 1; |
| 16 | } |
| 17 | |
| 18 | // 获取root树中最大节点 |
| 19 | public BTreeNode max(BTreeNode root){ |
| 20 | BTreeNode node = root; |
| 21 | while (null !=node.right){ |
| 22 | node = node.right; |
| 23 | } |
| 24 | return node; |
| 25 | |
| 26 | } |
| 27 | |
| 28 | // 获取root树中最小节点 |
| 29 | public BTreeNode min(BTreeNode root){ |
| 30 | BTreeNode node = root; |
| 31 | while (null !=node.left){ |
| 32 | node = node.left; |
| 33 | } |
| 34 | return node; |
| 35 | } |
| 36 | |
| 37 | // 查找节点 |
| 38 | public boolean find(int key){ |
| 39 | BTreeNode node = findNode(root,key); |
| 40 | if (null == node){ |
| 41 | return false; |
| 42 | }else { |
| 43 | return true; |
| 44 | } |
| 45 | } |
| 46 | |
| 47 | public BTreeNode findNode(BTreeNode root,int key){ |
| 48 | if (null == root){ |
| 49 | return null; |
| 50 | } |
| 51 | if (root.key == key){ |
| 52 | return root; |
| 53 | } |
| 54 | if (root.key > key){ |
| 55 | return findNode(root.left,key); |
| 56 | }else{ |
| 57 | return findNode(root.right,key); |
| 58 | } |
| 59 | } |
| 60 | |
| 61 | // 构建搜索二叉树 |
| 62 | public void insert(int key) { |
| 63 | if (null == root) { |
| 64 | root = new BTreeNode(key); |
| 65 | return; |
| 66 | } |
| 67 | insert(root, key); |
| 68 | } |
| 69 | |
| 70 | public BTreeNode insert(BTreeNode root, int key) { |
| 71 | if (null == root) { |
| 72 | root = new BTreeNode(key); |
| 73 | return root; |
| 74 | } |
| 75 | if (root.key > key) { |
| 76 | root.left = insert(root.left, key); |
| 77 | } else { |
| 78 | root.right = insert(root.right, key); |
| 79 | } |
| 80 | return root; |
| 81 | } |
| 82 | |
| 83 | // 先顺遍历 |
| 84 | public void preTraversal() { |
| 85 | preTraversal(root); |
| 86 | } |
| 87 | |
| 88 | public void preTraversal(BTreeNode root) { |
| 89 | if (null == root) { |
| 90 | return; |
| 91 | } |
| 92 | printNode(root); |
| 93 | preTraversal(root.left); |
| 94 | preTraversal(root.right); |
| 95 | } |
| 96 | |
| 97 | // 中顺遍历 |
| 98 | public void midTraversal() { |
| 99 | midTraversal(root); |
| 100 | } |
| 101 | |
| 102 | public void midTraversal(BTreeNode root) { |
| 103 | if (null == root) { |
| 104 | return; |
| 105 | } |
| 106 | midTraversal(root.left); |
| 107 | printNode(root); |
| 108 | midTraversal(root.right); |
| 109 | } |
| 110 | |
| 111 | // 后序遍历 |
| 112 | public void afterTraversal() { |
| 113 | afterTraversal(root); |
| 114 | } |
| 115 | |
| 116 | public void afterTraversal(BTreeNode root) { |
| 117 | if (null == root) { |
| 118 | return; |
| 119 | } |
| 120 | afterTraversal(root.left); |
| 121 | afterTraversal(root.right); |
| 122 | printNode(root); |
| 123 | } |
| 124 | |
| 125 | // 删除节点 |
| 126 | public void delete(int key) { |
| 127 | delete(root,key); |
| 128 | } |
| 129 | |
| 130 | public BTreeNode delete(BTreeNode root, int key) { |
| 131 | if (null == root) { |
| 132 | return null; |
| 133 | } |
| 134 | |
| 135 | if (root.key == key) { |
| 136 | if (null != root.left && null != root.right) { |
| 137 | if (height(root.left) > height(root.right)) { |
| 138 | BTreeNode node = max(root.left); |
| 139 | root.key = node.key; |
| 140 | root.left=delete(root.left,node.key); |
| 141 | } else { |
| 142 | BTreeNode node = min(root.right); |
| 143 | root.key = node.key; |
| 144 | root.right = delete(root.right, node.key); |
| 145 | } |
| 146 | } else { |
| 147 | root = null != root.left ? root.left : root.right; |
| 148 | } |
| 149 | |
| 150 | return root; |
| 151 | } |
| 152 | if (root.key > key) { |
| 153 | root.left = delete(root.left, key); |
| 154 | } else { |
| 155 | root.right = delete(root.right, key); |
| 156 | } |
| 157 | return root; |
| 158 | } |
| 159 | |
| 160 | public static void main(String[] args) { |
| 161 | Integer a[] = { 17, 9, 15, 7, 33, 16, 10, 5, 77, 32, 1 }; |
| 162 | System.out.println(Arrays.asList(a)); |
| 163 | BTreeSort btree = new BTreeSort(); |
| 164 | for (Integer v : a) { |
| 165 | btree.insert(v.intValue()); |
| 166 | } |
| 167 | btree.delete(17); |
| 168 | System.out.print("先序遍历："); |
| 169 | btree.preTraversal(); |
| 170 | System.out.println(); |
| 171 | System.out.print("中序遍历："); |
| 172 | btree.midTraversal(); |
| 173 | System.out.println(); |
| 174 | System.out.print("后序遍历："); |
| 175 | btree.afterTraversal(); |
| 176 | System.out.println(); |
| 177 | |
| 178 | System.out.println("find:"+btree.find(23)); |
| 179 | |
| 180 | } |
| 181 | } |
说明：
1、Java对方法传参数是按值传递，所以在insert构造二叉树是root需要初始化后才能传递。
2、delete删除节点时做了平衡处理 if (height(root.left) > height(root.right))，该行代码表示如果左子树比右子树高，那么调整左子树(那边高就动那边，实现树的平衡)。
3、delete删除节点时，若调整左子树，那么使用左子树中最大的节点替换被删除的节点，并更新被替换节点的左子树。
4、delete删除节点时，若调整右子树，那么使用右子树中最小的节点替换被删除的节点，并更新被替换节点的右子树。
原文：http://www.cnblogs.com/jianyuan/p/5313905.html