摘要：節(jié)點(diǎn)類二叉樹(shù)類實(shí)現(xiàn)了二叉樹(shù)插入刪除查找前序遍歷中序遍歷后序遍歷層序遍歷二叉樹(shù)序列化和反序列化二叉樹(shù)的常見(jiàn)操作增加刪除查找先序中序后序?qū)有虮闅v序列化二叉樹(shù)先序?qū)有蛐蛄谢头葱蛄谢刃蚍葱蛄谢瘜有蛐蛄谢瘜有蚍葱蛄谢瘮?shù)據(jù)測(cè)試建立一棵二叉樹(shù)參考資料

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;  
            }  
}

實(shí)現(xiàn)了二叉樹(shù)插入、刪除、查找、前序遍歷、中序遍歷、后序遍歷、層序遍歷、二叉樹(shù)序列化和反序列化

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {

    public Node root;
    public BinaryTree() {
        this.root=null;
    }
    /**
     * 二叉樹(shù)的常見(jiàn)操作
     * 增加、刪除、查找
     */
    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);
            }
        }
    }
/**
 * 序列化二叉樹(shù)
 * 先序、層序序列化和反序列化
 */
    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));
    }
}


數(shù)據(jù)測(cè)試
public class test {
    public static void main(String[] args) {
        BinaryTree binTree=new BinaryTree();
        //建立一棵二叉樹(shù)
        int[] data={25,15,10,5,36,65,52,45,42};
        for(int i=0;i
參考資料
《IT名企算法與數(shù)據(jù)結(jié)構(gòu)題目最優(yōu)解》左程云