這篇文章將為大家詳細講解有關怎么在C#中使用二叉樹計算用戶積分，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

創(chuàng)新互聯(lián)，專注為中小企業(yè)提供官網(wǎng)建設、營銷型網(wǎng)站制作、響應式網(wǎng)站設計、展示型網(wǎng)站制作、網(wǎng)站設計等服務，幫助中小企業(yè)通過網(wǎng)站體現(xiàn)價值、有效益。幫助企業(yè)快速建站、解決網(wǎng)站建設與網(wǎng)站營銷推廣問題。

假設積分范圍是0-5，我們對它不斷進行中位分區(qū)直到不能分為止，形成如下一棵二叉樹：

其中每個樹節(jié)點包含2個信息：節(jié)點范圍range[min，max) 和命中數(shù)量計數(shù)器count ，可以看到葉子節(jié)點的range一定是相鄰的2個數(shù)。

假如現(xiàn)在有一個積分3要插入到樹中，該如何操作呢？當前節(jié)點從根節(jié)點開始，分別判斷是否包含于左右子節(jié)點，如果包含的話當前節(jié)點改為這個子節(jié)點，同時計數(shù)器加1，然后再次進行相同判斷，直到遍歷到葉子節(jié)點為止，遍歷順序如下：

再依次插入1和4，二叉樹的演變情況為：

數(shù)據(jù)放進去后怎么判斷它是排名多少呢？還是從根節(jié)點開始，判斷它是否包含于左子節(jié)點，如果包含的話說明它比右子節(jié)點中count個數(shù)?。ㄔ赾ount名之外），然后再往下一級做同樣的判斷；如果包含于右子節(jié)點那就繼續(xù)往下判斷，直到碰到葉子節(jié)點為止。依次累加count最后加上葉子節(jié)點占的一位就得到了它在這棵樹里的排名，以1為例演示判斷步驟（排名為2+1=3）：

好了，一切就緒，只欠代碼。

擼碼實現(xiàn)

樹結(jié)構(gòu)由節(jié)點構(gòu)成，那首先設計一個節(jié)點類：

  /// <summary>
  /// 樹節(jié)點對象
  /// </summary>
  public class TreeNode
  {
    /// <summary>
    /// 節(jié)點的最小值
    /// </summary>
    public int ValueFrom { get; set; }

    /// <summary>
    /// 節(jié)點的大值
    /// </summary>
    public int ValueTo { get; set; }

    /// <summary>
    /// 在節(jié)點范圍內(nèi)的數(shù)量
    /// </summary>
    public int Count { get; set; }

    /// <summary>
    /// 節(jié)點高度（樹的層級）
    /// </summary>
    public int Height { get; set; }

    /// <summary>
    /// 父節(jié)點
    /// </summary>
    public TreeNode Parent { get; set; }

    /// <summary>
    /// 左子節(jié)點
    /// </summary>
    public TreeNode LeftChildNode { get; set; }

    /// <summary>
    /// 右子節(jié)點
    /// </summary>
    public TreeNode RightChildNode { get; set; }
  }

樹節(jié)點的屬性主要包含范圍值ValueFrom、ValueTo、計數(shù)器Count、左子節(jié)點LeftChildNode和右子節(jié)點RightChildNode，由此組成一個有層次的樹結(jié)構(gòu)。
然后就是定義我們的樹對象了，它的核心字段就是代表源頭的根節(jié)點：

  public class RankBinaryTree
  {
    /// <summary>
    /// 根節(jié)點
    /// </summary>
    private TreeNode _root;

  }

根據(jù)前面的算法思想，創(chuàng)建樹的時候要用積分范圍初始化所有節(jié)點，這里約定了最小積分為0，通過構(gòu)造函數(shù)傳入大值并創(chuàng)建樹結(jié)構(gòu)：

   /// <summary>
    /// 構(gòu)造函數(shù)初始化根節(jié)點
    /// </summary>
    /// <param name="max"></param>
    public RankBinaryTree(int max)
    {
      _root = new TreeNode() { ValueFrom = 0, ValueTo = max+1, Height = 1 };
      _root.LeftChildNode = CreateChildNode(_root, 0, max / 2);
      _root.RightChildNode = CreateChildNode(_root, max / 2, max);
    }

    /// <summary>
    /// 遍歷創(chuàng)建子節(jié)點
    /// </summary>
    /// <param name="current"></param>
    /// <param name="min"></param>
    /// <param name="max"></param>
    /// <returns></returns>
    private TreeNode CreateChildNode(TreeNode current, int min, int max)
    {
      if (min == max) return null;
      var node = new TreeNode() { ValueFrom = min, ValueTo = max, Height = current.Height + 1 };
      node.Parent = current;
      int center = (min + max) / 2;
      if (min < max - 1)
      {
        node.LeftChildNode = CreateChildNode(node, min, center);
        node.RightChildNode = CreateChildNode(node, center, max);
      }
      return node;
    }

