脚本宝典收集整理的这篇文章主要介绍了二叉树的一些常见的操作，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
节点类
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名企算法与数据结构题目最优解》左程云
以上是脚本宝典为你收集整理的二叉树的一些常见的操作全部内容，希望文章能够帮你解决二叉树的一些常见的操作所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。