我如何遍历具有多个孩子的树？

Question

我目前正在研究 2D 分区 Space。

Tree with Rectangles

这是我的树

    private class TreeNode
    {
        public Rectangle region;
        public TreeNode childQ1;
        public TreeNode childQ2;
        public TreeNode childQ3;
        public TreeNode childQ4;

        public TreeNode(Rectangle region)
        {
            this.region = region;
        }
    }

这就是我对树进行分区的方式，我对其进行了调试，一切看起来都很好

public class RegionTree
{
    private class TreeNode
    {
        public Rectangle region;
        public TreeNode childQ1;
        public TreeNode childQ2;
        public TreeNode childQ3;
        public TreeNode childQ4;

        public TreeNode(Rectangle region)
        {
            this.region = region;
        }
    }

    TreeNode root;

    public RegionTree(int RegionWidth, int RegionHeight, byte depth)
    {
        root = new TreeNode(new Rectangle(0, 0, RegionWidth, RegionHeight));
        GenerateNodes(root, depth);
    }

    private void GenerateNodes(TreeNode node, int depth)
    {
        for (int i = 0; i < depth; i++)
        {
            int halfWidth = node.region.Width / 2;
            int halfHeight = node.region.Height / 2;

            TreeNode childQ1 = new TreeNode(new Rectangle(node.region.X, node.region.Y, halfWidth, halfHeight));
            node.childQ1 = childQ1;
            TreeNode childQ2 = new TreeNode(new Rectangle(node.region.X + halfWidth, node.region.Y, halfWidth, halfHeight));
            node.childQ2 = childQ2;
            TreeNode childQ3 = new TreeNode(new Rectangle(node.region.X, node.region.Y + halfHeight, halfWidth, halfHeight));
            node.childQ3 = childQ3;
            TreeNode childQ4 = new TreeNode(new Rectangle(node.region.X + halfWidth, node.region.Y + halfHeight, halfWidth, halfHeight));
            node.childQ4 = childQ4;

            GenerateNodes(childQ1, i);
            GenerateNodes(childQ2, i);
            GenerateNodes(childQ3, i);
            GenerateNodes(childQ4, i);
        }
    }
}

我想遍历所有节点和子节点并绘制矩形，但需要一些帮助。

Answer 1

BFS、DFS、Euler Traversal 等，其中任何一个都可以：

https://en.wikipedia.org/wiki/Euler_tour_technique

https://en.wikipedia.org/wiki/Breadth-first_search

https://en.wikipedia.org/wiki/Depth-first_search

Answer 2

首先看一下四叉树生成器，生成器内部的循环是重新创建子节点对象并丢弃生成的对象。因此对于迭代 0，将创建 4 个新对象和后续子对象。对于迭代 1，这些对象被新对象覆盖，而以前的值被垃圾收集。你要做的是开始：

    private void GenerateNodes(TreeNode node, int depth)
    {
        if(depth < 0) return;
        int halfWidth = node.region.Width / 2;
        int halfHeight = node.region.Height / 2;

        TreeNode childQ1 = new TreeNode(new Rectangle(node.region.X, node.region.Y, halfWidth, halfHeight));
        node.childQ1 = childQ1;
        TreeNode childQ2 = new TreeNode(new Rectangle(node.region.X + halfWidth, node.region.Y, halfWidth, halfHeight));
        node.childQ2 = childQ2;
        TreeNode childQ3 = new TreeNode(new Rectangle(node.region.X, node.region.Y + halfHeight, halfWidth, halfHeight));
        node.childQ3 = childQ3;
        TreeNode childQ4 = new TreeNode(new Rectangle(node.region.X + halfWidth, node.region.Y + halfHeight, halfWidth, halfHeight));
        node.childQ4 = childQ4;

        GenerateNodes(childQ1, depth - 1);
        GenerateNodes(childQ2, depth - 1);
        GenerateNodes(childQ3, depth - 1);
        GenerateNodes(childQ4, depth - 1);
    }
}

好的，现在我们有了一个可以工作的生成器，走这些树叶的方法使用类似的代码。您可以根据要打印的顺序以不同的方式走它们。

    private void WalkNodes(TreeNode node)
    {   
        if(node == null) return;
        //do something here will write root tracing to the left, 
        //which will draw your rectangles from the outside in, 
        //finishing each bottom left before starting the next
        WalkNodes(node.childQ1);
        WalkNodes(node.childQ2);
        WalkNodes(node.childQ3);
        WalkNodes(node.childQ4);
        //do something here to traverse the tree from the last 
        //leaf back to the first, which will draw your rectangles 
        //from the inside to out, finishing the right upper first
    }
}

我如何遍历具有多个孩子的树？

How can I Traverse through a Tree with Multiple childs?

c#

tree

spatial