/* * 二叉树节点 */public class Node {//数据项public long data;//左子节点public Node leftChild;//右子节点public Node rightChild;/** * 构造方法 * @param data */public Node(long data) {this.data = data;}}/* * 二叉树 */public class Tree {//根节点public Node root;/** * 插入节点 * @param value */public void insert(long value,String sValue) {//封装节点Node newNode = new Node(value);//引用当前节点Node current = root;//引用父节点Node parent;//如果root为null,也就是第一插入的时候if(root == null) {root = newNode;return;} else {while(true) {//父节点指向当前节点parent = current;//如果当前指向的节点数据比插入的要大,则向左走if(current.data > value) {current = current.leftChild;if(current == null) {parent.leftChild = newNode;return;}} else {current = current.rightChild;if(current == null) {parent.rightChild = newNode;return;}}}}}/** * 查找节点 * @param value */public Node find(long value) {//引用当前节点,从根节点开始Node current = root;//循环,只要查找值不等于当前节点的数据项while(current.data != value) {//进行比较,比较查找值和当前节点的大小if(current.data > value) {current = current.leftChild;} else {current = current.rightChild;}//如果查找不到if(current == null) {return null;}}return current;}/** * 删除节点  删除节点需要父子两层指针 * @param value */public boolean delete(long value) {//引用当前节点,从根节点开始Node current = root;//应用当前节点的父节点Node parent = root;//是否为左节点boolean isLeftChild = true;while(current.data != value) {parent = current;//进行比较,比较查找值和当前节点的大小if(current.data > value) {current = current.leftChild;isLeftChild = true;} else {current = current.rightChild;isLeftChild = false;}//如果查找不到if(current == null) {return false;}}//删除叶子节点,也就是该节点没有子节点if(current.leftChild == null && current.rightChild == null) {if(current == root) {root = null;} else if(isLeftChild) {parent.leftChild = null;} else {parent.rightChild = null;}//current的右节点空,判断current是parrent的左孩子?右孩子?决定current的leftchild插入位置} else if(current.rightChild == null) {if(current == root) {root = current.leftChild;}else if(isLeftChild) {parent.leftChild = current.leftChild;} else {//是右节点,比parent节点要大parent.rightChild = current.leftChild;}//current只有右孩子的情况,其次判断current是parent的左右孩子,判断插入parent的位置} else if(current.leftChild == null) {if(current == root) {root = current.rightChild;} else if(isLeftChild) {//current是parent的左孩子parent.leftChild = current.rightChild;} else {//current是parent的右孩子parent.rightChild = current.rightChild;}} else {//current既有左孩子,也有右孩子Node successor = getSuccessor(current);// 先处理删除节点的父if(current == root) {root = successor;} else if(isLeftChild) {parent.leftChild = successor;} else{parent.rightChild = successor;}// 处理删除节点的左节点successor.leftChild = current.leftChild;}return true;}public Node getSuccessor(Node delNode) {Node successor = delNode;Node successorParent = delNode;Node current = delNode.rightChild;//寻找右子树的最左侧节点,比被删除节点稍微大一点while(current != null) {successorParent = successor;successor = current;current = current.leftChild; // 删除节点的右子树的最左侧孩子节点}//被删除的右孩子,不等于找到的最左侧节点,successor就是右子树的最左侧孩子,successorParent是父节点//不等于就是找到了,if(successor != delNode.rightChild) {//将最左节点的右节点给父节点是左,比较小,所以放再leftsuccessorParent.leftChild = successor.rightChild;// 直接放到位置了successor.rightChild = delNode.rightChild;}return successor;}/** * 前序遍历 */public void frontOrder(Node localNode) {if(localNode != null) {//访问根节点System.out.println(localNode.data + " ");//前序遍历左子树frontOrder(localNode.leftChild);//前序遍历右子树frontOrder(localNode.rightChild);}}/** * 中序遍历 */public void inOrder(Node localNode) {if(localNode != null) {//中序遍历左子树inOrder(localNode.leftChild);//访问根节点System.out.println(localNode.data + " ");//中旬遍历右子树inOrder(localNode.rightChild);}}/** * 后序遍历 */public void afterOrder(Node localNode) {if(localNode != null) {//后序遍历左子树afterOrder(localNode.leftChild);//后序遍历右子树afterOrder(localNode.rightChild);//访问根节点System.out.println(localNode.data + " " );}}}