有序二叉树java实现

类实现：

package 树;import java.util.LinkedList;
import java.util.Queue;public class BinaryTree {public TreeNode root;//插入public void insert(int value){//插入成功之后要return结束方法TreeNode node = new TreeNode(value);//如果root为空的话插入if(root == null){root = node;return;}//定义游标遍历二叉树TreeNode index = root;while (true){if(index.value<value){//要插入的节点是大的if(index.right==null){//插入index.right=node;return;}index = index.right;}else {//新插入的值小if(index.left==null){index.left=node;return;}index = index.left;}}}//广度优先搜索，借助队列实现,如果队列不为空的话就让队列头出队，将出队的左右孩子依次进队public void levelOrder(){Queue<TreeNode> queue = new LinkedList<TreeNode>();if(root!=null){queue.add(root);}else {System.out.println("树为空，请先插入数据");}while ((!queue.isEmpty())){TreeNode index = queue.poll();System.out.print(index.value + " ");if(index.left!=null){queue.add(index.left);}if(index.right!=null){queue.add(index.right);}}System.out.println();}//先序遍历public void beforeOrder(TreeNode node){if(node == null){return;}System.out.print(" "+node.value+" ");beforeOrder(node.left);beforeOrder(node.right);}//中序遍历public void inOrder(TreeNode node){if(node == null){return;}inOrder(node.left);System.out.print(" "+node.value+" ");inOrder(node.right);}//后序遍历public void adterOrder(TreeNode node){if(node == null){return;}adterOrder(node.left);adterOrder(node.right);System.out.print(" "+node.value+" ");}//查找public TreeNode seach(int value){if(root==null){return null;}//如果不是空的话，定义一个游标，指向根节点TreeNode index = root;while (index.value!=value){//如果目标值大if(index.value<value){index = index.right;}else {index = index.left;}if (index==null){return null;}}return index;}//查找节点的父节点public TreeNode searchParent(int value){if (root==null){return null;}//如果不是空的话，定义一个游标，指向根节点TreeNode index = root;//判断treeNode是不是目标节点的父节点while (true){if((index.left!=null&&index.left.value==value)||(index.right!=null&&index.right.value==value)){return index;}else if (value>index.value&&index.right!=null){//目标值大，index游标往右走index = index.right;}else if (value<index.value&&index.left!=null){//目标值小，index游标往左走index = index.left;}else {//没有父节点return null;}}}//找一棵树中的最小值public int min(TreeNode node){TreeNode index = node;if(index.left!=null){index = index.left;}return index.value;}//找一棵树中的最大值public int max(TreeNode node){TreeNode index = node;if(index.right!=null){index = index.right;}return index.value;}//删除public  void delete(int value){if (root==null){System.out.println("此树为空，无需删除");return;}//找到要删除的目标节点TreeNode targer = seach(value);//没有找到目标节点if (targer==null){System.out.println("没有此节点");return;}//找目标节点的父节点TreeNode parent = searchParent(value);//分为三大类if (targer.left==null&&targer.right==null){//删除叶子节点//如果没有父节点if (parent==null){root = null;return;}//如果有父节点//确定要删除的节点是父节点的左孩子还是右孩子if (parent.left!=null&&parent.left.value==value){parent.left = null;}else {parent.right = null;}}else if (targer.left!=null&&targer.right!=null){//删除有两棵子树的节点//找到目标节点右子树的最小值(或者左子树的最大值)int min = min(targer.right);//删除最小值的节点delete(min);//目标节点的值被最小值覆盖targer.value = min;}else {//删除只有一棵字数的节点//如果没有父节点if (parent==null){//判断目标节点有左子树还是有右子树if(targer.left!=null){//有左子树root = targer.left;}else {//有右子树root = targer.right;}return;}//有父节点//确定要删除的节点是父节点的左孩子还是右孩子if (parent.left!=null&&parent.left.value==value){//要删除的节点是父节点的左孩子//判断目标节点有左孩子还是右孩子if(targer.left!=null){//有左孩子parent.left = targer.left;}else {//有右孩子parent.left = targer.right;}}else {//要删除的节点是父节点的右孩子//判断目标节点有左孩子还是右孩子if(targer.left!=null){//有左孩子parent.right = targer.left;}else {//有右孩子parent.right = targer.right;}}}}
}

Test测试：

package 测试;import 树.BinaryTree;public class TreeTest {public static void main(String[] args) {
//        TreeNode t1 = new TreeNode(6);
//        TreeNode t2 = new TreeNode(11);
//        TreeNode t3 = new TreeNode(18);
//        TreeNode t4 = new TreeNode(3);
//        TreeNode t5 = new TreeNode(32);
//        TreeNode t6 = new TreeNode(8);
//        TreeNode t7 = new TreeNode(16);
//
//        t1.left = t4;
//        t1.right = t6;
//        t2.left = t6;
//        t2.right = t7;
//        t3.left = t7;
//        t3.right = t5;
//        System.out.println(t1);BinaryTree tree = new BinaryTree();BinaryTree tree1 = new BinaryTree();tree.insert(10);tree.insert(15);tree.insert(21);tree.insert(8);tree.insert(9);tree.insert(1);tree.insert(12);tree.insert(19);System.out.println(tree.root);tree.levelOrder();tree1.levelOrder();System.out.print("先序遍历为：");tree.beforeOrder(tree.root);System.out.println();System.out.print("中序遍历为：");tree.inOrder(tree.root);System.out.println();System.out.print("后序遍历为：");tree.adterOrder(tree.root);System.out.println();System.out.println("==========================");System.out.println("删除之后:");tree.delete(15);System.out.print("先序遍历为：");tree.beforeOrder(tree.root);System.out.println();System.out.print("中序遍历为：");tree.inOrder(tree.root);System.out.println();System.out.print("后序遍历为：");tree.adterOrder(tree.root);}
}

运行结果：