public class Node {
public int data;
public Node left;
public Node right;
public Node(int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = 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 class BinaryTreeUtil {
//中序遍历
public static void MiddleVisit(Node root){
if(root==null){
return;
}
MiddleVisit(root.left);
System.out.print(root.data+" ,");
MiddleVisit(root.right);
}
//先序遍历
public static void PreVisit(Node root){
if(root==null){
return ;
}
System.out.print(root.data+" ,");
PreVisit(root.left);
PreVisit(root.right);
}
//后序遍历
public static void latterVisit(Node root){
if(root==null){
return;
}
latterVisit(root.left);
latterVisit(root.right);
System.out.print(root.data+" ,");
}
//删除二叉树上的某个节点
public static void deleteNode(Node root,int data){
if(root==null){
return;
}
Node preNode=null;
Node curNode=root;
while(curNode!=null){
if(data<curNode.data){
preNode=curNode;
curNode=curNode.left;
}else if(data>curNode.data){
preNode=curNode;
curNode=curNode.right;
}else if(curNode.data==data){
if(curNode.left==null&&curNode.right!=null){
if(preNode.left!=null&&preNode.left.data==curNode.data){
preNode.left=curNode.right;
}else if(preNode.right!=null&&preNode.right.data==curNode.data){
preNode.right=curNode.right;
}
}else if(curNode.left!=null&&curNode.right==null){
if(preNode.left!=null&&preNode.left.data==curNode.data){
preNode.left=curNode.left;
}else if(preNode.right!=null&&preNode.right.data==curNode.data){
preNode.right=curNode.left;
}
} else if(curNode.left!=null&&curNode.right!=null){
Node curLeftMinNode=findMin(curNode);
deleteNode(curNode, curLeftMinNode.data);
curNode.data=curLeftMinNode.data;
}else if(curNode.left==null&&curNode.right==null){
if(preNode.left!=null&&preNode.left.data==curNode.data){
preNode.left=null;
}else if(preNode.right!=null&&preNode.right.data==curNode.data){
preNode.right=null;
}
}
return ;
}
}
}
//根据元素查找节点
public static Node findNode(Node root,int data){
if(root==null){
return null;
}
Node temp=root;
while(temp!=null){
if(data<temp.data){
temp=temp.left;
}else if(data>temp.data){
temp=temp.right;
}else if(temp.data==data){
return temp;
}
}
return null;
}
//插入节点
public static Node insertNode(Node root ,int data){
//递归实现
//
// if(root==null){
// root=new Node(data,null,null);
// }else {
//
// if(data<root.data){
// root.left=insertNode(root.left, data);
// }else{
// root.right=insertNode(root.right, data);
// }
// }
if(root==null){
root=new Node(data,null,null);
}else{
Node n=new Node(data,null,null);
Node temp=root;
while(temp!=null){
if(temp.data>data){
if(temp.left==null){
temp.left=n;
break;
}
temp=temp.left;
}else{
if(temp.right==null){
temp.right=n;
break;
}
temp=temp.right;
}
}
}
return root;
}
//查找最大值
public static Node findMax(Node root){
if(root==null){
return null;
}
Node result=null;
result=root;
while(result.right!=null){
result=result.right;
}
return result;
}
//查找最小值
public static Node findMin(Node root){
if(root==null){
return null;
}
Node result=null;
result=root;
while(result.left!=null){
result=result.left;
}
return result;
}
}