``` 节点类 public class Node { public Node left; public Node right; public int data; public Node(int data){ this.left = null; this.right = null; this.data = data; } } 二叉树类 实现了二叉树插入、删除、查找、前序遍历、中序遍历、后序遍历、层序遍历、二叉树序列化和反序列化 import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class BinaryTree { public Node root; public BinaryTree() { this.root=null; } /** * 二叉树的常见操作 * 增加、删除、查找 */ public void insert(int data){ Node node=new Node(data); if(this.root==null){ this.root=node; }else{ Node current=this.root; Node parent; while(true){ parent=current; if(data<current.data){ current=current.left; if(current==null){ parent.left=node; break; } }else{ current=current.right; if(current==null){ parent.right=node; break; } } } } } public Node find(int data){ Node current=this.root; while(current!=null){ if(current.data==data){ return current; } else if(data<current.data){ current=current.left; }else{ current=current.right; } } return null; } public void remove(int data){ root=removeNode(this.root,data); } public Node removeNode(Node node,int data){ if(node==null){ return null; } if(data==node.data){ if(node.left==null&&node.right==null){ return null; } if(node.left==null){ return node.right; } if(node.right==null){ return node.left; } Node tempNode=getSmallest(node.right); node.data=tempNode.data; node.right=removeNode(node.right,tempNode.data); return node; }else if(data<node.data){ node.left=removeNode(node.left,data); return node; }else{ node.right=removeNode(node.right,data); return node; } } public Node getSmallest(Node node) { if(node.left==null){ return node; }else{ return getSmallest(node.left); } } /** * 先序、中序、后序、层序遍历 */ public void preOrderCur(Node head){ if(head==null){ return; } System.out.println(head.data+" "); preOrder(head.left); preOrder(head.right); } public void preOrder(Node head){ if(head!=null){ Stack<Node> stack=new Stack<Node>(); stack.add(head); while(!stack.isEmpty()){ head=stack.pop(); System.out.println(head.data+" "); if(head.right!=null){ stack.push(head.right); } if(head.left!=null){ stack.push(head.left); } } } } public void inOrderCur(Node head){ if(head==null){ return ; } preOrder(head.left); System.out.println(head.data+" "); preOrder(head.right); } public void inOrder(Node head){ if(head!=null){ Stack<Node> stack=new Stack<Node>(); while(!stack.isEmpty()||head!=null){ if(head!=null){ stack.push(head); head=head.left; }else{ head=stack.pop(); System.out.println(head.data+" "); head=head.right; } } } } public void posOrderCur(Node head){ if(head==null){ return; } preOrder(head.left); preOrder(head.right); System.out.println(head.data+" "); } public void posOrder(Node head){ if(head!=null){ Stack<Node> stack=new Stack<Node>(); stack.push(head); Node c=null; while(!stack.isEmpty()){ c=stack.peek(); if(c.left!=null&&head!=c.left&&head!=c.right){ stack.push(c.left); }else if(c.right!=null &&head!=c.right){ stack.push(c.right); }else{ System.out.println(stack.pop().data+" "); head=c; } } } } public void levelOrder(Node head){ if(head==null){ return; } Queue<Node> queue=new LinkedList<Node>(); queue.offer(head); while(!queue.isEmpty()){ head=queue.poll(); System.out.println(head.data); if(head.left!=null){ queue.offer(head.left); } if(head.right!=null){ queue.offer(head.right); } } } /** * 序列化二叉树 * 先序、层序序列化和反序列化 */ public String serialPre(Node head){ if(head==null){ return "#!"; } String str=head.data+"!"; str+=serialPre(head.left); str+=serialPre(head.right); return str; } /*先序反序列化*/ public Node recoByPre(String preStr){ String[] values=preStr.split("!"); Queue<String> queue=new LinkedList<String>(); for(int i=0;i!=values.length;i++){ queue.offer(values[i]); } return reconPreOrder(queue); } public Node reconPreOrder(Queue<String> queue){ String value=queue.poll(); if(value.equals("#")){ return null; } Node head=new Node(Integer.valueOf(value)); head.left=reconPreOrder(queue); head.right=reconPreOrder(queue); return head; } /*层序序列化*/ public String serialLevel(Node head){ if(head==null){ return "#!"; } String res=head.data+"!"; Queue<Node> queue=new LinkedList<Node>(); queue.offer(head); while(!queue.isEmpty()){ head=queue.poll(); if(head.left!=null){ res+=head.left.data+"!"; queue.offer(head.left); }else{ res+="#!"; } if(head.right!=null){ res+=head.right.data+"!"; queue.offer(head.right); }else{ res+="#"; } } return res; } /*层序反序列化*/ public Node reconLevel(String str){ String[] values=str.split("!"); int index=0; Node head=createNode(values[index++]); Queue<Node> queue=new LinkedList<Node>(); if(head!=null){ queue.offer(head); } Node node=null; while(!queue.isEmpty()){ node=queue.poll(); node.left=createNode(values[index++]); node.right=createNode(values[index++]); if(node.left!=null){ queue.offer(node.left); } if(node.right!=null){ queue.offer(node.right); } } return head; } public Node createNode(String val){ if(val.equals("#")){ return null; } return new Node(Integer.valueOf(val)); } } 数据测试 public class test { public static void main(String[] args) { BinaryTree binTree=new BinaryTree(); //建立一棵二叉树 int[] data={25,15,10,5,36,65,52,45,42}; for(int i=0;i<data.length;i++){ binTree.insert(data[i]); } binTree.remove(42); binTree.preOrder(binTree.root); String a=binTree.serialPre(binTree.root); System.out.println(a); } } 参考资料 《IT名企算法与数据结构题目最优解》左程云 ```