有了樹以后下一步就是往里面插入數(shù)據(jù)，根據(jù)前面介紹的邏輯：

  /// <summary>
    /// 往樹中插入一個值
    /// </summary>
    /// <param name="value"></param>
    public void Insert(int value)
    {
      InnerInsert(_root, value);
      _data.Add(value);
    }

    /// <summary>
    /// 子節(jié)點判斷范圍遍歷插入
    /// </summary>
    /// <param name="node"></param>
    /// <param name="value"></param>
    private void InnerInsert(TreeNode node, int value)
    {
      if (node == null) return;
      //判斷是否在這個節(jié)點范圍內(nèi)
      if (value >= node.ValueFrom && value < node.ValueTo)
      {
        //更新節(jié)點總數(shù)信息
        node.Count++;
        //更新左子節(jié)點
        InnerInsert(node.LeftChildNode, value);
        //更新右子節(jié)點
        InnerInsert(node.RightChildNode, value);
      }
    }

下一步提供方法獲取指定值在樹中的排名：

   /// <summary>
    /// 從樹中獲取總排名
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public int GetRank(int value)
    {
      if (value < 0) return 0;
      return InnerGet(_root, value);
    }

    /// <summary>
    /// 遍歷子節(jié)點獲取累計排名
    /// </summary>
    /// <param name="node"></param>
    /// <param name="value"></param>
    /// <returns></returns>
    private int InnerGet(TreeNode node, int value)
    {
      if (node.LeftChildNode == null || node.RightChildNode == null) return 1;
      if (value >= node.LeftChildNode.ValueFrom && value < node.LeftChildNode.ValueTo)
      {
        //當這個值存在于左子節(jié)點中時，要累加右子節(jié)點的總數(shù)（表示這個數(shù)在多少名之后）
        return node.RightChildNode.Count + InnerGet(node.LeftChildNode, value);
      }
      else
      {
        //如果在右子節(jié)點中就繼續(xù)遍歷
        return InnerGet(node.RightChildNode, value);
      }
    }

到這里，核心功能已經(jīng)實現(xiàn)了?？紤]到有積分更新的情況，我們可以加上節(jié)點更新和刪除的方法。刪除很容易，和插入逆向操作就行，更新就更容易了，把舊節(jié)點刪除再計算出新值插入即可，完整代碼已經(jīng)上傳到Github。
這棵樹究竟效率如何，下面我們跑個分看看。

測試走起來

在測試程序中，我模擬了積分范圍0-1000000的場景，這個范圍幾乎覆蓋了真實業(yè)務中90%的積分值，100萬積分以上的會員系統(tǒng)應該比較少見了。

而會員的積分值分布也是不均勻的，一般來說擁有小額積分的用戶比例大，積分值越高所占用戶比例越小。
在程序中我假設有100萬個會員，其中50W用戶積分都在100以內(nèi)，30W用戶積分在100-10000，15W用戶積分在10000-50000，5W用戶積分在50000以上。

下面是各個操作的耗時時間：

可以看到，這個效率不是一般的快啊，其中獲取排名的查詢時間幾乎可以忽略不計。
這時候有人問了，這么多數(shù)據(jù)會不會非常吃內(nèi)存，下面用任務管理器分別查看不使用樹和使用樹的內(nèi)存情況：

運行環(huán)境是.NetCore3.0 Console，測試主機配置情況：

關于怎么在C#中使用二叉樹計算用戶積分就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

文章標題：怎么在C#中使用二叉樹計算用戶積分-創(chuàng)新互聯(lián)
URL標題：http://www.rwnh.cn/article46/dghphg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供動態(tài)網(wǎng)站、品牌網(wǎng)站建設、網(wǎng)站營銷、網(wǎng)站策劃、標簽優(yōu)化、軟件開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)