package j2se;

import java.util.ArrayList;
import java.util.List;

import charactor.Hero;

//自定义二叉树
public class MyTree<E> {
	public Node<E> root;
	private List<NodePair> pairs;

	public void add(E e) {
		if (root == null) {
			root = new Node<E>(e, 0);
		} else
			root.add(e, 1);

	}

	public void add(List<Hero> heros) {
		for (Hero hero : heros) {
			add(hero.hp, hero);
		}
	}

	public void add(Float key, Object obj) {
		if (root == null) {
			root = new Node<>(key, obj, 0);
		} else
			root.add(key, obj, 1);
	}

	public void add(E key, Object obj) {
		if (root == null) {
			root = new Node<E>(key, obj, 0);
		} else
			root.add(key, obj, 1);
	}

	public void add(E[] arr) {
		for (E e : arr) {
			add(e);
		}
	}

	public void print() {
		pairs = new ArrayList<NodePair>();
		print("Root", root, "\r\n", pairs);
		showList();
	}

	public void showList() {
		// Collections.sort(pairs,Comparator.comparingInt(p->p.Dimension));
		int[] count = new int[] { 0 };
		int Dimension = getDiemension(root, new int[] { 0 }, count);
		int margin = (int) ((Dimension - root.Dimension) * 1);
		String emString = "";
		for (int j = 0; j < margin; j++) {
			emString += " ";
		}
		int margin2 = margin * 3;
		String emString2 = "";
		for (int j = 0; j < margin2; j++) {
			emString2 += " ";
		}
		System.out.print(String.format("共%d个有效非空节点，%d层", count[0], Dimension + 1));
		System.out.print("树状图如下：\r\n");
		System.out.print(String.format("%s%.0f%n", emString2, root.Key));
		for (int i = 1; i <= Dimension; i++) {
			for (NodePair np : pairs) {
				if (np.Dimension != i)
					continue;
				margin = (int) ((Dimension - np.Dimension) * 1);
				if (i == 1)
					margin += 1;
				emString = " ";
				for (int j = 0; j < margin; j++) {
					emString += " ";
				}
				margin2 = (int) ((Dimension - np.Dimension) * 1) * 3;
				emString2 = " ";
				for (int j = 0; j < margin2; j++) {
					emString2 += " ";
				}

				String L = "□";
				String R = "□";
				if (np.L == 0 || np.L > Double.MIN_VALUE + 1e-12 && !np.IsNull)
					L = String.valueOf((Math.round(np.L * 100) / 100f));
				if (np.L == 0 || np.R > Double.MIN_VALUE + 1e-12 && !np.IsNull)
					R = String.valueOf((Math.round(np.R * 100) / 100f));
				if (np.IsNull) {

					np.R = np.L = Double.MIN_VALUE;
					L = "□";
					R = "□";
				}
				if (!(np.L == np.R && np.L <= Double.MIN_VALUE) && np.L != 0)
					System.out.print(String.format("%s%s %s%s%s", emString, L, emString2, R, emString));
			}
			System.out.println();
		}

	}

	public void print(String str1, Node<E> n, String str2, List<NodePair> nps) {
		if (n == null) {
			nps.add(new NodePair(n == null, nps.get(nps.size() - 1).Dimension + 1, 0, 0));
			return;
		}
		nps.add(new NodePair(n == null, n.Dimension + 1, n.Left == null ? Double.MIN_VALUE : n.Left.Key,
				n.Right == null ? Double.MIN_VALUE : n.Right.Key));
		System.out.print(String.format("第%d层：", n.Dimension));
		if (n.Obj != null)
			if (n.Obj instanceof Hero)
				System.out.print(String.format("object：%s;", (Hero) n.Obj));
		System.out.println(String.format("%s.value:%.2f%s", str1, n.Key, str2));
		String left = str1 + ".Left";
		print(left, n.Left, "", nps);
		String right = str1 + ".Right";
		print(right, n.Right, "", nps);

	}

