Javaは二叉ソートツリーの挿入クエリーと遍歴を実現する

ツリーの非再帰挿入、非再帰クエリー、最大値の検索、最小値の検索

package whut.tree;
//           ，     ，     ，     
class Node {
    private int data;
    private Node left;
    private Node right;
    public Node(int data) {
        this.data = data;
    }
    public int getData() {
        return data;
    }
    public Node getLeft() {
        return left;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public Node getRight() {
        return right;
    }
    public void setRight(Node right) {
        this.right = right;
    }
    //       
    public void displayNode() {
        System.out.println(" " + data + " ");
    }
}
//  
public class BinaryTree {
    private Node root;//   
    //              ，
    public void insert(int data) {
        Node newNode = new Node(data);
        if (root == null) {
            root = newNode;
        } else {
            //    ，    
            Node current = root;
            //    
            Node parent;
            while (true)//        
            {
                parent = current;
                //       ，     
                if (data < current.getData()) {
                    current = current.getLeft();
                    //     
                    if (current == null) {
                        parent.setLeft(newNode);
                        return;
                    }
                } else {
                    current = current.getRight();
                    if (current == null) {
                        parent.setRight(newNode);
                        return;
                    }
                }
            }
        }
    }
    //          
    public Node find(int data) {
        Node current = root;
        while (current.getData() != data) {
            if (current.getData() < data)
                current = current.getLeft();
            else
                current = current.getRight();
            //              ，   null 
            if (current == null)
                return null;
        }
        //               
        return current;
    }
    //          ,       ，       null
    public Node findMinNode() {
        Node current;
        Node parent;
        //
        if (root == null) {
            return null;
        } else {
            parent = root;
            current = parent.getLeft();
            while (current != null) {
                parent = current;
                current = current.getLeft();
            }
            return parent;
        }
    }
    //            ，         
    public Node findMaxNode() {
        Node current;
        Node parent;
        //
        if (root == null) {
            return null;
        } else {
            parent = root;
            current = parent.getRight();
            while (current != null) {
                parent = current;
                current = current.getRight();
            }
            return parent;
        }
    }
    //       ，                
    //         ，    ，        ，        
    public boolean delete(int key) {
        Node current = root;
        Node parent = root;
        //                      
        boolean isLeftChild = false;
        //   ， current.iData == key  ，current         
        //       parent       
        while (current.getData() != key) {
            parent = current;
            if (key < current.getData()) {
                isLeftChild = true;
                current = current.getLeft();
            } else {
                isLeftChild = false;
                current = current.getRight();
            }
            if (current == null)//    key   false
                return false;
        }
        //            
        if (current.getLeft() == null && current.getRight() == null) {
            if (current == root)
                root = null;
            else if (isLeftChild)
                parent.setLeft(null);
            else
                parent.setRight(null);
        }
        //                  
        //               
        //                     
        else if (current.getRight() == null) {
            if (current == root)//           
                root = current.getLeft();
            else if (isLeftChild)//              
                parent.setLeft(current.getLeft());
            else
                parent.setRight(current.getLeft());//              
        }
        //                  
        //               
        //                     
        else if (current.getLeft() == null) {
            if (current == root)//           
                root = current.getRight();
            else if (isLeftChild)//              
                parent.setLeft(current.getRight());
            else
                parent.setRight(current.getRight());//              
        }
        //                  
        else
         {
            //               ，current
             Node successor = getSuccessor(current);
             if(current == root)
                root = successor ;
             //                    
             else if(isLeftChild)
                    parent.setLeft(successor);
             else
                    parent.setRight(successor);
             successor.setLeft(current.getLeft());
         }
        return true;
    }
    //       ，                     
    //       ,                             。
    //                        ，                  
    private Node getSuccessor(Node delNode)
    {
        //         
        Node successorParent = delNode;
        //     
        Node successor = delNode.getRight();
        //            
        Node current = successor.getLeft();
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.getLeft();
        }
        //                       
        if (successor != delNode.getRight())
        {
            successorParent.setLeft(successor.getRight());
            //           
            successor.setRight(delNode.getRight());
        }
        return successor;
    }
    //        
    //              
    //     
    public void preOrder(Node localRoot) {
        if (localRoot != null) {
            localRoot.displayNode();//       
            preOrder(localRoot.getLeft());//           
            preOrder(localRoot.getRight());//           
        }
    }
    //     
    public void midOrder(Node localRoot) {
        if (localRoot != null) {
            preOrder(localRoot.getLeft());//           
            localRoot.displayNode();//       
            preOrder(localRoot.getRight());//           
        }
    }
    //     
    public void lastOrder(Node localRoot) {
        if (localRoot != null) {
            preOrder(localRoot.getLeft());//           
            preOrder(localRoot.getRight());//           
            localRoot.displayNode();//       
        }
    }
}

ツリーの再帰的挿入、再帰的遍歴、再帰的クエリー

package whut.tree;
//      ，            ,    
public class NodeTree {
    public int value;
    public NodeTree left;
    public NodeTree right;
    //      
    public void store(int value) {
        if (value < this.value) {
            if (left == null) {
                left = new NodeTree();
                left.value = value;
            } else {
                left.store(value);
            }
        } else if (value > this.value) {
            if (right == null)
            {
                right = new NodeTree();
                right.value = value;
            } else {
                right.store(value);
            }
        }
    }
    public boolean find(int value) {
        System.out.println("find happen " + this.value);
        if (value == this.value) {
            return true;
        } else if (value > this.value) {
            if (right == null)
                return false;
            return right.find(value);
        } else {
            if (left == null)
                return false;
            return left.find(value);
        }
    }
    //    
    public void preList() {
        System.out.print(this.value + ",");
        if (left != null)
            left.preList();
        if (right != null)
            right.preList();
    }
            
    //    
    public void middleList() {
        if (left != null)
            left.middleList();
        System.out.print(this.value + ",");
        if (right != null)
            right.middleList();
    }
     //    
    public void afterList() {
        if (left != null)
            left.afterList();
        if (right != null)
            right.afterList();
        System.out.print(this.value + ",");
    }
    public static void main(String[] args) {
        int[] data = new int[20];
        for (int i = 0; i < data.length; i++) {
            data[i] = (int) (Math.random() * 100) + 1;
            System.out.print(data[i] + ",");
        }
        System.out.println();
        NodeTree root = new NodeTree();
        root.value = data[0];
        for (int i = 1; i < data.length; i++) {
            root.store(data[i]);
        }
        //  
        root.find(data[19]);
        //  
        root.preList();
        System.out.println();
        //  
        root.middleList();
        System.out.println();
        //  
        root.afterList();
    }
}