C#實現二叉樹查找

BuildTree 代碼1次CODE完,沒有BUG.

在畫圖地方debug了很多次.第一次畫這種圖.

一開始用treeview顯示,但發現不是很好看出樹結構,於是自己動手畫了出來.

 using System;
 using System.Collections.Generic;
 using System.ComponentModel;
 using System.Data;
 using System.Drawing;
 using System.Linq;
 using System.Text;
 using System.Windows.Forms;
 
 namespace 二叉查找樹
 {
     public partial class Form1 : Form
     {
         public Form1()
         {
             InitializeComponent();
 
            //BuildTreeView(topNode , treeView1.Nodes);
            treeView1.Visible = false;
         }
         BNode<int> topNode;
         private void Form1_Click(object sender, EventArgs e)
         {
             var lastNode = RandomGenBSPTree(50);
             topNode = lastNode.GetTopNode();
             //r1 += 0.1f;
             DrawTree(topNode, 1);
 
             maxLevel = dicLevel.Count;
             Bitmap b = new Bitmap((marginX + blockWidth) * maxLevel, (marginY + blockHeight) * maxLevel);
             var g = Graphics.FromImage(b);
             g.Clear(Color.Black);
             DrawTree2(topNode, g, b.Width / 2 - blockWidth / 2, 20,false,true);
             DrawTree3(topNode, g);
             int minI=0,maxI = 0;
             for (int i = 0; i < b.Width; i++)
             {
                 for (int y = 0; y < b.Height; y++)
                 {
                     if (b.GetPixel(i, y).R != 0 || b.GetPixel(i, y).G != 0 || b.GetPixel(i, y).B != 0)
                         goto QUITMAXI;
                 }
                 minI = i;
             }
         QUITMAXI:
             for (int i = 0; i < b.Width-minI; i++)
             {
                 int id=b.Width - 2 - i;
                 int ct = 0;
                 for (int y = 0; y < b.Height; y++)
                 {
                     if (b.GetPixel(id, y).R != 0 || b.GetPixel(id, y).G != 0 || b.GetPixel(id, y).B != 0)
                         ct++;
                     if(ct>50)
                         goto QUITMIN;
                 }
                 maxI = id;
             }
         QUITMIN:
             Bitmap bmpOut = new Bitmap(maxI-minI, b.Height);
             Graphics g2 = Graphics.FromImage(bmpOut);
             g2.DrawImage(b, new Rectangle(0, 0, bmpOut.Width, bmpOut.Height), new Rectangle(minI-20, 0, maxI, b.Height), GraphicsUnit.Pixel);
 
             this.BackgroundImage = bmpOut;
         }
 
         void BuildTreeView(BNode<int> node,TreeNodeCollection tn)
         {
             if (node == null) return;
            var newNode= tn.Add(node.value.ToString());
            BuildTreeView(node.left, newNode.Nodes);
            BuildTreeView(node.right, newNode.Nodes);
         }
         int blockWidth = 300;
         int minBlockWidth = 10;
         int blockHeight = 40;
         int marginX = 10;
         int marginY = 10;
         int maxLevel = 0;
         Font font = new Font("宋體",12,FontStyle.Bold);
         Brush brush = new SolidBrush(Color.White);
         Dictionary<int, List<BNode<int>>> dicLevel = new Dictionary<int, List<BNode<int>>>();
         void DrawTree(BNode<int> node,int level)
         {
             if (node == null) return;
             if (dicLevel.ContainsKey(level) == false)
             dicLevel.Add(level,new List<BNode<int>>());
             dicLevel[level].Add(node);
             node.level = level;
             DrawTree(node.left,level+1);
             DrawTree(node.right, level + 1);
         }
 
         void DrawTree2(BNode<int> node , Graphics g,int x,int y , bool isLeft=false,bool isRoot=false)
         {
             if (node == null) return;
           
             if (isRoot){
                 g.DrawString(node.value.ToString(), font, brush, x, y);
                 node.pos = new Point(x, y);
             }
             else
             {
                 
                 Text = r1.ToString();
                 var rate = (int)(blockWidth  - r1*Math.Pow(node.level,2) * marginX);
                 rate = rate < minBlockWidth ? minBlockWidth : rate;
                 node.pos = new Point(x + (isLeft ? -1 : 1) * (rate), y + blockHeight + marginY);
                 g.DrawString(node.value.ToString(), font, brush, node.pos.X, node.pos.Y);
             }
           
             DrawTree2(node.left, g, node.pos.X, node.pos.Y, true);
             DrawTree2(node.right, g, node.pos.X, node.pos.Y, false);
         }
         float r1=1f;
         void DrawTree3(BNode<int> node, Graphics g)
         {
             if (node == null) return;
             if (node.left != null)
                 g.DrawLine( new Pen(Color.Green,2.1f),node.pos,node.left.pos);
             if (node.right != null)
                 g.DrawLine(new Pen(Color.Green, 2.1f), node.pos, node.right.pos);
             DrawTree3(node.left , g);
             DrawTree3(node.right, g);
         }
 
         BNode<int> RandomGenBSPTree(int Count)
         {
             var r = new Random();
             List<int> pool = new List<int>();
         
             BNode<int> curNode = new BNode<int>();
             curNode.value = 50;
             pool.Add(curNode.value);
             for (int i = 0; i < Count; i++)
             {
                 do
                 {
                     var newValue = r.Next(1, 100);
                     if (pool.Contains(newValue) == false)
                     {
                         pool.Add(newValue);
                         break;
                     }
                     
                 }while(true);
 
                 curNode.Insert(pool[pool.Count-1]);
             }
             return curNode;
         }
 
         class BNode<T>where T:IComparable
         {
             public BNode<T> left;
             public BNode<T> right;
             public BNode<T> parent;
             public T value;
             public int level;
             public string text;
             public Point pos;
             public void Insert(T v)
             {
                 var firstCompare=v.CompareTo( value );
                 BNode<T> nextCompare=firstCompare<0?left:right;
                
                 if (nextCompare != null)
                 {
                     nextCompare.Insert(v);
                 }
                 else
                 {
                     if (firstCompare < 0)
                         left = new BNode<T> { parent=this, value=v };
                     else
                         right = new BNode<T> { parent = this, value = v };
                 }
             }
 
             public BNode<T> GetTopNode()
             {
                 if (parent != null)
                     return parent.GetTopNode();
                 else
                     return this;
             }
         }
       
     }
 }