여러 개의 하위가있는 트로프를 트래버스 할 수 있습니까?

Question

저는 현재 partioning 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

첫째, 쿼드 트리 생성기를 살펴의 생성자 내부의 루프는 자식 노드 객체를 재생성하고 생성 된 객체를 버리고 있습니다. 그래서 반복을 위해 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 
    } 
} 

Answer 2

BFS, DFS, 오일러 순회 등, 이들의 그것을 할 것입니다 :

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

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

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