在统一问题中展示二叉树

Question

我在统一中做了一个函数，它接受一个 Binode - 并将它变成一个 2d 树，但这里的问题是：我所谓的显示树的想法是这样的：

做一个递归函数，每次level加1，同时给函数传一个bool(旧节点是右还是左)，如果为真就通过 level * 55 获取树的根和 - y，那么它要么是 x = level * 55，如果它是对的，如果它是左的 x = level * -55.

现在的问题是假设我有一棵有 3 层的树，然后如果我将一个右节点放在左树上，它只会把它放在最右的节点上并且它会重叠，有点难文字说明，希望大家理解。

这里是存储库： git

代码：

public void GenrateTreeUI(BinNode<int> t, bool right, int Level)
{

    if (Level == 0)
    {
        cir = Instantiate(CirclePrefab, new Vector2(0, 0), Quaternion.identity);
        t.SetGO(cir);
        cir.transform.SetParent(canvas.transform);
        cir.GetComponent<Image>().color = Color.black;
        roottr = cir.GetComponent<RectTransform>();
        Value = cir.GetComponentInChildren<TMP_Text>();


        roottr.anchoredPosition = new Vector2(-11, 213);
        Value.text = t.GetValue().ToString();
        Value.color = Color.white;
    }
    else
    {
        if (!right)
        {
            cir = Instantiate(CirclePrefab, new Vector2(0, 0), Quaternion.identity);
            cir.transform.SetParent(canvas.transform);
            t.SetGO(cir);
            cir.GetComponentInChildren<TMP_Text>().text = t.GetValue().ToString();
            cir.GetComponent<RectTransform>().anchoredPosition = new Vector2(roottr.anchoredPosition.x - Level * 55,
                roottr.anchoredPosition.y - (Level * 55));
        }
        else
        {
            cir = Instantiate(CirclePrefab, new Vector2(0, 0), Quaternion.identity);
            cir.transform.SetParent(canvas.transform);
            t.SetGO(cir);
            cir.GetComponentInChildren<TMP_Text>().text = t.GetValue().ToString();
            cir.GetComponent<RectTransform>().anchoredPosition = new Vector2(roottr.anchoredPosition.x + Level * 55,
                roottr.anchoredPosition.y - Level * 55);
        }
    }


    if (t.HasLeft())
    {

        GenrateTreeUI(t.GetLeft(), false, Level + 1);
        GenrateWire(cir.GetComponent<RectTransform>().anchoredPosition, GetFutreNode(t.GetLeft(), Level, false));

    }
    if (t.HasRight())
    {

        GenrateTreeUI(t.GetRight(), true, Level + 1);
        GenrateWire(cir.GetComponent<RectTransform>().anchoredPosition, GetFutreNode(t.GetRight(), Level, true));

    }

}

感谢您的帮助！

Answer 1

在这里给出答案之前，我会再次建议一些重构和修复：

首先你的 CreateRndTree 是错误的 ;)

public void CrateRndTree(int levels, BinNode<int> save_node)
{
    BinNode<int> newNode = null;
    for (int i = 0; i < levels; i++)
    {
        newNode = new BinNode<int>(Random.Range(1, 20));
        save_node.SetLeft(newNode);
        newNode = new BinNode<int>(Random.Range(1, 20));
        save_node.SetRight(newNode);
        save_node = newNode;
    }
}

你创建了两个新的子节点，但只在最后一个创建的节点（右）上设置了 left 和 right => 左边的树永远不会有任何子节点。

我会像

这样递归地做

private static void CreateRndTree(int levels, BinNode<int> rootNode)
{
    if (levels <= 0)
    {
        return;
    }

    var leftNode = new BinNode<int>(Random.Range(1, 20), rootNode);
    var rightNode = new BinNode<int>(Random.Range(1, 20), rootNode);

    rootNode.SetChildren(leftNode, rightNode);

    CreateRndTree(levels - 1, leftNode);
    CreateRndTree(levels - 1, rightNode);
}

然后作为最后一次，我将在圆形预制件上有一个适当的 class Circle，例如

public class Circle : MonoBehaviour
{
    [SerializeField] private Image image;
    [SerializeField] private RectTransform rectTransform;
    [SerializeField] private TMP_Text text;

    public Image Image
    {
        get
        {
            if (image) return image;

            image = GetComponent<Image>();

            return image;
        }
    }

    public RectTransform RectTransform
    {
        get
        {
            if (rectTransform) return rectTransform;

            rectTransform = GetComponent<RectTransform>();

            return rectTransform;
        }
    }

    public TMP_Text Text
    {
        get
        {
            if (text) return text;

            text = GetComponentInChildren<TMP_Text>();

            return text;
        }
    }
}

并在您的 BinNode 中存储它而不是 GameObject 以摆脱重复的 GetComponent 调用。

然后对于定位，我宁愿在节点本身中实现一个 getter 来计算它们的子级别。

我还会存储父节点，而是将新节点相对于父节点定位，而不是总是必须从根节点开始计算

public class BinNode<T>
{
    ...

    private BinNode<T> parent;
    public BinNode<T> Parent => parent;

    // proper class that will be sitting on your circle prefab
    public Circle circle;
    
    public BinNode(T value, BinNode<T> parent = null)
    {
        this.value = value;
        this.parent = parent;
    }

    public int GetChildLevels()
    {
        var rightChildLevels = right == null ? 0 : 1 + right.GetChildLevels();
        var leftChildLevels = left == null ? 0 : 1 + left.GetChildLevels();

        return Mathf.Max(rightChildLevels, leftChildLevels);
    }
    
    ...
}

然后在获取节点位置时执行

public float spacing = 55;

public Vector2 GetNodePosition(BinNode<int> node, bool right)
{
    var subLevels = node.GetChildLevels();

    // simply get the position relative to the parent node
    // otherwise you would need to sum them up all the time
    var parentRectTransform = node.Parent.Cirlce.RectTransform;

    return parentRectTransform.anchoredPosition + new Vector2(spacing * (Mathf.Pow(2, subLevels)) * (right ? 1 : -1), -spacing);
}

3 级

4 级

5 级

作为上次我为此做了一个pull request ;)

在统一问题中展示二叉树

Showcasing a binary tree in unity problom

c#

simulation

binary-tree

unity3d

nodes