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

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)了二叉樹插入、刪除、查找、前序遍歷、中序遍歷、后序遍歷、層序遍歷、二叉樹序列化和反序列化

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


數(shù)據(jù)測(cè)試
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名企算法與數(shù)據(jù)結(jié)構(gòu)題目最優(yōu)解》左程云