	public int getDiemension(Node<E> node, int[] d, int[] c) {
		if (node == null)
			return d[0];
		c[0]++;
		d[0] = Math.max(node.Dimension, d[0]);
		if (node.Left != null)
			getDiemension(node.Left, d, c);
		if (node.Right != null)
			getDiemension(node.Right, d, c);
		return d[0];
	}

	public int getDimension() {
		return getDiemension(root, new int[] { 0 }, new int[] { 0 });
	}

	// 中序遍历
	public void inOrder() {
		order(root, OrderWay.inOrderWay);
	}

	private void order(Node<E> node, OrderWay orderWay) {
		if (node == null)
			return;
		if (orderWay == OrderWay.preOrderWay)
			node.print();
		if (node.Left != null)
			order(node.Left, orderWay);
		if (orderWay == OrderWay.inOrderWay)
			node.print();
		if (node.Right != null)
			order(node.Right, orderWay);
		if (orderWay == OrderWay.postOrderWay)
			node.print();
	}
	public List<Double> order(Node<E> node, OrderWay orderWay,List<Double>memoryList) {
		if (node == null)
			return null;
		if (orderWay == OrderWay.preOrderWay)
			memoryList.add(node.Key);
		if (node.Left != null)
			order(node.Left, orderWay,memoryList);
		if (orderWay == OrderWay.inOrderWay)
			memoryList.add(node.Key);
		if (node.Right != null)
			order(node.Right, orderWay,memoryList);
		if (orderWay == OrderWay.postOrderWay)
			memoryList.add(node.Key);
		
		return memoryList;
	}
	//每次遍历记录数据，返回链表形式
	public List<Double> orderDescending(Node<E> node, OrderWay orderWay,List<Double>memoryList) {
		if (node == null)
			return null;
		if (orderWay == OrderWay.preOrderWay)
			memoryList.add(node.Key);
		if (node.Right != null)
			orderDescending(node.Right, orderWay,memoryList);
		if (orderWay == OrderWay.inOrderWay)
			memoryList.add(node.Key);
		if (node.Left != null)
			orderDescending(node.Left, orderWay,memoryList);
		if (orderWay == OrderWay.postOrderWay)
			memoryList.add(node.Key);
		
		return memoryList;
	}

	// 前序遍历
	public void preOrder() {
		order(root, OrderWay.preOrderWay);
	}

	// 前序降序遍历
	public void preOrderDescending() {
		orderDescend(root, OrderWay.preOrderWay);
	}
	// 中序降序遍历
	public void inOrderDescending() {
		orderDescend(root, OrderWay.inOrderWay);
	}
	// 后序降序遍历
	public void postOrderDescending() {
		orderDescend(root, OrderWay.postOrderWay);
	}

	// 后续遍历
	public void postOrder() {
		order(root, OrderWay.postOrderWay);
	}
	
	private void orderDescend(Node<E> node, OrderWay orderWay) {
		if (node == null)
			return;
		if (orderWay == OrderWay.preOrderWay)
			node.print();
		if (node.Right != null)
			orderDescend(node.Right, orderWay);
		if (orderWay == OrderWay.inOrderWay)
			node.print();
		if (node.Left != null)
			orderDescend(node.Left, orderWay);
		if (orderWay == OrderWay.postOrderWay)
			node.print();
	}
}
//二叉树节点对，用于打印二叉树图
class NodePair {
	public boolean IsNull;
	public int Dimension;
	public double L = 4.9E-324;
	public double R = 4.9E-324;

	public NodePair(boolean isnull, int d, double L, double R) {
		IsNull = isnull;
		Dimension = d;
		this.L = L;
		this.R = R;
	}
}

//二叉树遍历方式
enum OrderWay {
	preOrderWay, inOrderWay, postOrderWay,
}

//二叉树节点
class Node<E> {
	public int Dimension;
	public double Key;
	public Object Obj;
	public Node<E> Left;
	public Node<E> Right;

	public Node(E e) {
		this.Key = E2Double(e);
	}

	public Node(E e, Object obj) {
		this(e);
		this.Obj = obj;
	}

	public Node(E e, int id) {
		this.Key = E2Double(e);
		this.Dimension = id;
	}

