[Java知识库]Java实现二叉搜索树的基本功能

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication24;
import java.util.Scanner;
/**
 *
 * @author 86188
 */
class Node {
    Node left;
    private int data;
    Node right;
    public Node(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}
public class BinaryTree {
    public static Node deleteNode(Node root, int key) {
    	if(root==null)	return null;
    	if(root.getData()>key) {
    		root.left=deleteNode(root.left,key);	
    	}
    	else if(root.getData()<key) {
    		root.right=deleteNode(root.right,key);
    	}
    	else {										
    		if(root.left==null) return root.right;	
    		if(root.right==null) return root.left;	
    		Node t=Find(root.right);			
    		root.setData(t.getData());							
    		root.right=deleteNode(root.right,t.getData());
    		
    	}
    	return root;
	}

	private static Node Find(Node root) {
		while(root.left!=null) {		
			root=root.left;				
		}
		return root;					
	}
    public static void insert(Node root, int value) {
        if (root.getData() == 0) {
            root.setData(value);
        } else if (root.getData() < value) {
            if (root.getRight() != null) {
                insert(root.getRight(), value);
            } else {
                Node newNode = new Node(0);
                newNode = null;
                root.setRight(newNode);
                insert(root.getRight(), value);
            }
        } else if (root.getData() > value) {
            if (root.getLeft() != null) {
                insert(root.getLeft(), value);
            } else {
                Node newNode = new Node(0);
                root.setLeft(newNode);
                insert(root.getLeft(), value);
            }
        }
    }

    public static Node findNode(Node root, int data) {
        if (root.getData() == data) {
            return root;
        } else if (root.getData() < data) {
            if (root.getRight() != null) {
                return findNode(root.getRight(), data);
            } else {
                return null;
            }
        } else if (root.getData() > data) {
            if (root.getLeft() != null) {
                return findNode(root.getLeft(), data);
            } else {
                return null;
            }
        }
        return null;
    }

    private static void prevOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.getData() + ",");
        prevOrder(root.getLeft());
        prevOrder(root.getRight());
    }

    private static void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.getLeft());
        System.out.print(root.getData() + ",");
        inOrder(root.getRight());
    }

    private static void postOrder(Node root) {
        if (root == null) {
            return;
        }
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.print(root.getData() + ",");
    }
    //根结点,默认为null
    public Node root = null;

    public Node getRoot() {
        return root;
    }

    private void buildBiTree(Node node, int data) {
        if (root == null) {
            root = new Node(data);
        } else {
            if (data < node.getData()) {
       
                if (node.getLeft() == null) {
                 
                    node.setLeft(new Node(data));
                } else {
                
                    buildBiTree(node.getLeft(), data);
                }
            } else {
                
                if (node.getRight() == null) {
                
                    node.setRight(new Node(data));
                } else {
       
                    buildBiTree(node.getRight(), data);
                }
            }
        }
    }

    public static BinaryTree createBiTree(int[] datas) {
        BinaryTree binaryTree = new BinaryTree();
        for (int data : datas) {
            binaryTree.buildBiTree(binaryTree.getRoot(), data);
        }
        return binaryTree;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);//构建一棵树
        System.out.println("请输入一棵树的各个结点值,并用逗号隔开");
        String str = in.next().toString();//将一行字符串转换成数字
        String[] arr = str.split(",");
        int[] a = new int[arr.length];
        for (int j = 0; j < a.length; j++) {
            a[j] = Integer.parseInt(arr[j]);
        }
        
        BinaryTree biTree = BinaryTree.createBiTree(a);//创建一棵树并用三种方式遍历
        System.out.print("先序遍历");
        BinaryTree.prevOrder(biTree.root);
        System.out.print("\n中序遍历");
        BinaryTree.inOrder(biTree.root);
        System.out.print("\n后序遍历");
        
        BinaryTree.postOrder(biTree.root);//查找树中的一个数值
        System.out.println();
        System.out.print("请输入一个需要查找的值data:");
        int data = in.nextInt();
        System.out.println(findNode(biTree.root, data).getData());
        
        System.out.print("请输入需要插入的一个数:");//在构建好的树中插入一个值
        int data2 = in.nextInt();
        insert(biTree.root, data2);
        System.out.print("先序遍历");
        BinaryTree.prevOrder(biTree.root);
        System.out.println();
        
        System.out.print("请输入需要删除的一个数:");//在构建好的树中删除一个值
        int data3=in.nextInt();
        deleteNode(biTree.root,data3);
        System.out.print("先序遍历");
        BinaryTree.prevOrder(biTree.root);
    }
}