日期：2023年 03月 05日

標籤： Algorithm Sort Paractical Algorithm C# Asp.NET Core

摘要：演算法-排序

第一部分：二元樹排序 - 介紹

Step 1：原理

Step 2：演算法流程圖

第二部分：圖解範例說明

Step 1：以整數陣列為例

初始內有5個值

第三部分：代碼

Step 1：二元樹排序代碼 - 呼叫進入點

輸入一組數列 inputItem 求出 result

public void Execute()
{
    List<int> inputItem = new() { 92, 17, 38, 59, 26, 39 };
    
    var execute = new BinaryTreeSort<int>();
    var result =  execute.BinarySorting(inputItem);
}

Step 2：二元樹排序代碼 - 主程式

主要三個流程
1. 輸入陣列建立成二元樹
2. 中序遍歷該樹，中序的結果為由小而大
※中序，根節點往左子樹遍歷，經過根節點，然後右子樹，經過的點記錄

public class BinaryTreeSort<T> where T : IComparable<T>
{
    public List<int> BinarySorting(List<int> inputItem)
    {
        //1. 數組第一個節點為根結點
        TreeNode root = new TreeNode(inputItem[0]);
        //2. 建構二元樹
        for (int index = 1; index < inputItem.Count(); index++)
            BuildTree(root, inputItem[index]);            
        //3. 中序遍歷樹取值結果
        var result = new List<int>();
        InOrderTraversal(root, ref result);
        return result;
    }
    /// <summary>
    /// 建構二元樹
    /// </summary>
    public void BuildTree(TreeNode node, int value)
    {
        //左節點
        if (value < node.value)
        {
            if (node.LeftNode == null)
            {
                node.LeftNode = new TreeNode(value);
            }
            else
            {
                BuildTree(node.LeftNode, value);
            }
        }
        else//右節點
        {
            if (node.RightNode == null)
            {
                node.RightNode = new TreeNode(value);
            }
            else
            {
                BuildTree(node.RightNode, value);
            }
        }
    }
    /// <summary>
    /// 中序
    /// </summary>
    private void InOrderTraversal(TreeNode node,ref List<int> container)
    {
        //走到Null直接捨棄
        if (node == null)            
            return;
        InOrderTraversal(node.LeftNode, ref container);
        container.Add(node.value);
        InOrderTraversal(node.RightNode, ref container);
    }
}


/// <summary>
/// 二元樹節點結構
/// </summary>
public class TreeNode
{
    public int value;
    public TreeNode LeftNode;
    public TreeNode RightNode;
    public TreeNode(int value)
    {
        this.value = value;
        this.LeftNode = null;
        this.RightNode = null;
    }
}