/// <summary>
/// 線索二叉樹 節點
/// </summary>
/// <typeparam name="T"></typeparam>
public class ClueTreeNode<T>
{
    /// <summary>
    /// 內容
    /// </summary>
    public T data { get; set; }
    /// <summary>
    /// 左樹
    /// </summary>
    public ClueTreeNode<T> leftNode { get; set; }
    /// <summary>
    /// 右樹
    /// </summary>
    public ClueTreeNode<T> rightNode { get; set; }
    /// <summary>
    /// 0 標識左樹 1 標識 當前節點的前驅
    /// </summary>
    public int leftTag { get; set; }
    /// <summary>
    /// 0標識右樹 1 標識 當前節點的後繼
    /// </summary>
    public int rightTag { get; set; }

    public ClueTreeNode()
    {
        data = default(T);
        leftNode = null;
        rightNode = null;
    }

    public ClueTreeNode(T item)
    {
        data = item;
        leftNode = null;
        rightNode = null;
    }
}

/// <summary>
/// 線索化 二叉樹 
/// 
/// 為什麼線索化二叉樹？
/// 第一：對於二叉樹，如果有n個節點，每個節點有指向左右孩子的兩個指針域，所以一共有2n個指針域。
/// 而n個節點的二叉樹一共有n-1條分支線數，也就是說，其實是有 2n-(n-1) = n+1個空指針。
/// 這些空間不存儲任何事物，白白浪費記憶體的資源。
/// 第二：對於二叉樹的遍歷，我們知道每個節點的前驅與後繼，但是這是建立在遍歷的基礎上。
/// 否則我們只知道後續的左右子樹。
/// 第三：對於二叉樹來說，從結構上來說是單向鏈表，引入前驅後繼後，線索化二叉樹可以認為是雙向鏈表。
/// </summary>
/// <typeparam name="T"></typeparam>
public class ClueBinaryTree<T>
{
    /// <summary>
    /// 樹根節
    /// </summary>
    private ClueTreeNode<T> head { get; set; }
    /// <summary>
    /// 線索化時作為前驅轉存
    /// </summary>
    private ClueTreeNode<T> preNode { get; set; }

    public ClueBinaryTree(){
        head = new ClueTreeNode<T>();
    }
    public ClueBinaryTree(T val){
        head = new ClueTreeNode<T>(val);
    }


    public ClueTreeNode<T> GetRoot(){
        return head;
    }

    /// <summary>
    /// 插入左節點
    /// </summary>
    /// <param name="val"></param>
    /// <param name="node"></param>
    /// <returns></returns>
    public ClueTreeNode<T> AddLeftNode(T val, ClueTreeNode<T> node){
        if (node == null)
            throw new ArgumentNullException("參數錯誤");
        ClueTreeNode<T> treeNode = new ClueTreeNode<T>(val);
        ClueTreeNode<T> childNode = node.leftNode;
        treeNode.leftNode = childNode;
        node.leftNode = treeNode;
        return treeNode;
    }

    /// <summary>
    /// 插入右節點
    /// </summary>
    /// <param name="val"></param>
    /// <param name="node"></param>
    /// <returns></returns>
    public ClueTreeNode<T> AddRightNode(T val, ClueTreeNode<T> node){
        if (node == null)
            throw new ArgumentNullException("參數錯誤");
        ClueTreeNode<T> treeNode = new ClueTreeNode<T>(val);
        ClueTreeNode<T> childNode = node.rightNode;
        treeNode.rightNode = childNode;
        node.rightNode = treeNode;
        return treeNode;
    }
    /// <summary>
    /// 刪除當前節點的 左節點
    /// </summary>
    /// <param name="node"></param>
    /// <returns></returns>
    public ClueTreeNode<T> DeleteLeftNode(ClueTreeNode<T> node){
        if (node == null || node.leftNode == null)
            throw new ArgumentNullException("參數錯誤");
        ClueTreeNode<T> leftChild = node.leftNode;
        node.leftNode = null;
        return leftChild;
    }

    /// <summary>
    /// 刪除當前節點的 右節點
    /// </summary>
    /// <param name="node"></param>
    /// <returns></returns>
    public ClueTreeNode<T> DeleteRightNode(ClueTreeNode<T> node){
        if (node == null || node.rightNode == null)
            throw new ArgumentNullException("參數錯誤");
        ClueTreeNode<T> rightChild = node.rightNode;
        node.rightNode = null;
        return rightChild;
    }



    /// <summary>
    /// 中序遍歷線索化二叉樹
    /// </summary>
    public void MiddlePrefaceTraversal(){
        ClueTreeNode<T> node = head;
        while (node != null)
        {
            //判斷是否是
            while (node.leftTag == 0)
            {
                node = node.leftNode;
            }
            Console.Write($" {node.data}");
            while (node.rightTag == 1)
            {
                node = node.rightNode;
                Console.Write($" {node.data}");
            }
            node = node.rightNode;
        }
    }
    /// <summary>
    /// 線索化二叉樹
    /// </summary>
    /// <param name="node"></param>
    public void MiddleClueNodes(ClueTreeNode<T> node){
        if (node == null)
        {
            return;
        }
        //線索化左子樹
        MiddleClueNodes(node.leftNode);
        //當左樹為空時，指向前驅，標識為 1
        if (node.leftNode == null)
        {
            node.leftNode = preNode;
            node.leftTag = 1;
        }
        //如果 前驅的右樹不為空
        if (preNode != null && preNode.rightNode == null)
        {
            preNode.rightNode = node;
            preNode.rightTag = 1;
        }
        preNode = node;
        //線索化右子樹
        MiddleClueNodes(node.rightNode);
    }
}

//創建樹
ClueBinaryTree<string> clueBinaryTree = new ClueBinaryTree<string>("A");
ClueTreeNode<string> tree1 = clueBinaryTree.AddLeftNode("B", clueBinaryTree.GetRoot());
ClueTreeNode<string> tree2 = clueBinaryTree.AddRightNode("C", clueBinaryTree.GetRoot());
ClueTreeNode<string> tree3 = clueBinaryTree.AddLeftNode("D", tree1);
clueBinaryTree.AddRightNode("E", tree1);
clueBinaryTree.AddLeftNode("F", tree2);
clueBinaryTree.AddRightNode("G", tree2);

clueBinaryTree.MiddleClueNodes(clueBinaryTree.GetRoot());

Console.Write("中序遍歷");
clueBinaryTree.MiddlePrefaceTraversal();

中序遍歷 D B E A F C G