データ構造:ツリーのapi設計とjavaコード実装

二叉木の基本的な概念について
ツリー:ツリーは度が2を超えないツリーです(ノードごとに最大2つのサブノードがあります)
フルツリー:各レイヤのノード数が最大値に達すると、このツリーはフルツリーになります.
完全二叉樹:葉の結点は最下層とこの下層にしか現れず、最下層の結点はその層の最も左側のいくつかの位置に集中している二叉樹、すなわち木が不満であれば左満右が不満であり、完全二叉樹である
 
二叉木の結点の特性を解析した後,二叉木の結点クラスを容易に設計した.

 private class Node {
        private K key;// 
        private V value;// 
        private Node left;//    
        private Node right;//    

        public Node(K key,V value,Node left,Node right){
           this.key=key;
           this.value=value;
           this.left=left;
           this.right=right;
        }

    }

次に,二叉ルックアップツリーのAPI設計を解析する.
類名:BinaryTree,V value>メンバー変数:private Node rootレコードルートノードprivate int Nレコードツリーの要素個数メンバーメソッド:public void put(K key,V value)ツリーにキー値対private Node put(Node,K key,V value)を挿入ツリーに指定したノードにキー値対public V get(K key)を挿入ツリーのキー対応値private V get(Node,K key,K key)を検索ツリーで指定したノードxからキー対応値public void delete(K key)キー値対private Node delete(Node x,K key)キー削除ツリーで指定したノードのキー値対public int size()ツリーの要素数を取得する
BinaryTree完全javaコード実装

package com.tingcream.alg.tree;


import com.tingcream.alg.linear.Queue;

/**
 *       ，  
 * 1、            (    、    )
 * 2、               ，               
 *
 * BinaryTree
 *
 */
public class BinaryTree,V> {
    private Node root;//       
    private int N;//        


    //    
    public int size(){
        return this.N;
    }

    public boolean isEmpty(){
        return this.N<=0;
    }

    //   put    key-value
    public void put(K key, V value){
        //     put  
        root=put(root,key,value);
    }

    //      x   kv,      x  
    public Node put(Node x,K key, V value){
        //  x  ， new           
        if(x==null){
            N++;
            return new Node(key,value,null,null);
        }
        //  x   
        //   x     key   
        //  key   x    ,    x      
        //  key   x    ,    x      
        //  key  x     ，   x     value
        int cmp=key.compareTo(x.key);
        if(cmp>0){
            x.right= put(x.right,key,value);

        }else if(cmp<0){
            x.left=put(x.left,key,value);
        }else{//key     x    ，   x   value 
            x.value=value;
        }
        return x;

    }




    //      key   value
    public  V get(K key){
        return  get(root,key);
    }

    //      x ，  key    
    public V get(Node x,K key){
        //    x null
        if(x==null){
            return null ;
        }
        int cmp=key.compareTo(x.key);
        if(cmp>0){
           //   key   x    ,    x      
            return  get(x.right,key);
        }else if(cmp<0){
            //  key   x    ,    x      
            return  get(x.left,key);
        }else{
            //  key  x     ，      key   ，       value  
            return  x.value;
        }
    }




    //    key     
    public void delete(K key){
       delete(root,key);
    }

    //      x  key     ，         x
    public Node delete(Node x,K key){
        //x  null
        if(x==null){
            return null;
        }
        //x   null
        int cmp=key.compareTo(x.key);
        if(cmp>0){
            //   key   x    ,    x      
            x.right=delete(x.right,key);
        }else if(cmp<0){
            //  key   x    ,    x      
            x.left=delete(x.left,key);
        }else{

            //  key  x    ，            x

            //      
            N--;

            //  x      ,         
            if(x.right==null){
                return x.left;
            }

            //x     ，       ，      
            if(x.left==null ){
                return x.right;
            }


            //  x            

            //           
            if(x.right.left==null){
                x.right.left=x.left;
                x=x.right;
               return x;
            }else{
                Node minNode= x.right;
                while(minNode.left!=null){
                    minNode= minNode.left;
                }

                //           
                Node n=x.right;
                while(n.left!=null){
                    if(n.left.left==null){
                        n.left=null; //            ，  left  
                    }else{
                        n=n.left;
                    }
                }


                //  x minNode  
                //            // x        minNode    
//            // x        minNode    
//                minNode.left=x.left;
//                minNode.right=x.right;
//                // x         minNode
//                x=minNode;

                //x    ， minNode    key、value  x    key、value
                x.key=minNode.key;
                x.value=minNode.value;

            }

        }

        return x;
    }





