数据结构在C#中的实现小结

以下是基于.net framwwork 4.8的研究。
	
数组Array：顺序存储结构
		优点：按位置索引很快，修改效率高。
		缺点：需声明存放类型，且只能存放相同类型，必须指定长度（过长浪费，过短溢出），插入与删除很慢（排除特殊情况）。
	
数组ArrayList：顺序存储结构，解决了Array的缺点，由源码得知，默认容量为4，容量自增2倍。
		不过由于容量是类成员，自增机制会引发线程安全问题，所以ArrayList不是线程安全的。
		优点：无需指定长度，无需声明存放类型，可存放不同类型元素，底层是object,顺序存储结构常有优点这里都有。
		缺点：由于底层元素是object，当为值类型时，存在装箱/拆箱操作，效率降低，且可能会有非类型安全问题。顺序存储结构常有缺点这里都有。
	
数组List：顺序存储结构，综合Array和ArrayList的优点，所以List也不是线程安全的。
		优点：无需指定长度，长度自增。需声明存放类型，内部用Array实现，保证了类型安全。
		缺点：顺序存储结构常有缺点都有。
	所以现在基本上不使用Array和ArrayList，而是使用List。
	
双向链表LinkList：链式存储结构,非线程安全，可自己加锁实现线程安全。
		优点：插入，删除效率高，只需修改指针域的前驱节点和后继节点即可进行插入删除。
		缺点：无法基于位置索引，必须从头结点依次遍历。
	
队列Queue：顺序存储结构，先进先出集合。由官方文档得知，非线程安全，但是其有线程安全的的队列实现为ConcurrentQueue<T>。
		默认容量为32，容量自增为4(.net framework 4.8)，其他版本可能会有变化。
	
栈Stack：顺序存储结构，后进先出集合，默认容量10，容量自增2倍。非线程安全。


复习二叉树遍历，和二叉树确定的两个条件，复习二叉树还原基本原理是根据根节点位置分出左子树和右子树即可。
	复习二叉树广度优先搜索的实现，原理是使用先进先出集合队列Queue。
	复习二叉树深度优先搜索的实现，原理是使用后进先出集合栈Stack。

class ListNode{
      ListNode left;
      ListNode right;
      int val;
      public ListNode(int value){
            this.val=value;
      }
}


广度优先搜索
public void levelOrderTraversal(LsitNode node){
      if(node==null){
            System.out.print("empty tree"); 
            return;
      }
使用先进先出队列
      ArrayDeque<ListNode> deque = new ArrayDeque<ListNode>();
      deque.add(node);
      while(!deque.isEmpty()){
            ListNode rnode = deque.remove();
            System.out.print(rnode.val+"  ");
            if(rnode.left!=null){
                  deque.add(rnode.left);
            }
            if(rnode.right!=null){
                  deque.add(rnode.right);
            }
      }
}



深度优先搜索
public void depthTraversal(ListNode node){
       if(node==null){
             System.out.print("empty tree");
             return;
       }
使用后进先出栈
       Stack<ListNode> stack = new Stack<ListNode>();
       stack.push(node);
       while(!stack.isEmpty()){
             ListNode rnode = stack.pop();
             System.out.print(rnode.val);
             if(rnode.right!=null){
                   stack.push(rnode.right);
             }
             if(rnode.left!=null){
                   stack.push(rnode.left);
             }
       }
}