二叉排序树的非递归插入，非递归查询，寻找最大值，寻找最小值
| 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 | package whut.tree; //二叉排序树的非递归插入，非递归查询，寻找最大值，寻找最小值 class Node { private int data; private Node left; private Node right; public Node( int data) { this .data = data; } public int getData() { return data; } public Node getLeft() { return left; } public void setLeft(Node left) { this .left = left; } public Node getRight() { return right; } public void setRight(Node right) { this .right = right; } // 展示节点数据 public void displayNode() { System.out.println( " " + data + " " ); } } // 树 public class BinaryTree { private Node root; // 树根 // 非递归方式插入新的节点数据， public void insert( int data) { Node newNode = new Node(data); if (root == null ) { root = newNode; } else { // 子节点，当前节点 Node current = root; // 父节点 Node parent; while ( true ) // 寻找插入的位置 { parent = current; // 当小于根节点，插入到左边 if (data < current.getData()) { current = current.getLeft(); // 跳出循环 if (current == null ) { parent.setLeft(newNode); return ; } } else { current = current.getRight(); if (current == null ) { parent.setRight(newNode); return ; } } } } } // 非递归方式实现查询 public Node find( int data) { Node current = root; while (current.getData() != data) { if (current.getData() < data) current = current.getLeft(); else current = current.getRight(); // 当一个元素不在一个二叉树中，肯定为null了 if (current == null ) return null ; } // 跳出循环说明找到了那个相等的 return current; } // 找二叉树最小的节点,一直遍历左孩子，直到其左孩子为null public Node findMinNode() { Node current; Node parent; // if (root == null ) { return null ; } else { parent = root; current = parent.getLeft(); while (current != null ) { parent = current; current = current.getLeft(); } return parent; } } // 找到二叉排序树的最大值，也就是最右边的孩子 public Node findMaxNode() { Node current; Node parent; // if (root == null ) { return null ; } else { parent = root; current = parent.getRight(); while (current != null ) { parent = current; current = current.getRight(); } return parent; } } // 先要找到节点，然后根据要删除节点的位置进行删除 // 删除的节点有三种，叶子节点，有一个节点的节点，有两个节点的节点 public boolean delete( int key) { Node current = root; Node parent = root; // 这里主要是为了区分删除的是左孩子还是右孩子 boolean isLeftChild = false ; // 显然，当current.iData == key 时，current就是需要删除的节点 // 在循环中利用parent保存了父类节点 while (current.getData() != key) { parent = current; if (key < current.getData()) { isLeftChild = true ; current = current.getLeft(); } else { isLeftChild = false ; current = current.getRight(); } if (current == null ) // 找不到key时返回false return false ; } // 当节点为叶子节点的时候 if (current.getLeft() == null && current.getRight() == null ) { if (current == root) root = null ; else if (isLeftChild) parent.setLeft( null ); else parent.setRight( null ); } // 当删除的节点为含有一个子节点的节点 // 删除的节点只有一个左子节点时 // 必须要考虑被删除的节点是左节点还是右节点 else if (current.getRight() == null ) { if (current == root) // 要删除的节点为根节点 root = current.getLeft(); else if (isLeftChild) // 要删除的节点是一个左子节点 parent.setLeft(current.getLeft()); else parent.setRight(current.getLeft()); // 要删除的节点是一个右子节点 } // 当删除的节点为含有一个子节点的节点 // 删除的节点只有一个右子节点时 // 必须要考虑被删除的节点是左节点还是右节点 else if (current.getLeft() == null ) { if (current == root) // 要删除的节点为根节点 root = current.getRight(); else if (isLeftChild) // 要删除的节点是一个左子节点 parent.setLeft(current.getRight()); else parent.setRight(current.getRight()); // 要删除的节点是一个右子节点 } // 当要删除的节点是含有两个节点的时候 else { //首先要获取被删除节点的后继节点，current Node successor = getSuccessor(current); if (current == root) root = successor ; //这里已经屏蔽了后继节点是叶子和非叶子节点 else if (isLeftChild) parent.setLeft(successor); else parent.setRight(successor); successor.setLeft(current.getLeft()); } return true ; } // 寻找后记节点，主要是当要删除的节点包含了两个子节点的时候 // 返回后继节点,后继节点就是比要删除的节点的关键值要大的节点集合中的最小值。 //后继节点要么是被删除节点的不包含左子节点的右节点，要么就是包含左子节点的右节点的子节点 private Node getSuccessor(Node delNode) { // 后继节点的父节点 Node successorParent = delNode; // 后继节点 Node successor = delNode.getRight(); //判断后继节点是否有左孩子 Node current = successor.getLeft(); while (current != null ) { successorParent = successor; successor = current; current = current.getLeft(); } //当该后继节点是属于包含左子节点的右节点的子节点 if (successor != delNode.getRight()) { successorParent.setLeft(successor.getRight()); //连接被删除节点的右孩子 successor.setRight(delNode.getRight()); } return successor; } // 下面三种遍历树 // 三种遍历均是采用递归实现的 // 前序遍历 public void preOrder(Node localRoot) { if (localRoot != null ) { localRoot.displayNode(); // 访问这个节点 preOrder(localRoot.getLeft()); // 调用自身来遍历左子树 preOrder(localRoot.getRight()); // 调用自身来遍历右子树 } } // 中序遍历 public void midOrder(Node localRoot) { if (localRoot != null ) { preOrder(localRoot.getLeft()); // 调用自身来遍历左子树 localRoot.displayNode(); // 访问这个节点 preOrder(localRoot.getRight()); // 调用自身来遍历右子树 } } // 后续遍历 public void lastOrder(Node localRoot) { if (localRoot != null ) { preOrder(localRoot.getLeft()); // 调用自身来遍历左子树 preOrder(localRoot.getRight()); // 调用自身来遍历右子树 localRoot.displayNode(); // 访问这个节点 } } } |
二叉排序树的递归插入，递归遍历，递归查询
| 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 | package whut.tree; //二叉树的存储，这里会建立一个二叉排序树,递归方式 public class NodeTree { public int value; public NodeTree left; public NodeTree right; //递归实现存储 public void store( int value) { if (value < this .value) { if (left == null ) { left = new NodeTree(); left.value = value; } else { left.store(value); } } else if (value > this .value) { if (right == null ) { right = new NodeTree(); right.value = value; } else { right.store(value); } } } public boolean find( int value) { System.out.println( "find happen " + this .value); if (value == this .value) { return true ; } else if (value > this .value) { if (right == null ) return false ; return right.find(value); } else { if (left == null ) return false ; return left.find(value); } } //前序遍历 public void preList() { System.out.print( this .value + "," ); if (left != null ) left.preList(); if (right != null ) right.preList(); } //中序遍历 public void middleList() { if (left != null ) left.middleList(); System.out.print( this .value + "," ); if (right != null ) right.middleList(); } //后续遍历 public void afterList() { if (left != null ) left.afterList(); if (right != null ) right.afterList(); System.out.print( this .value + "," ); } public static void main(String[] args) { int [] data = new int [ 20 ]; for ( int i = 0 ; i < data.length; i++) { data[i] = ( int ) (Math.random() * 100 ) + 1 ; System.out.print(data[i] + "," ); } System.out.println(); NodeTree root = new NodeTree(); root.value = data[ 0 ]; for ( int i = 1 ; i < data.length; i++) { root.store(data[i]); } //查询 root.find(data[ 19 ]); //先序 root.preList(); System.out.println(); //中序 root.middleList(); System.out.println(); //后续 root.afterList(); } } |