二叉树的一些常见的操作

摘要：节点类二叉树类实现了二叉树插入删除查找前序遍历中序遍历后序遍历层序遍历二叉树序列化和反序列化二叉树的常见操作增加删除查找先序中序后序层序遍历序列化二叉树先序层序序列化和反序列化先序反序列化层序序列化层序反序列化数据测试建立一棵二叉树参考资料

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
    /**
     * 先序、中序、后序、层序遍历
     */
    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 stack=new Stack();
            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 stack=new Stack();
            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 stack=new Stack();
            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 queue=new LinkedList();
        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 queue=new LinkedList();
        for(int i=0;i!=values.length;i++){
            queue.offer(values[i]);
        }
        return reconPreOrder(queue);
    }
    public Node reconPreOrder(Queue 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 queue=new LinkedList();
        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 queue=new LinkedList();
        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
参考资料
《IT名企算法与数据结构题目最优解》左程云