二叉树，单链表，反向链表，stack栈 二叉查找树

// 二叉查找树节点 Binary search tree node
    public class BinarySearchTreeNode
    { public int key;// 二叉查找树节点的值
       public BinarySearchTreeNode left;// 二叉查找树节点的左子节点
       public BinarySearchTreeNode right;// 二叉查找树节点的右子节点
       /// 二叉查找树节点构造函数
       public BinarySearchTreeNode(int nodeValue)
       {   key = nodeValue;//nodeValue 节点的值
           left = null; right = null;
       }
       /// 插入节点
       public void InsertNode(BinarySearchTreeNode node)
       {   if(node.key > this.key)
           {  if(this.right == null)
              {   this.right = node;//node插入的节点
                  return;
              }
              else
                  this.right.InsertNode(node);
           }
           else
           {   if(this.left == null)
              {   this.left = node; return; }
              else
                  this.left.InsertNode(node);
           }
       }
       /// 二叉查找树查询
       public bool SearchKey(int searchValue)
       { if(this.key == searchValue)//searchValue需要查询的值
              return true;// 是否找到查询的值
           if(searchValue > this.key)
           {   if(this.right == null) return false;
              else
                  return this.right.SearchKey(searchValue);
           }
           else
           {   if(this.left == null)   return false;
              else
                  return this.left.SearchKey(searchValue);
           }
       }
       // 中序遍历
       public void MiddleDisplay()
       { if(this.left != null)
              this.left.MiddleDisplay();
           Console.WriteLine(this.key);
           if(this.right != null)
              this.right.MiddleDisplay();
       }
       // 前序遍历
       public void FrontDisplay()
       { Console.WriteLine(this.key);
           if(this.left != null)
              this.left.FrontDisplay();
           if(this.right != null)
              this.right.FrontDisplay();
       }
       // 后序遍历
       public void BehindDisplay()
       {   if(this.left != null)
              this.left.BehindDisplay();
           if(this.right != null)
              this.right.BehindDisplay();
           Console.WriteLine(this.key);
       }
    }
    /// 二叉查找树
    public class BinarySearchTree
    {   private BinarySearchTreeNode root;
       /// 生成一个二叉查找树
        public BinarySearchTree()
       {   root = nul; }
       /// 生成一个二叉查找树
       /// <param name="nodeValue">二叉查找树根节点的值</param>
       public BinarySearchTree(int nodeValue)
       { root = new BinarySearchTreeNode(nodeValue); }
       /// 在二叉查找树上插入一个节点
       /// <param name="nodeValue">插入节点的值</param>
       public void InsertBinarySearchTreeNode(int nodeValue)
       {   BinarySearchTreeNode insertNode = new BinarySearchTreeNode(nodeValue);
                     if(root == null)
           { root = insertNode;
              return;
           }
           else
              root.InsertNode(insertNode);
           return;
       }
       /// 在二叉查找树上查询一个数
       /// <param name="searchValue">需要查询的值</param>
       /// <returns>是否找到查询的值</returns>
       public bool SearchKey(int searchValue)
       { if(root.key == searchValue)   return true;
           else
              return root.SearchKey(searchValue);
       }
       /// 二叉查找树中序遍历
       public void MiddleDisplay()
       { root.MiddeleDisplay(); return; }
       /// 二叉查找树前序遍历
       public void FrontDisplay()
       { root.FrontDisplay(); return; }
       /// 二叉查找树后序遍历
       public void BehindDisplay()
       {   root.BehindDisplay(); return; }
       /// 二叉查找树排序
       /// <param name="a">需要排序的数组</param>
       public static void BinarySearchTreeSort(int [] a)
       { BinarySearchTree t = new BinarySearchTree();
           for(int i = 0; i < a.Length; i ++)
              t.InsertBinarySearchTreeNode(a[i]);
           t.MiddleDisplay();return;
       }/// 二叉查找树查找
       /// <param name="a">进行查找的数组</param>
       /// <param name="searchKey">需要查找的树</param>
       public static bool BinarySearchTreeSearch(int [] a, int searchKey)
       {   BinarySearchTree t = new BinarySearchTree();
           for(int i = 0; i < a.Length; i ++)
              t.InsertBinarySearchTreeNode(a[i]);
           return t.SearchKey(searchKey);
       }
    }
