[游戏开发]数据结构（二）——代码实现树

/****************************************************
    文件：TestBinaryTree.cs
	作者：
    邮箱:
    日期：2022/3/30 14:9:23
	功能：Nothing
*****************************************************/

using UnityEngine;

public class TestBinaryTree : MonoBehaviour 
{

    private void Update()
    {
        if (Input.GetKeyDown(KeyCode.A))
        {
            Nodes<string> rootNode = Nodes<string>.BinTree();

            Debug.Log("前");
            Nodes<string>.PreOrder(rootNode);      
            Debug.Log("中");
            Nodes<string>.MidOrder(rootNode);
            Debug.Log("后");
            Nodes<string>.AfterOrder(rootNode);
            Debug.Log("层");
            Nodes<string>.LayerOrder(rootNode);

        }
    }
}
public class Nodes<T>
{
    T data;
    
    Nodes<T> lNode;
    
    Nodes<T> rNode;
    
    Nodes<T> pNode;

    public Nodes(T data) 
    {
        this.data = data;
    }

    /// <summary>
    /// 节点数据
    /// </summary>
    public T Data { get => data; set => data = value; }
    /// <summary> 
    /// 左节点
    /// </summary>
    public Nodes<T> LNode { get => lNode; set => lNode = value; }
    /// <summary>
    /// 右节点
    /// </summary>
    public Nodes<T> RNode { get => rNode; set => rNode = value; }

    /// <summary>
    /// 父节点
    /// </summary>
    public Nodes<T> PNode { get => pNode; set => pNode = value; }

    /// <summary>
    /// 前序遍历
    /// </summary>
    /// <param name="rootNode"></param>
    public static void PreOrder<T>(Nodes<T> rootNode)
    {
        if (rootNode!=null)
        {
            Debug.Log(rootNode.Data);
            PreOrder<T>(rootNode.LNode);
            PreOrder<T>(rootNode.RNode);
        }
    }

    /// <summary>
    /// 中序遍历
    /// </summary>
    /// <param name="rootNode"></param>
    public static void MidOrder<T>(Nodes<T> rootNode)
    {
        if (rootNode != null)
        {
            PreOrder<T>(rootNode.LNode);
            Debug.Log(rootNode.Data);
            PreOrder<T>(rootNode.RNode);
        }
    }

    /// <summary>
    /// 后序遍历
    /// </summary>
    /// <param name="rootNode"></param>
    public static void AfterOrder<T>(Nodes<T> rootNode)
    {
        if (rootNode != null)
        {
            PreOrder<T>(rootNode.LNode);
            PreOrder<T>(rootNode.RNode);
            Debug.Log(rootNode.Data);
        }
    }

    /// <summary>
    /// 层序遍历
    /// </summary>
    /// <param name="rootNode"></param>
    public static void LayerOrder<T>(Nodes<T> rootNode)
    {
        Nodes<T>[] nodes = new Nodes<T>[20];
        //前节点
        int front = -1;
        //后节点
        int rear = -1;

        if (rootNode!=null)
        {
            rear++;
            nodes[rear] = rootNode;
        }

        while (front != rear)
        {
            front++;
            rootNode = nodes[front];//第一个值赋值 
            Debug.Log(rootNode.Data);

            if (rootNode.LNode!=null)//左子树
            {
                rear++;
                nodes[rear] = rootNode.LNode;
            }

            if (rootNode.RNode != null)//右子树
            {
                rear++;
                nodes[rear] = rootNode.RNode;
            }
        }
    }

    /// <summary>
    /// 构造一个已知的二叉树
    /// </summary>
    /// <returns></returns>
    public static Nodes<string> BinTree()
    {
        Nodes<string>[] binTree = new Nodes<string>[8];
        binTree[0] = new Nodes<string>("A");
        binTree[1] = new Nodes<string>("B");
        binTree[2] = new Nodes<string>("C");
        binTree[3] = new Nodes<string>("D");
        binTree[4] = new Nodes<string>("E");
        binTree[5] = new Nodes<string>("F");
        binTree[6] = new Nodes<string>("G");
        binTree[7] = new Nodes<string>("H");

        binTree[0].LNode = binTree[1];
        binTree[0].RNode = binTree[2];
        binTree[1].LNode = binTree[3];
        binTree[1].RNode = binTree[4]; 
        binTree[2].LNode = binTree[5];
        binTree[2].RNode = binTree[6];
        binTree[3].LNode = binTree[7];

        return binTree[0];
    }
}

输出结果

前序：ABDHECFG（从上到下，从左到右）

中序：HDBEAFCG（先左节点--根--最后右节点）

后序：HDEBDGCA（先左--右--最后根节点）

层序：ABCDEFGH（从上到下，从左到右一层一层遍历）