主要利用java实现了二叉树的一些基本操作：
- 获取树的深度；
- 添加、删除节点
- 获取左右兄弟节点
- 简单的递归中序遍历。。后续会提供前序，后序遍历的方法以及非递归遍历的方法
BinaryTree 1 package Tree; 2 3 class BTNode { 4 int data; 5 BTNode left; 6 BTNode right; 7 8 public BTNode(int data) { 9 this(data, null, null); 10 } 11 12 public BTNode(int data, BTNode left, BTNode right) { 13 this.data = data; 14 this.left = left; 15 this.right = right; 16 } 17 } 18 19 class BinaryTree { 20 BTNode root; 21 22 /** 23 * 创建一个空的二叉树 24 */ 25 public void initBiTree() { 26 root = null;// new BTNode (null); 27 } 28 29 /** 30 * 利用数组输入构建二叉树 31 * 32 * @param data 33 * 要输入的数值 34 */ 35 public void buildTree(int[] data) { 36 root = new BTNode(data[0]); 37 for (int i = 1; i < data.length; i++) { 38 BTNode tmpNode = root;//new BTNode(data[i]); 39 while (true) { 40 if (tmpNode.data == data[i]) 41 break; 42 if (tmpNode.data > data[i]) { // 小于等于根节点 43 if (tmpNode.left == null) { // 如果左孩子为空，这把当前数组元素插入到左孩子节点的位置 44 tmpNode.left = new BTNode(data[i]); 45 break; 46 } 47 tmpNode = tmpNode.left;// 如果不为空的话，则把左孩子节点用来和当前数组元素作比较 48 } else { // 大于根节点 49 if (tmpNode.right == null) { // 如果右孩子为空，这把当前数组元素插入到左孩子节点的位置 50 tmpNode.right = new BTNode(data[i]); 51 break; 52 } 53 tmpNode = tmpNode.right;// 如果不为空的话，则把右孩子节点用来和当前数组元素作比较 54 } 55 } 56 } 57 } 58 59 // 清空二叉树 60 public void destroyBiTree() { 61 destroyBiTree(root); 62 } 63 64 private void destroyBiTree(BTNode root) { 65 while (root != null) { 66 destroyBiTree(root.left); 67 destroyBiTree(root.right); 68 } 69 } 70 71 // 将二叉树清为空树 72 public void clearBiTree() { 73 if (root == null) 74 return; 75 root = null; 76 } 77 78 // 查找二叉查找树的最小节点 79 public BTNode getMinNode(BTNode node) { 80 while (node.left != null) { 81 node = node.left; 82 } 83 return node; 84 } 85 86 // 查找二叉查找树的最大节点 87 public BTNode getMaxNode(BTNode node) { 88 while (node.right != null) { 89 node = node.right; 90 } 91 return node; 92 } 93 94 // 查找节点的前驱节点 95 public BTNode getPredecessor(BTNode node) { 96 if (node.left != null) { 97 return getMaxNode(node.left);// 左子树的最大值 98 } 99 BTNode parent = getParent(node);100 //System.out.println("K的父节点(k的data为54)：" + y.data);101 while (parent != null && node == parent.left) { // 向上找到最近的一个节点，其父亲节点的右子树包涵了当前节点或者其父亲节点为空102 node = parent;103 parent = getParent(parent);104 }105 return parent;106 }107 108 // 查找节点的后继节点109 public BTNode getSuccessor(BTNode node) {110 if (node.right != null) {111 return getMinNode(node.right);// 右子树的最小值112 }113 //为了避免54,87,43的情况114 BTNode parent = getParent(node);115 //System.out.println("K的父节点(k的data为54)：" + y.data); 116 if (parent == null)117 return null;118 while (parent != null) {119 if (parent.left == node) {120 return parent; //为左子树情况，后继为父节点121 } else {122 node = parent; //否则递归123 parent = getParent(parent);124 }125 }126 return parent;127 }128 129 // 求出父亲节点，在定义节点类BSTreeNode的时候，没有申明父亲节点，所以这里专门用parent用来输出父亲节点（主要是不想修改代码了，就在这里加一个parent函数吧）130 public BTNode getParent(BTNode node) {131 BTNode p = root;132 BTNode tmp = null;133 while (p != null && p.data != node.data) { // 最后的p为p.data等于k.data的节点，tmp为p的父亲节点134 if (p.data > node.data) {135 tmp = p;// 临时存放父亲节点136 p = p.left;137 } else {138 tmp = p;// 临时存放父亲节点139 p = p.right;140 }141 }142 return tmp;143 }144 145 //返回root根节点146 public BTNode getRootNode() {147 return root;148 }149 150 public int getDepth() {151 int depth = 0;152 depth = getRecDepth(root);153 return depth;154 }155 156 private int getRecDepth(BTNode node) {157 if (node == null) {158 return 0;159 }160 //没有子树 161 if (node.left == null && node.right == null) {162 return 1;163 } else {164 int leftDeep = getRecDepth(node.left);165 int rightDeep = getRecDepth(node.right);166 //记录其所有左、右子树中较大的深度 167 int max = leftDeep > rightDeep ? leftDeep : rightDeep;168 //返回其左右子树中较大的深度 + 1 169 return max + 1;170 }171 }172 173 //或者直接放入到BTNode的属性当中去174 public int getNodeValue(BTNode node) {175 return node!=null?node.data:-1;176 }177 178 public BTNode getLeftChild(BTNode node) {179 return node!=null?node.left:null;180 }181 182 public BTNode getRightChild(BTNode node) {183 return node!=null?node.right:null;184 }185 186 public BTNode getLeftSibling(BTNode node) {187 BTNode parent = getParent(node);188 //node为左孩子或者无左兄弟节点189 if(parent.data>node.data||parent.left == null)190 return null;191 return parent.left;192 }193 194 public BTNode getRightSibling(BTNode node) {195 BTNode parent = getParent(node);196 //node为右孩子或者无右兄弟节点右边197 if(parent.data data)208 return existNode(p.left, data);209 else210 return existNode(p.right, data);211 }212 }213 return false;214 }215 216 public BTNode getExsitNode(int data) {217 if (existNode(root, data)) {218 return getExsitNode(root, data);219 }220 return null;221 }222 223 private BTNode getExsitNode(BTNode p, int data) {224 if (p.data == data)225 return p;226 if (p.data > data)227 return getExsitNode(p.left, data);228 else229 return getExsitNode(p.right, data);230 }231 232 public boolean isEmpty() {233 return (root == null);234 }235 236 //与二叉查找树的删除有些区别237 public boolean deleteChild(BTNode node) {238 BTNode p = root;239 boolean exsits = existNode(root, node.data);240 if (exsits && p != null) {241 //deleteRecChild(node);242 BTNode parent = getParent(node);243 if (parent.data > node.data)//即node为左节点244 {245 parent.left = null;246 } else {247 parent.right = null;248 }249 }250 return false;251 }252 253 //递归删除node对应的子树254 public void deleteRecChild(BTNode node) {255 BTNode parent = getParent(node);256 System.out.println("parentData=" + parent.data);257 if (node.left != null || node.right != null) {258 //递归出现问题259 deleteRecChild(node.left);260 deleteRecChild(node.right);261 } else {262 if (parent.data > node.data)//即node为左节点263 {264 parent.left = null;265 } else {266 parent.right = null;267 }268 }269 }270 271 //插入指定的node节点272 public void insertChild(BTNode node) {273 BTNode p = root;274 while (true) {275 if (p.data == node.data)276 return;277 else if (p.data > node.data) {278 if (p.left == null) {279 p.left = node;280 break;281 }282 p = p.left;283 } else {284 if (p.right == null) {285 p.right = node;286 break;287 }288 p = p.right;289 }290 }291 }292 293 //插入data294 public void insertNode(int data) {295 296 }297 298 // 批量插入节点299 public void insertChild(int[] data) {300 301 }302 303 /**304 * 递归打印出二叉树305 */306 public void traversalBiTree() {307 traversalBiTree(root);308 System.out.println();309 }310 311 /**312 * 从根结点开始遍历，从树的最高层叶子结点开始输出，从左至右313 * 314 * @param node315 * 当前的结点316 */317 private void traversalBiTree(BTNode node) {318 if (node != null) {319 traversalBiTree(node.left);320 System.out.print(node.data + " ");321 traversalBiTree(node.right);322 }323 }324 }325 326 public class BinaryTreeTest {327 public static void main(String[] args) {328 Integer a = new Integer(6);329 Integer b = new Integer(7);330 Integer c = new Integer(8);331 System.out.println(c.compareTo(b) + " " + a);332 333 BinaryTree biTree = new BinaryTree();334 335 /************************336 * 构造的二叉树结构为：337 * 2338 * / \339 * 1 8340 * / \341 * 7 9342 * /343 * 4344 * / \345 * 3 6346 * /347 * 5348 * **********************/349 350 /************************351 * 初始化操作352 * **********************/353 int[] data = { 2, 8, 7, 4, 9, 3, 1, 6, 7, 5 };354 biTree.buildTree(data);355 System.out.println("二叉树的深度为:" + biTree.getDepth());356 System.out.println("初始化后，二叉树遍历结果:");357 biTree.traversalBiTree();358 BTNode p = biTree.root;359 System.out.println("根节点相关信息:" + p.right.right.data + " "360 + p.right.left.data);361 362 /************************363 * 插入子节点操作364 * **********************/365 BTNode node = new BTNode(10);366 biTree.insertChild(node);367 System.out.println("插入子节点后，二叉树遍历结果:");368 biTree.traversalBiTree();369 370 node = new BTNode(7);371 boolean result;372 result = biTree.existNode(biTree.root, node.data);373 System.out.println(result == true ? "Node存在" : "Node不存在");374 375 /************************376 * 递归删除子树操作377 * **********************/378 node = biTree.getExsitNode(7);379 System.out.println("左右孩子节点分别为："+biTree.getNodeValue(node.left)+" "+biTree.getNodeValue(node.right));380 System.out.println("节点的左右兄弟节点分别为："+biTree.getLeftSibling(node)+" "+biTree.getRightSibling(node));381 382 biTree.deleteChild(node);383 System.out.println("递归删除子树后，二叉树遍历结果:");384 biTree.traversalBiTree();385 386 /************************387 * 清空操作388 * **********************/389 //biTree.clearBiTree();390 //biTree.traversalBiTree();391 }392 }