	public Node(E e, Object obj, int id) {
		this(e, obj);
		this.Dimension = id;
	}

	public Node(Float e, Object obj, int id) {
		Key = e;
		Obj = obj;
		this.Dimension = id;
	}

	private double E2Double(E e) {
		double value = Double.MIN_VALUE;
		if (e instanceof Number) {
			value = ((Number) e).doubleValue();
		}
		return value;
	}

	public void add(E e) {
		double value = E2Double(e);
		if (value <= this.Key) {
			if (this.Left != null)
				this.Left.add(e);
			else {
				this.Left = new Node<E>(e);
				return;
			}
		} else {
			if (this.Right != null)
				this.Right.add(e);
			else {
				this.Right = new Node<E>(e);
				return;
			}
		}

	}

	public void add(E e, Object obj, int d) {
		double value = E2Double(e);
		if (value <= this.Key) {
			if (this.Left != null)
				this.Left.add(e, obj, d + 1);
			else {
				this.Left = new Node<E>(e, obj, d);
				return;
			}
		} else {
			if (this.Right != null)
				this.Right.add(e, obj, d + 1);
			else {
				this.Right = new Node<E>(e, obj, d);
				return;
			}
		}
	}

	public void add(Float e, Object obj, int d) {
		double value = e;
		if (value <= this.Key) {
			if (this.Left != null)
				this.Left.add(e, obj, d + 1);
			else {
				this.Left = new Node<E>(e, obj, d);
				return;
			}
		} else {
			if (this.Right != null)
				this.Right.add(e, obj, d + 1);
			else {
				this.Right = new Node<E>(e, obj, d);
				return;
			}
		}
	}

	public void add(E e, int d) {
		double value = E2Double(e);
		if (value <= this.Key) {
			if (this.Left != null)
				this.Left.add(e, d + 1);
			else {
				this.Left = new Node<E>(e, d);
				return;
			}
		} else {
			if (this.Right != null)
				this.Right.add(e, d + 1);
			else {
				this.Right = new Node<E>(e, d);
				return;
			}
		}
	}

	public void print() {
		if (Obj == null)
			System.out.println(this.Key);
		else {
			if (Obj instanceof Hero) {
				System.out.println((Hero) Obj);
			}
		}
	}

}

