/**
* 使用樹形結(jié)構(gòu)--二叉樹實現(xiàn)排序
* 二叉樹為結(jié)點的度最大為2的樹，每個結(jié)點最多有兩個子結(jié)點
* 二叉排序樹的定義：1.根結(jié)點的左子樹的值小于根結(jié)點 2.根結(jié)點的右子樹的值大于根結(jié)點 3.左右子樹也各為一顆二叉排序樹
* 二叉排序樹的中序遍歷的結(jié)果為一個有序的集合
*/
public class SortByBinaryTree<E extends Integer> {
? ?//模擬二叉排序樹 ? 對Integer類型進行排序
? ?private static final class Node<E extends Integer>{
? ? ? ?//泛型類定義E小于等于Integer 類內(nèi)使用E不再聲明extends
? ? ? ?E item;
? ? ? ?//存放元素
? ? ? ?Node<E> left;
? ? ? ?//左子樹
? ? ? ?Node<E> right;
? ? ? ?//右子樹
? ? ? ?public Node(E item, Node<E> left, Node<E> right) {
? ? ? ? ? ?this.item = item;
? ? ? ? ? ?this.left = left;
? ? ? ? ? ?this.right = right;
? ? ? ?}
? ?}

? ?Node<E> root;
? ?//類中僅記錄根結(jié)點，每次操作通過根結(jié)點遞進向下調(diào)用
? ?public void add(E e){
? ? ? ?if (e==null)return;
? ? ? ?//返回類型void的方法內(nèi)return不加參數(shù)會結(jié)束方法
? ? ? ?if (root==null){
? ? ? ? ? ?root = new Node<>(e,null,null);
? ? ? ?}else {
? ? ? ? ? ?Node<E> n = getParentNode(e);
? ? ? ? ? ?if (n==null)return;
? ? ? ? ? ?if (e.intValue() < n.item.intValue()) {
? ? ? ? ? ? ? ?//E extends Integer 所以可以使用.intValue()
? ? ? ? ? ? ? ?n.left = new Node<>(e, null, null);
? ? ? ? ? ?} else {
? ? ? ? ? ? ? ?n.right = new Node<>(e, null, null);
? ? ? ? ? ?}
? ? ? ?}
? ?}
? ?private Node<E> getParentNode(E e){
? ? ? ?int eInt = e.intValue();
? ? ? ?int nInt;
? ? ? ?for (Node<E> n = root;eInt != (nInt=n.item.intValue());){
? ? ? ? ? ?//在判定條件中賦值
? ? ? ? ? ?if (eInt < nInt){
? ? ? ? ? ? ? ?if (n.left==null){
? ? ? ? ? ? ? ? ? ?return n;
? ? ? ? ? ? ? ?}else {
? ? ? ? ? ? ? ? ? ?n=n.left;
? ? ? ? ? ? ? ?}
? ? ? ? ? ?} else {
? ? ? ? ? ? ? ?if (n.right==null){
? ? ? ? ? ? ? ? ? ?return n;
? ? ? ? ? ? ? ?}else {
? ? ? ? ? ? ? ? ? ?n=n.right;
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return null;
? ? ? ?//重復(fù)元素不添加
? ?}

? ?public void traversal(){
? ? ? ?//遍歷traversal
? ? ? ?if (root==null){
? ? ? ? ? ?System.out.println("當前無元素");
? ? ? ? ? ?return;
? ? ? ?}
? ? ? ?traversal(root);
? ?}
? ?private void traversal(Node<E> n){
? ? ? ?if (n!=null){
? ? ? ? ? ?traversal(n.left);
? ? ? ? ? ?System.out.print(n.item+", ");
? ? ? ? ? ?traversal(n.right);
? ? ? ?}
? ?}

? ?public static void main(String[] args) {
? ? ? ?Random r = new Random();
? ? ? ?Integer[] arr = new Integer[10];
? ? ? ?for (int i = 0;i<10;i++){
? ? ? ? ? ?arr[i] = r.nextInt(40);
? ? ? ?}
? ? ? ?SortByBinaryTree<Integer> sort = new SortByBinaryTree<>();
? ? ? ?for (Integer i:arr){
? ? ? ? ? ?sort.add(i);
? ? ? ?}
? ? ? ?System.out.println(Arrays.toString(arr));
? ? ? ?//打印原數(shù)組，結(jié)果為[28, 3, 14, 36, 12, 25, 15, 5, 37, 22]
? ? ? ?sort.traversal();
? ? ? ?//排序結(jié)果為3,5,12,14,15,22,25,28,36,37,
? ?}
}