namespace 二叉树
{   class Node
    {   int n;
        public Node(int x)
        {   n=x; }
        public Node Left;
        public Node Right;
        public void Insert(Node node)
        {   if(node.n > this.n)
            {   if(this.Right == null)
                    this.Right = node;
                else
                    this.Right.Insert(node);   }
            else
            {   if(this.Left == null)
                { this.Left = node; }
                else
                { this.Left.Insert(node); }  }   }    //递归
        public void Show()
        {   Console.WriteLine(n); } }
    class BinaryTree
    {   Node root;
        public void GenerateTree(Node node) //高内聚，低耦合
        {   if(root == null)
            {   root = node; return; }//如果树是空，第一次加节点
            root.Insert(node);
    }
        public void ShowInOrder(Node node) //中序遍历(in order)：左中右。先(前)序遍历(pre order)：中左右。后序遍历(post order)：左右中。
        {  if(node == null) return;//递归必须有个终止条件,递归方法中一定要接受参数
            ShowInOrder(node.Left);
            node.Show();
            ShowInOrder(node.Right);
        }
        public void Show()
        {   ShowInOrder(root); }
}
    class A
    {   static void Main()
        {   BinaryTree b = new BinaryTree();
            Node node = new Node(5);
            b.GenerateTree(node);
            node = new Node(13);
            b.GenerateTree(node);
            node = new Node(6);
            b.GenerateTree(node);
            node = new Node(26);
            b.GenerateTree(node);
            node = new Node(7);
            b.GenerateTree(node);
            b.Show();   }   }   }    结果:5,6,7,13,26
单链表
    class Node
    { int a;
       public Node(int a)
       {   this.a=a; }
       public int A     
       {get{return a;}  set{a=value;} }
       public Node next;
    }
    class LinkedList
    { Node header;
       public void Generate(int x)
       {   if(header==null)
              header=new Node(x);
           else
           {   Node n = new Node(x);
              if(n.A < header.A)
              {   n.next = header;
                  header=n;
                  return;
              }
              Node tmp=header;
              Node t=header;
              while(tmp.A < n.A)
              {   t=tmp; //为了下一次循环
                  tmp=tmp.next;
                  if(tmp==null)
                     break;
              }
              t.next=n;
              n.next=tmp;
           }
       }
       public void Out()
       {   Node tmp=header;
           while(tmp!=null)
           {   Console.WriteLine(tmp.A);
              tmp = tmp.next;
           } } }
    class Test
    {   static void Main()
       {   LinkedList ll = new LinkedList();
           ll.Generate(6);
           ll.Generate(36);
           ll.Generate(26);
           ll.Generate(16);
           ll.Out();
       }   }   }
反向链表
    class Link            //this class reverse the LinkedList
    { public int a;
       public Link next;
    }
    class createLink     //the class create the LinkedList
    {
       Link header=null;
       Link p = null;
       Link temp = null;
       Link l=null;       //Link k=null;
       Link g=null;
       public void create()
       { string str;
           int i;
           Console.WriteLine("Please enter number:");
           str=Console.ReadLine();
           while(str!="y")
           { i=Convert.ToInt32(str);
              temp=new Link();
              temp.a=i;
              temp.next=null;
                if(g==null)
                  g=temp;
              if(header==null)
                  header=temp;
              if(p==null)
                  p=temp;
              else
              { p.next=temp;
                  p=p.next;
              }
              Console.WriteLine("please enter number:");
              str=Console.ReadLine();
           }
       }
       public void display()
       {   while(header!=null)
           {   Console.WriteLine(header.a);
              header=header.next;
           }
       }
       public void reversed() // the mothod reversed the LinkedList
       { Link k=null;
           Link tmp=null;
           Link com =null;
           if(tmp==null)
              tmp=header.next;
           while(tmp!=null)
           {  //            if(com==null)
//             com=header;
              l=tmp;
              if(k==null)
              {   header.next=null;
                  k=header;
              }
              com=header;
              header=l;
              tmp=l.next;
              l.next=com;
           }
       }
       public void show()
       {   while(l!=null)
           {   Console.WriteLine(l.a);
              l=l.next;
           } } }
    class Tester
    {   static void Main()
       {  createLink cl=new createLink();
           cl.create();
           //cl.display();
           cl.reversed();
           cl.show();
       } } }
Stack 栈
    class Node
    { int a;
       public Node(int a)
       {   this.a=a; }
       public int A
       { get{return a;} set{a=value;} }
       public Node next;
    }
    class LinkedList
    { protected Node header;
       public void Generate(int x)
       {   if(header==null)
              header=new Node(x);
           else
           {   Node n = new Node(x);
              n.next=header;
              header=n;
           }
       }
       public void Out()
       {   Node tmp=header;
           while(tmp!=null)
           {   Console.WriteLine(tmp.A);
              tmp = tmp.next;
           } } }
    class Stack : LinkedList
    {   public void Push(int x)
       {   this.Generate(x); }
       public int Pop()
       { if(this.header == null)
              return -1; // empty stack
           int n = header.A;
           header = header.next;
           return n;
       }
    }
    class Test
    {   static void Main()
       {   Stack ss = new Stack();
           ss.Push(7);
           ss.Push(78);
           ss.Push(9);
           ss.Push(2);
           int i = ss.Pop();
           while(i != -1)
           {   Console.WriteLine(i);
              i = ss.Pop();
           } } } }