應用二元樹實作一個可排序任何型別的泛型類別

2010-02-26

最近都在看書跟看文件，Code寫的比較少。因此今天來寫一篇實作的文章。

先來看下面這段Code


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> list_temp = new List<int>();   //new一個List<int>
            
            list_temp.Add(2);                        //隨便丟幾個數字進去
            list_temp.Add(7);
            list_temp.Add(3);
            list_temp.Add(4);
            
            list_temp.Sort();                        //用Sort()方法排序
            
            foreach (int i in list_temp) {           //在主控台show出來
                Console.WriteLine(i);
            }
        }
    }
}

使用Sort()方法之後，只要是數值型別，就會用由小到大的方式排序好。

不過，如果我今天是丟進去我自訂的類別，

例如List<employee> list_employee=new List<employee>();

然後我想依list_employee類別中的兩個屬性，例如說工時跟時薪相乘之後的結果來排序

又假設我現在有一個student類別，我要依其中的國、英、數成績相加來排序

那要怎麼排比較好？這邊提供一個實作可排序的泛型類別的方式。

首先先稍微說明一下什麼叫二元樹：

二元樹是一種資料結構，由於要整個講完可能要很大篇幅，又會離題，因此我自己是把

二元樹想像成一個有規則的擺放資料的資料結構。從一個節點開始往下延伸。

例如我想要的二元樹規則是，跟第一個節點比較大小，比結點小就往左走，否則就

往右走。如果現在往左走，而左邊的子結點又是空的話，就占下來，反之，如果有人占

著，就在跟它比大小，然後決定要往左還往右，一直重複直到找到自己的位置。

如圖：

在閱讀的時候，就是從最下層開始，依照左、中、右，依序列出來，就可以發現，

是一個有規則的排序。可以練習隨便寫一串數字，然後用2元樹畫出來，如果都正確

那差不多就懂了。

接下來就把上面的概念寫成一個泛型的類別，看下面的程式碼說明：


public class Tree<TItem> where TItem : IComparable<TItem>      
        //where TItem : IComparable<TItem>的意思是 
        //傳進來的TItem型別必須實作IComparable<>介面
    {                                                              
       
        //三個public的欄位
        public TItem NodeData { get; set; }
        public Tree<TItem> LeftTree { get; set; }
        public Tree<TItem> RightTree { get; set; }

        //只有一個建構子，必須傳入<TItem>型別的物件
        public Tree(TItem nodeValue)
        {
            //初始化
            this.NodeData = nodeValue;
            this.LeftTree = null;
            this.RightTree = null;
        }

        //做一個Insert()的方法，傳入的參數為<TItem>型別的物件
        public void Insert(TItem newItem)
        {
            TItem currentNodeValue = this.NodeData;
            
            //跟結點比大小，如果比結點小就往左走，比結點大就往右走。
            //注意這邊的CompareTo()方法，就是等等傳入類別必須實作IComparable<TItem>介面
            //的CompareTo()方法
            if (currentNodeValue.CompareTo(newItem) > 0)
            {
                //如果左結點是空的，就占下來，反之，則在跟下一層的節點比，也就是遞迴直到找到位置為止
                if (this.LeftTree == null)
                {
                    this.LeftTree = new Tree<TItem>(newItem);
                }
                else
                {
                    this.LeftTree.Insert(newItem);
                }
            }
            else
            {
                //如果右結點是空的，就占下來，反之，則在跟下一層的節點比，也就是遞迴直到找到位置為止
                if (this.RightTree == null)
                {
                    this.RightTree = new Tree<TItem>(newItem);
                }
                else
                {
                    this.RightTree.Insert(newItem);
                }
            }
        }


        //做一個WalkTree()方法，依左中右的順序從最下層開始找二元樹的節點。
        //這個方法是讓我們可以印出二元樹各節點的值。
        public void WalkTree()
        {
            if (this.LeftTree != null)
            {
                this.LeftTree.WalkTree();
            }

            Console.WriteLine(this.NodeData.ToString());

            if (this.RightTree != null)
            {
                this.RightTree.WalkTree();
            }
        }
    }

整段Code看起來有點複雜，不過如果了解我們當初對二元樹的定義的話，就可以用很直觀的方式寫出來。

做好之後，接下來就簡單了，只要把我們要傳入的類別，實作IComparable<T>這個介面，

就可以用自定的排序規則來排序了。我下面用一個算員工工資的類別來舉例：


public class Employee : IComparable<Employee>
    {
        //三個私有欄位，分別是名字，時薪，跟工時
        private string name { get; set; }
        private int salary { get; set; }
        private int hour { get; set; }

        //只有一個建構子，傳入員工姓名，時薪跟工時
        public Employee(string name, int salary, int hour)
        {
            this.name = name;
            this.salary = salary;
            this.hour = hour;
        }

        //override  ToString()方法，傳回某某某的薪水為多少元
        public override string ToString()
        {
            return this.name+" 的薪水為: "+this.hour * this.salary+"元";
        }


        //實作IComparable<Employee>介面的方法。
        #region IComparable<Employee> 成員

        //這邊的方法，就可以自己定義要怎麼排序，像我這個例子就是用時薪*工時的結果去排
        public int CompareTo(Employee other)
        {
            if (this.hour * this.salary == other.salary * other.hour) { return 0; }
            if (this.hour * this.salary > other.salary * other.hour) { return 1; }
            return -1;
        }

        #endregion
    }

下面就直接用主控台程式來測試結果：


static void Main(string[] args)
        {
            
            //先new出一個Employee物件叫a
            Employee a = new Employee("a",95,25);

            //以我們的二元樹類別，傳入的型別是Employee，預設建構子放a物件。
            Tree<Employee> tree1 = new Tree<Employee>(a);
            
            //下面就是測試隨便new幾個員工出來，然後用Insert方法放進二元樹裡。
            Employee b = new Employee("b", 120, 10);
            tree1.Insert(b);
            Employee c = new Employee("c", 500, 7);
            tree1.Insert(c);
            Employee d = new Employee("d", 95, 10);
            tree1.Insert(d);
            
            //將我們要的結果印出來
            tree1.WalkTree();
        }

很方便吧!寫好之後一勞永逸。只要有實作IComparable<T>，就可以丟進去。

例如int本來就有實作該介面，就可以直接丟進去。


            Tree<int> tree1 = new Tree<int>(6);
            tree1.Insert(5);
            tree1.Insert(3);
            tree1.Insert(8);
            tree1.Insert(-1);
            tree1.Insert(5);
            tree1.Insert(4);
           
            tree1.WalkTree();

結果就是：

沒看過的人可能會覺得很難懂(也可能是我表達能力不好啦...)

我也是今天才第一次知道這個寫法，花了兩個小時去理解然後邊看書邊寫出這些Code

不過想出這些資料結構或是演算法的人，一定都是天才，也花了很多時間去思考。

所以多花幾個小時去理解他，也是值得的啦。

回首頁