查找二叉树
查找二叉树的定义
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
一棵二叉搜索树（Binary Sort Tree）是以一棵二叉树来组织的，可以用链表数据结构来表示，其中，每一个结点就是一个对象，一般地，包含数据值和指向孩子（也可能是父母）的指针。如果某个孩子结点不存在，其指针为空（NULL）。
- 查找树的左右子树各是一棵查找树
- 若查找树的左子树非空，则其左子树上的各节点值均小于根节点的值。
- 若查找树的右子树非空，则其右子树上的各节点值均大于根节点的值。
二叉树的后继节点
对于下面的二叉树，8的后继节点为9(题目说的中序遍历)，6的后继节点为7，5的后继节点为6
①如果节点有右子树，则该节点的后继节点就是往右子树出发，然后转到右子树的左子树，一直到左子树的左子树为空（即输入节点的右子树的最左子树，例如节点8，后继节点就是9）其实就是找，结点的右结点里值最小结点。
②如果节点没有右子树，则向上寻找父节点，直到父节点的左子树等于当前节点，则该父节点就是后继节点（如节点7，没有右子树，则向上找，这时到6这个节点，因为6的左子树不等于7，所以继续向上找，这时到节点8，8的左子树等于当前节点6，所以返回8）
查找二叉树代码实现
1 package cn.itcast.test; 2
3 import sun.reflect.generics.tree.Tree; 4
5 public class SearchBinaryTree { 6 public static void main(String[] args) { 7 SearchBinaryTree binaryTree = new SearchBinaryTree(); 8 int[] intArray = new int[]{50, 30, 20, 44, 88, 33, 87, 16, 7, 77}; 9 for (int i : intArray) { 10 TreeNode put = binaryTree.put(i); 11 } 12 binaryTree.midOrder(binaryTree.root); 13 System.out.println("-----"); 14 try { 15 binaryTree.deleteNode(44); 16 binaryTree.midOrder(binaryTree.root); 17 } catch (Exception e) { 18 e.printStackTrace(); 19 } 20 } 21
22 //定义根结点
23 private TreeNode root; 24
25 public SearchBinaryTree() { 26
27 } 28
29 /**
30 * 中序遍历 31 * @param node 32 */
33 public void midOrder(TreeNode node) { 34 if (node == null) { 35 return; 36 } else { 37 midOrder(node.leftChild); 38 System.out.println(node.data); 39 midOrder(node.rightChild); 40 } 41 } 42
43 /**
44 * 创建查找二叉树，添加结点 45 */
46 public TreeNode put(int data) { 47 TreeNode node = null;//定义一个结点
48 TreeNode parent = null;//定义一个父节点
49 node = new TreeNode(0, data);//创建一个结点
50 if (root == null) { 51 root = node;//创建根节点
52 return node; 53 } 54 node = root; 55 while (node != null) {//找左右结点，直到note=null，跳出循环
56 parent = node;//先暂时把当前结点当做父节点
57 if (data > node.data) {//data：根节点
58 node = node.rightChild; 59 } else if (data < node.data) { 60 node = node.leftChild; 61 } else { 62 return node; 63 } 64 } 65
66 //表示将此结点添加到相应位置
67 node = new TreeNode(0, data); 68 if (data < parent.data) {//传data值
69 parent.leftChild = node; 70 node.parent = parent; 71 } else { 72 parent.rightChild = node; 73 node.parent = parent; 74 } 75 return node; 76 } 77
78
79 public void deleteNode(int key) throws Exception { 80 //查找node结点
81 TreeNode node = searchNode(key); 82 if (node == null) { 83 throw new Exception("该节点无法找到"); 84 } else { 85 //删除该结点
86 delete(node); 87 } 88 } 89
90 private void delete(TreeNode node) throws Exception { 91 //严谨，再判断一次，可以单独写一个方法判断
92 if (node == null) { 93 throw new Exception("该节点无法找到"); 94 } else { 95 TreeNode parent = node.parent; 96 //1.被删除的结点无左右孩子
97 if (node.leftChild == null && node.rightChild == null) { 98 if (parent.leftChild == node) { 99 parent.leftChild = null;//断开父结点与其的连接，等于删除了
100 } else { 101 parent.rightChild = null; 102 } 103 return; 104 } 105 //2.被删除的结点有左无右
106 if (node.leftChild != null && node.rightChild == null) { 107 if (parent.leftChild == node) { 108 //在父结点的左边，并且有左无右
109 parent.leftChild = node.leftChild; 110 } else { 111 //在父结点的右边，并且有左无右
112 parent.rightChild = node.leftChild; 113 } 114 return; 115 } 116 //3.被删除的结点有右无左
117 if (node.leftChild == null && node.rightChild != null) { 118 if (parent.leftChild == node) { 119 //在父结点的左边，并且有右无左
120 parent.leftChild = node.rightChild; 121 } else { 122 //在父结点的右边，并且有右无左
123 parent.rightChild = node.rightChild; 124 } 125 return; 126 } 127 //4.被删除的结点有左有右
128 TreeNode next = getNextNode(node);//找到该结点node的后继结点
129 delete(next);//递归
130 node.data = next.data;//完成赋值
131 } 132 } 133
134 /**
135 * 获取一个结点的后继结点 136 * @param node 137 * @return
138 */
139 private TreeNode getNextNode(TreeNode node) { 140 if (node == null) { 141 return null; 142 } else { 143 if (node.rightChild != null) { 144 //找某结点的最小关键字结点
145 return getMinTreeNode(node.rightChild); 146 } else { 147 TreeNode parent = node.parent; 148 //直到node是父结点的左结点，而不是父结点的右结点
149 while (parent != null && node == parent.rightChild) { 150 node = parent; 151 parent = parent.parent; 152 } 153 return parent; 154 } 155 } 156 } 157
158 private TreeNode getMinTreeNode(TreeNode node) { 159 if (node == null) { 160 return null; 161 } else { 162 //一直往左子树找，直到找到为止
163 while (node.leftChild != null) { 164 node = node.leftChild; 165 } 166 } 167 return node; 168 } 169
170 /**
171 * 找node结点，要么为空，要么找到 172 * 173 * @param key 174 * @return
175 */
176 private TreeNode searchNode(int key) { 177 TreeNode node = root;//为了从根节点开始查找
178 if (node == null) { 179 return null; 180 } else { 181 while (node != null && key != node.data) { 182 if (key < node.data) { 183 node = node.leftChild;//左子树永远比右子树小
184 } else { 185 node = node.rightChild; 186 } 187 } 188 } 189 return node; 190 } 191
192
193 class TreeNode { 194 private int key; 195 private TreeNode leftChild; 196 private TreeNode rightChild; 197 private TreeNode parent; 198 private int data; 199
200 public TreeNode(int key, int data) { 201 //调用父类的构造方法，即Object类的无参构造方法
202 super(); 203 this.key = key; 204 this.data = data; 205 this.leftChild = null; 206 this.rightChild = null; 207 this.parent = null; 208 } 209
210 public int getKey() { 211 return key; 212 } 213
214 public void setKey(int key) { 215 this.key = key; 216 } 217
218 public TreeNode getLeftChild() { 219 return leftChild; 220 } 221
222 public void setLeftChild(TreeNode leftChild) { 223 this.leftChild = leftChild; 224 } 225
226 public TreeNode getRightChild() { 227 return rightChild; 228 } 229
230 public void setRightChild(TreeNode rightChild) { 231 this.rightChild = rightChild; 232 } 233
234 public TreeNode getParent() { 235 return parent; 236 } 237
238 public void setParent(TreeNode parent) { 239 this.parent = parent; 240 } 241
242 public int getData() { 243 return data; 244 } 245
246 public void setData(int data) { 247 this.data = data; 248 } 249 } 250 }
更多精彩
