package j2se;

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

//自定义二叉树，插入的对象需实现 Comparable 接口
public class MyTree<E extends Comparable<E>>{
	private Node<E> root;

	public void add(E e) {
		if (root == null) {
			root = new Node<E>(e, 0);
		} else
			root.add(e, 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 List<? extends Comparable<E>> values(){
		
		return inOrder();
		
	}
	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 List<E> inOrder() {
		return order(root, OrderWay.inOrderWay,new ArrayList<>());
	}

	// 递归遍历
	public List<E> order(Node<E> node, OrderWay orderWay,List<E> 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<E> preOrderStack() {
		List<E> memoryList = new ArrayList<>();
		MyStack<Node<E>> stack = new MyStack<>();
		stack.push(root);
		while (stack.peek() != null) {
			Node<E> top = stack.pull();
			memoryList.add(top.Key);
			while (top != null) {
				if (top.Right != null)
					stack.push(top.Right);
				top = top.Left;
				if (top != null)
					memoryList.add(top.Key);
			}
		}
		return memoryList;
	}

	// 非递归中序遍历
	public List<E> inOrderStack() {
		List<E> memoryList = new ArrayList<>();
		MyStack<Node<E>> stack = new MyStack<>();
		Node<E> top = root;
		do {
			while (top != null) {
				if (top.Left != null || top.Right != null)
					stack.push(top);
				else
					memoryList.add(top.Key);
				top = top.Left;
			}
			top = stack.pull();
			if (top != null) {
				memoryList.add(top.Key);
				top = top.Right;
			}
		} while (top != null || stack.peek() != null);
		return memoryList;
	}

	// 非递归中序降序遍历
	public List<E> inOrderStackDescending() {
		List<E> memoryList = new ArrayList<>();
		MyStack<Node<E>> stack = new MyStack<>();
		Node<E> top = root;
		do {
			while (top != null) {
				if (top.Left != null || top.Right != null)
					stack.push(top);
				else
					memoryList.add(top.Key);
				top = top.Right;
			}
			top = stack.pull();
			if (top != null) {
				memoryList.add(top.Key);
				top = top.Left;

			}
		} while (top != null || stack.peek() != null);
		return memoryList;
	}

	//非递归后续遍历
	public List<E> postOrderStack() {
		List<E> memoryList = new ArrayList<>();
		MyStack<Node<E>> stack = new MyStack<>();
		Node<E> top = root;
		MyStack<Node<E>> memoryStack = new MyStack<>();
		// stack.push(root);
		do {

			while (top != null) {
				if (top.Left != null || top.Right != null)
					stack.push(top);
				else
					memoryList.add(top.Key);
				top = top.Left;
			}
			while (stack.peek() == memoryStack.peek() && stack.peek() != null) {
				stack.pull();
				memoryList.add(memoryStack.pull().Key);
			}
			if (stack.peek() != null) {
				memoryStack.push(stack.peek());
				top = stack.peek().Right;
			}

		} while (stack.peek() != null || top != null);
		return memoryList;
	}

	// 每次遍历记录数据，返回链表形式
	public List<E> orderDescending(Node<E> node, OrderWay orderWay, List<E> 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 List<E> preOrder() {
		return order(root, OrderWay.preOrderWay,new ArrayList<>());
	}

	// 前序降序遍历
	public List<E> preOrderDescending() {
		return orderDescending(root, OrderWay.preOrderWay,new ArrayList<>());
	}

	// 中序降序遍历
	public List<E> inOrderDescending() {
		return orderDescending(root, OrderWay.inOrderWay,new ArrayList<>());
	}

	// 后序降序遍历
	public List<E> postOrderDescending() {
		return orderDescending(root, OrderWay.postOrderWay,new ArrayList<>());
	}

	// 后续遍历
	public List<E> postOrder() {
		return order(root, OrderWay.postOrderWay,new ArrayList<>());
	}
}

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

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

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

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

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

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

	public void add(E e) {
		if (e.compareTo(Key)<=0) {
			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) {
		if (e.compareTo(Key)<=0) {
			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) {
		if (e.compareTo(Key)<=0) {
			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;
			}
		}
	}

}

----------------------下面为主函数调用--------------------------

ublic static void main(String[] args) throws Exception {
		Random r = new Random();
		//创建不同类型的数值型（实现Comparable）二叉树
		MyTree<Integer>t1 = new MyTree<>();
		MyTree<Double>t2 = new MyTree<>();
		MyTree<Float>t3 = new MyTree<>();
		//创建不同类型的对象（实现Comparable）二叉树
		MyTree<Hero>t4 = new MyTree<>();
		MyTree<Item>t5 = new MyTree<>();
		
		//用随机数值初始化以上二叉树
		for (int i = 0; i < 10; i++) {
			t1.add(r.nextInt(10));
		}
		for (int i = 0; i < 10; i++) {
			t2.add(r.nextDouble());
		}
		
		for (int i = 0; i < 10; i++) {
			t3.add(r.nextFloat());
		}
		for (int i = 0; i < 10; i++) {
			t4.add(new Hero("Hero - "+r.nextInt(10),r.nextFloat(),r.nextFloat(),r.nextInt(10)));
		}
		for (int i = 0; i < 10; i++) {
			t5.add(new Item("potion - "+r.nextInt(10),r.nextInt(10)));
		}
		//遍历二叉树，打印结果
		iterate(t1);
		iterate(t2);
		iterate(t3);
		iterate(t4);
		iterate(t5);

		//测试二叉树排序性能
		testBinaryTree();
	}
	public static void iterate(MyTree nums)//中序遍历二叉树，打印结果
	{
		System.out.println(nums.inOrderStackDescending()+"\r\n");
	}

------------------下面为测试二叉树性能方法---------------------------------

public static void testBinaryTree() throws IndexIsNagetiveException, IndexIsOutofRangeException {
		int number = 10 * 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<Integer> treelist1 = mTree.inOrderDescending();
		long endMs = System.currentTimeMillis();
		long timeTree = endMs - startMs;
		System.out.println("Tree.InOrder（递归） 用时(ms):" + timeTree);


		long startMs3 = System.currentTimeMillis();
		MyTree<Integer> mTree3 = GetMyTree(list);
		List<Integer>treelist3 = mTree3.inOrderStackDescending();
		long endMs3 = System.currentTimeMillis();
		long timeTree3 = endMs3 - startMs3;
		System.out.println("Tree.postOrder(非递归) 用时(ms):" + timeTree3);
		
		 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,
		 treelist1));
		 System.out.println("选择排序与二叉树结果一致？：" + compareSortRes(list2,
		 treelist1));
		 System.out.println("冒泡排序与选择排序结果一致？：" + compareSortRes2(list2,
		 list1));

		System.out.println("递归与非递归结果一致？：" + compareSortRes3(treelist3, treelist1));

	}

------------下面为冒泡排序、选择排序的方法-------------
------------------以及以上结果一致性检验-------------------

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<Integer> treelist) {
		int length = list.length;
		for (int i = 0; i < length; i++) {
			if (list[i] != (int) ((double) Math.floor(treelist.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 boolean compareSortRes3(List<Integer> treelist3, List<Integer> treelist2) {
		if (treelist3 == null && treelist2 == null)
			return true;
		int length = treelist3.size();
		if (treelist3.size() != treelist2.size())
			return false;
		for (int i = 0; i < length; i++) {
			if ((double) treelist3.get(i) != (double) treelist2.get(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() * 100);
		}
		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;
	}

1.public static void iterate(ArrayList<? extends Hero> list){
       for(Hero hero :list){
           System.out.println(hero.name);
       }
    }

    public static void main(String[] args) {
        ArrayList< Hero> hs = new ArrayList<>();

        ArrayList<APHero> aphs = new ArrayList<>();

        ArrayList<ADHero> adhs = new ArrayList<>();



        iterate(hs);

        iterate(adhs);
    }


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

public class Node2<T extends Comparable<T>> {
    Node2<T> leftNode;

    Node2<T> rightNode;

    T t;

    public void add(T t){
      if(this.t==null){
          this.t=t;
      }else{
          if(t.compareTo(this.t)<=0){
              if(null==leftNode){
                  leftNode=new Node2<>();              }leftNode.add(t);
          }else{
              if(null==rightNode)
                  rightNode=new Node2<>();
              rightNode.add(t);
          }
      }
    }
    public List<T> order(){
        List<T> values=new ArrayList<>();
        if(null!=leftNode){
            values.addAll(leftNode.order());
        }
        values.add(t);
        if(null!=rightNode){
            values.addAll(rightNode.order());
        }

        return values;
    }

    public static void main(String[] args) {
        Node2<Hero> hero =new Node2<>();
        for(int i=0;i<10;i++){
            hero.add(new Hero("hero"+i,111,(int) (Math.random() * 901) + 100));
        }
        for(Hero h:hero.order()){
            System.out.println(h);
        }
    }
}

public static void iterate(ArrayList< ?extends Hero> list) {
        for (Hero hero : list) {
            System.out.println(hero.name);
        }
    }
 public static void iterate(ArrayList<  Hero> list) {
        for (Hero hero : list) {
            System.out.println(hero.name);
        }
    }

import java.util.ArrayList;

public class ListIter {
    public static void iterate(ArrayList<? extends Hero> list) {
        for (Hero hero : list) {
            System.out.println(hero.name);
        }
    }
    public static void main(String[] args) {
        ArrayList<Hero> heroes = new ArrayList<>();
        heroes.add(new Hero("a"));
        heroes.add(new ADHero("b"));
        heroes.add(new APHero("c"));
        iterate(heroes);
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayList<Hero> heroes = new ArrayList<>();
        heroes.add(new Hero("a"));
        heroes.add(new ADHero("b",1));
        heroes.add(new APHero("c",1));
        iterate(heroes);
    }
    public static void iterate(ArrayList<? extends Hero> list) {
        for (Hero hero : list) {
            System.out.println(hero.name);
        }
    }
}