    //             
    public K  min(){
        if(root==null){
            return null;
        }
        return min(root).key;
    }
    //         
    private Node min(Node x){
        //     ：while  
        Node n=x;
        while(n.left!=null){
            n=n.left;
        }
        return n;

    }



    //             
    public K  max(){
        if(size()>0){
            return null;
        }
        return max(root).key;
    }

    //         
    private Node max(Node x){
        //     ：while  
        Node n=x;
        while(n.right!=null){
            n=n.right;
        }
        return n;
    }


    //      ，           
    public Queue preErgodic(){
        Queue keys= new Queue();//new     keys
        preErgodic(root,keys);
        return keys;
    }

    //      ，    x        keys   
    private  void preErgodic(Node x,Queue keys){
        //  x   ，   return （     ）
        if(x==null){
            return;
        }
        // x   key   keys 
        //    x      
        //    x      

        // x       
        keys.enqueue(x.key);

        //  x     ，          
        if(x.left!=null){
            preErgodic(x.left,keys);
        }

        //  x     ，          
        if(x.right!=null){
            preErgodic(x.right,keys);
        }
    }




    //      ，           
    public Queue midErgodic(){
        Queue keys= new Queue();//new     keys
        midErgodic(root,keys);
        return keys;
    }

    //      ，    x        keys   
    private  void   midErgodic(Node x,Queue keys){
        //  x   ，   return （     ）
        if(x==null){
            return;
        }
        // x   key   keys 
        //    x      
        //    x      

        //  x     ，          
        if(x.left!=null){
            midErgodic(x.left,keys);
        }

        // x       
        keys.enqueue(x.key);

        //  x     ，          
        if(x.right!=null){
            midErgodic(x.right,keys);
        }
    }




    //      ，           
    public Queue afterErgodic(){
        Queue keys= new Queue();//new     keys
        afterErgodic(root,keys);
        return keys;
    }

    //      ，    x        keys   
    private  void   afterErgodic(Node x,Queue keys){
        //  x   ，   return （     ）
        if(x==null){
            return;
        }
        // x   key   keys 
        //    x      
        //    x      

        //  x     ，          
        if(x.left!=null){
            afterErgodic(x.left,keys);
        }

        //  x     ，          
        if(x.right!=null){
            afterErgodic(x.right,keys);
        }

        // x       
        keys.enqueue(x.key);
    }

    //    ，       key      （     ）
    public Queue  layerErgodic(){
        if(isEmpty()){
            return null;
        }

        //      ，       key      
        Queue keys=new Queue();//    keys   
        Queue nodes=new Queue();//    

        //  root    nodes  
        nodes.enqueue(root);
        while(!nodes.isEmpty()){

            //      ，   key  keys  
            Node n= nodes.dequeue();
            keys.enqueue(n.key);

            //               ，            
            if(n.left!=null){
                nodes.enqueue(n.left);
            }
            //               ，            
            if(n.right!=null){
                nodes.enqueue(n.right);
            }
        }

        return  keys;
    }



    //         
    public int maxDepth(){
        if(isEmpty()){
           return 0;
        }
        return  maxDepth(root);

    }
    //          
    private int maxDepth(Node x){
        if(x==null){
            return 0;
        }

        //  x           
        //  x           
        //  x               ，    +1   

        int max=0;//x     
        int maxL=0;//x         
        int maxR=0;//x         

        if(x.left!=null){
            maxL=  maxDepth(x.left);
        }
        if(x.right!=null){
            maxR= maxDepth(x.right);
        }
        max=(maxL>maxR)?maxL+1:maxR+1;

        return max;
    }

    //   Node     
    private class Node {
        private K key;// 
        private V value;// 
        private Node left;//    
        private Node right;//    

        public Node(K key,V value,Node left,Node right){
           this.key=key;
           this.value=value;
           this.left=left;
           this.right=right;
        }

    }
}

二叉樹前序遍歴:まずルートノードを遍歴し、次に左サブツリーを遍歴し、最後に右サブツリー二叉樹中序遍歴:まず左サブツリーを遍歴し、次にルートノードを遍歴し、最後に右サブツリー二叉樹後序遍歴:まず左サブツリーを遍歴し、次に右サブツリーを遍歴し、最後にルートノードを遍歴する
二叉木の層順遍歴(広さ優先):最上位(root)から最下層まで、1層1層が順次遍歴し、同じ層の要素が左から右に遍歴する.