参考：http://www.cnblogs.com/skywang12345/p/3577479.html

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Diagnostics;using System.Threading;using System.IO;using System.Collections;namespace ConsoleApplication2{    public class Program    {        public static void Main()        {            int[] arr = { 3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9 };            AVLTree
     
       avlTree = new AVLTree
      
       ();            for (int i = 0; i < arr.Length; i++)            {                avlTree.Insert(arr[i]);                Console.Write(arr[i] + " ");            }            Console.WriteLine();            Console.Write("层遍历：");            avlTree.LevelOrder();            Console.WriteLine();            Console.Write("删除节点15：");            avlTree.Remove(15);            avlTree.LevelOrder();            Console.WriteLine();            Console.Write("删除节点16：");            avlTree.Remove(16);            avlTree.LevelOrder();            Console.WriteLine();            Console.Write("删除节点7：");            avlTree.Remove(7);            avlTree.LevelOrder();            Console.WriteLine();            Console.Read();        }    }    public class AVLTreeNote
       
         where TKey : IComparable    {        public AVLTreeNote(TKey key, AVLTreeNote
        
          leftNote, AVLTreeNote
         
           rightNote)        {            Key = key;            LeftNote = leftNote;            RightNote = rightNote;        }        public TKey Key { get; set; }        public int Height { get; set; }        public AVLTreeNote
          
            LeftNote { get; set; } public AVLTreeNote
           
             RightNote { get; set; } } public class AVLTree
            
              where TKey : IComparable { private AVLTreeNote
             
               RootNote { get; set; } public AVLTree() { } private int GetHeight() { return 0; } private int GetHeight(AVLTreeNote
              
                note) { return note == null ? 0 : note.Height; } private AVLTreeNote
               
                 LeftLeftRotation(AVLTreeNote
                
                  note) { AVLTreeNote
                 
                   temp = note.LeftNote; note.LeftNote = temp.RightNote; temp.RightNote = note; note.Height = Math.Max(GetHeight(note.LeftNote), GetHeight(note.RightNote)) + 1; temp.Height = Math.Max(GetHeight(temp.LeftNote), GetHeight(temp.RightNote)) + 1; return temp; } private AVLTreeNote
                  
                    RightRightRotation(AVLTreeNote
                   
                     note) { AVLTreeNote
                    
                      temp = note.RightNote; note.RightNote = temp.LeftNote; temp.LeftNote = note; note.Height = Math.Max(GetHeight(note.LeftNote), GetHeight(note.RightNote)) + 1; temp.Height = Math.Max(GetHeight(temp.LeftNote), GetHeight(temp.RightNote)) + 1; return temp; } private AVLTreeNote
                     
                       LeftRightRotation(AVLTreeNote
                      
                        note) { note.LeftNote = RightRightRotation(note.LeftNote); return LeftLeftRotation(note); } private AVLTreeNote
                       
                         RightLeftRotation(AVLTreeNote
                        
                          note) { note.RightNote = LeftLeftRotation(note.RightNote); return RightRightRotation(note); } public void Insert(TKey key) { RootNote = Insert(key, RootNote); } private AVLTreeNote
                         
                           Insert(TKey key, AVLTreeNote
                          
                            note) { if (note == null) { note = new AVLTreeNote
                           
                            (key, null, null); } else { if (key.CompareTo(note.Key) < 0) { note.LeftNote = Insert(key, note.LeftNote); if (Math.Abs(GetHeight(note.LeftNote) - GetHeight(note.RightNote)) == 2) { if (key.CompareTo(note.LeftNote.Key) < 0)//其实这里判断就像知道新增加的子节点属于左节点还是右节点 画图的话 一目了然 { note = LeftLeftRotation(note); } else { note = LeftRightRotation(note); } } } if (key.CompareTo(note.Key) > 0) { note.RightNote = Insert(key, note.RightNote); if (Math.Abs(GetHeight(note.RightNote) - GetHeight(note.LeftNote)) == 2) { if (key.CompareTo(note.RightNote.Key) > 0)//其实这里判断就像知道新增加的子节点属于左节点还是右节点 画图的话 一目了然 { note = RightRightRotation(note); } else { note = RightLeftRotation(note); } } } } note.Height = Math.Max(GetHeight(note.LeftNote), GetHeight(note.RightNote)) + 1; return note; } public void Remove(TKey key) { Remove(key, RootNote); } private AVLTreeNote
                            
                              Remove(TKey key, AVLTreeNote
                             
                               note) { if (note == null) { return null; } if (key.CompareTo(note.Key) < 0) { note.LeftNote = Remove(key, note.LeftNote); if (Math.Abs(GetHeight(note.RightNote) - GetHeight(note.LeftNote)) == 2) { AVLTreeNote
                              
                                rightNote = note.RightNote; if (GetHeight(rightNote.LeftNote) > GetHeight(rightNote.RightNote)) { note = RightLeftRotation(note); } else { note = RightRightRotation(note); } } } if (key.CompareTo(note.Key) > 0) { note.RightNote = Remove(key, note.RightNote); if (Math.Abs(GetHeight(note.RightNote) - GetHeight(note.LeftNote)) == 2) { AVLTreeNote
                               
                                 leftNote = note.LeftNote; if (GetHeight(leftNote.RightNote) > GetHeight(leftNote.LeftNote)) { note = LeftRightRotation(note); } else { note = LeftLeftRotation(note); } } } if (note.Key.CompareTo(key) == 0) { if (note.LeftNote != null && note.RightNote != null) { if (GetHeight(note.LeftNote) > GetHeight(note.RightNote)) { AVLTreeNote
                                
                                  max = FindMax(note.LeftNote); note.Key = max.Key; note.LeftNote = Remove(max.Key, note.LeftNote); } else { AVLTreeNote
                                 
                                   min = FindMin(note.RightNote); note.Key = min.Key; note.RightNote = Remove(min.Key, note.RightNote); } } else { note = note.LeftNote == null ? note.RightNote : note.LeftNote; } } return note; } public void LevelOrder() { LevelOrder(RootNote); } private void LevelOrder(AVLTreeNote
                                  
                                    note) { Queue
                                   
                                    
                                     > queue = new Queue
                                     
                                      
                                       >(); queue.Enqueue(note); while (queue.Count > 0) { var temp = queue.Dequeue(); Console.Write(temp.Key + " "); if (temp.LeftNote != null) { queue.Enqueue(temp.LeftNote); } if (temp.RightNote != null) { queue.Enqueue(temp.RightNote); } } } public AVLTreeNote
                                       
                                         FindMin() { return FindMin(RootNote); } private AVLTreeNote
                                        
                                          FindMin(AVLTreeNote
                                         
                                           note) { if (note.LeftNote == null) { return note; } return FindMin(note.LeftNote); } public AVLTreeNote
                                          
                                            FindMax() { return FindMax(RootNote); } private AVLTreeNote
                                           
                                             FindMax(AVLTreeNote
                                            
                                              note) { if (note.RightNote == null) { return note; } return FindMax(note.RightNote); } }}