------------------主方法调用测试-----------------------------
	public static void main(String[] args) throws IndexIsNagetiveException, IndexIsOutofRangeException {
		int number = 5 * 10000;
		System.out.println("测试次数"+number);
		int[] list = GetArrList(number);
		int[] list1 = getarr(list);
		int[] list2 = getarr(list);
		long startMs = System.currentTimeMillis();
		MyTree<Integer> mTree = GetMyTree(list);
		List<Double> treelist = mTree.orderDescending(mTree.root, OrderWay.inOrderWay, new ArrayList<>());
		long endMs = System.currentTimeMillis();
		long timeTree = endMs - startMs;
		System.out.println("Tree.InOrder 用时(ms):" + timeTree);
		long timeBub = BubbleSort(list1);
		System.out.println("BubbleSort 用时(ms):" + timeBub);
		long timeSelect = SelectSort(list2);
		System.out.println("SelectSort 用时(ms):" + timeSelect);
		System.out.println("冒泡排序与二叉树结果一致？：" + compareSortRes(list1, treelist));
		System.out.println("选择排序与二叉树结果一致？：" + compareSortRes(list2, treelist));
		System.out.println("冒泡排序与选择排序结果一致？：" + compareSortRes2(list2, list1));
		// mTree.print();
	}

	public static int[]getarr(int[]list)
	{
		int [] arr = new int[list.length];
		int index = 0;
		for (int i : list) {
			arr[index++] = i;
		}
		return arr;
	}

	public static boolean compareSortRes(int[] list, List<Double> list2) {
		int length = list.length;
		for (int i = 0; i < length; i++) {
			if (list[i] != (int) ((double) Math.floor(list2.get(i))))
				return false;
		}
		return true;
	}

	public static boolean compareSortRes2(int[] list, int[] list2) {
		int length = list.length;
		for (int i = 0; i < length; i++) {
			if (list[i] != list[i])
				return false;
		}
		return true;
	}

	public static MyTree<Integer> GetMyTree(int[] arr) {
		MyTree<Integer> mTree = new MyTree<>();
		for (int i : arr) {
			mTree.add(i);
		}
		return mTree;
	}

	public static int[] GetArrList(int Num) {
		int[] is = new int[Num];
		for (int i = 0; i < Num; i++) {
			is[i] = (int) (Math.random() * 1000);
		}
		return is;
	}

	public static long BubbleSort(int[] list) {
		long startMs = System.currentTimeMillis();
		int length = list.length;
		for (int i = 0; i < length - 1; i++) {
			for (int j = 0; j < length - 1 - i; j++) {
				if (list[j] < list[j + 1]) {
					int temp = list[j + 1];
					list[j + 1] = list[j];
					list[j] = temp;
				}
			}
		}
		long endMs = System.currentTimeMillis();
		return endMs - startMs;
	}

	public static long SelectSort(int[] list) {
		long startMs = System.currentTimeMillis();
		int length = list.length;
		for (int i = 0; i < length - 1; i++) {
			for (int j = i + 1; j < length; j++) {
				if (list[i] < list[j]) {
					int temp = list[j];
					list[j] = list[i];
					list[i] = temp;
				}
			}
		}
		long endMs = System.currentTimeMillis();
		return endMs - startMs;
	}

	public static void compListArr2Link() {
		List<Integer> list = new ArrayList<>();
		int n = 500 * 10000;
		System.out.println("测试次数：" + n);
		long time = testList(list, n);
		System.out.println("ArrayList执行Add用时(ms)：" + time);
		list = new LinkedList<>();
		time = testList(list, n);
		System.out.println("LinkedList执行Add用时(ms)：" + time);
	}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class testBST {
    static class Hero{
        String name;
        int HP;

        public Hero(String name, int HP) {
            this.name = name;
            this.HP = HP;
        }

        @Override
        public String toString() {
            return "name: " + name  +
                    "HP: " + HP;
        }
    }

   static class btsTree{
        btsTree leftnode;
        btsTree rightnode;
        Hero myhero;
        void add(Object obj)
        {
            if (myhero==null)
            myhero=(Hero) obj;
            else
            {
                if (((Hero)obj).HP<=this.myhero.HP)
                {
                    if (this.leftnode==null)
                    {
                        leftnode=new btsTree();

                    }
                    leftnode.add(obj);
                }
                else
                {
                    if (this.rightnode==null)
                    {
                        rightnode=new btsTree();
                    }
                    rightnode.add(obj);
                }

            }

        }

        void LastNode()
        {
            if (this.myhero==null)
                return;
            if (this.rightnode!=null)
            {
                this.rightnode.LastNode();
            }
            System.out.println(this.myhero.toString());
            if (this.leftnode!=null)
            {
                this.leftnode.LastNode();
            }

        }


    }

    public static void  main(String[] args) {
        while (true) {
            int n=0;
            btsTree myBtsTree=new btsTree();
            Scanner input=new Scanner(System.in);
            System.out.print("请输入英雄数目：");
            n=input.nextInt();
            List<Hero> heroes=new ArrayList<>();
            for (int i = 0; i < n; i++) {
                heroes.add(new Hero("hero"+i,(int)(Math.random()*100)));
            }
            for (Hero hero:heroes)
            {
                myBtsTree.add(hero);
            }
            myBtsTree.LastNode();
        }
    }
}

package yu;
import java.util.List;
import java.util.ArrayList;
import yu.Hero;
import java.util.Random;
public class HeroNode {
    public HeroNode left;
    public HeroNode right;
    public Hero value;

    public HeroNode(Hero value) {
        this.value = value;    }

    public void add(Hero hero) {
        if (hero.getHp() > this.value.getHp()) {
            if (this.right == null) {
                this.right = new HeroNode(hero);
            } else {
                this.right.add(hero);
            }
        } else {
            if (this.left == null) {
                this.left = new HeroNode(hero);
            } else {
                this.left.add(hero);
            }
        }
    }

    public List<Hero> sort() {
        List<Hero> result = new ArrayList<>();
        if (this.left != null) {
            result.addAll(this.left.sort());
        }
        result.add(this.value);
        if (this.right != null) {
            result.addAll(this.right.sort());
        }
        return result;
    }

    
    public static void main(String[] args) {
       Random random = new Random();
       HeroNode root = new HeroNode(new Hero("hero"+0,random.nextInt(500)));
       List<Hero>heros = new ArrayList<>();
       heros.add(root.value);
        for (int i = 0; i < 9; i++) {
           heros.add(new Hero("hero" + (i + 1), random.nextInt(500)));
           root.add(new Hero(heros.get(i+1).getName(),heros.get(i+1).getHp()));
        }
        for(int i=0;i<heros.size();i++){
        	System.out.println("name:"+heros.get(i).getName()+"  hp:"+heros.get(i).getHp());
        }
        System.out.println("-------------");
        List<Hero> sorted = root.sort();
        for (Hero hero : sorted) {
            System.out.println("name:"+hero.getName() + "   hp:" + hero.getHp());
        }
    }
}

package com.white.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: white
 * @Date: 2023/9/23 - 09 - 23 - 11:54
 * @Description: com.white.tree
 * @version: 1.0
 */
public class HeroNode {
    //左节点
    private HeroNode leftNode;
    //右节点
    private HeroNode rightNode;
    //Hero类型的变量
    private Hero hero;

    //插入数据
    public void add(Hero hero){
        //如果当前节点没有值，就把数据放在当前节点上
        if (this.hero == null) {
            this.hero = hero;
        }
        // 如果当前节点有值，就进行判断，新增的值与当前值的大小关系
        else {
            // 新增的值，比当前值大或者相同，比当前值大就去左边
            if (this.hero.hp - hero.hp <= 0) {
                if (leftNode == null) {
                    leftNode = new HeroNode();
                }
                leftNode.add(hero);
            }
            // 新增的值，比当前值小，比当前值大就去右边
            else{
                if (rightNode == null) {
                    rightNode = new HeroNode();
                }
                rightNode.add(hero);
            }
        }
    }

    public List<Hero> inOrderTraverse(){
        List<Hero> heroValues = new ArrayList<>();

        if(leftNode != null){
            heroValues.addAll(leftNode.inOrderTraverse());
        }
        heroValues.add(this.hero);
        if (rightNode != null) {
            heroValues.addAll(rightNode.inOrderTraverse());
        }
        return heroValues;
    }


    //这是一个main方法，是程序的入口：
    public static void main(String[] args) {
        //实例化一个集合对象，用来存储Hero对象
        List<Hero> heros = new ArrayList<>();
        //随机生成10个Hero对象，每个Hero对象都有不同的血量值
        for (int i = 0; i < 10; i++) {
            heros.add(new Hero("hero"+i,(float)Math.random()*100));
        }
        //打印试试看
        System.out.println(heros);

        //实例化一个HeroNode二叉树对象，作为根节点
        HeroNode heroRoots = new HeroNode();
        //遍历集合，将里面的Hero对象加进二叉树
        for(Hero h : heros){
            heroRoots.add(h);
        }
        System.out.println(heroRoots.inOrderTraverse());

        List heroList = heroRoots.inOrderTraverse();
        for (int i= 0; i < heroList.size(); i++) {
            System.out.print(heroList.get(i));
        }


    }


}

//快速排序
public static void quickSort(int[] arr, int l, int r) {
    if (l < r) {
        int pivot = arr[l];//定义基准
        int i = l;
        int j = r;
        while (i < j) {//当左右指针没重合时
            while (i < j && arr[j] > pivot)
                j--;
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
//                System.out.println("右指针操作完成时的数组：");
//                print(arr);
            while (i < j && arr[i] < pivot)
                i++;
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
//                System.out.println("左指针操作完成时的数组：");
//                print(arr);
        }
        arr[i] = pivot;
        quickSort(arr, l, i-1);
        quickSort(arr, i+1, r);
//            System.out.println("快速排序后的数组：");
//            print(arr);
    }
}