バイナリ検索ツリーで兄弟を接続する

Question

バイナリ検索ツリーの兄弟を接続しようとしています。ロジックはConnect（）メソッドで見つけることができます。私の質問は、それを行うためのより良い方法はありますか？私は2つのキューを使用してロジックを実装することで過度な作業をしていますか？

using System; 
using System.Diagnostics; 
using System.Collections.Generic; 
using System.Text; 

namespace SampleCSParallel 
{ 
    class Tree 
    { 
     public Tree left = null; 
     public Tree right = null; 
     public Tree sibling = null; 
     public int _data; 

     Tree(int data) 
     { 
      _data = data; 
      left = null; 
      right = null; 
     } 

     public Tree Left 
     { 
      get 
      { 
       return this.left; 
      } 
     } 

     public Tree Right 
     { 
      get 
      { 
       return this.right; 
      } 
     } 

     public Tree AddNode(Tree node, int data) 
     { 
      if (node == null) 
      { 
       node = new Tree(data); 
       return node; 
      } 
      else if (node._data <= data) 
      { 
       node.left = AddNode(node.left, data); 
      } 
      else if (node._data > data) 
      { 
       node.right = AddNode(node.right, data); 
      } 
      return node; 
     } 

     public static Tree CreateTree(Tree node, int depth, int start) 
     { 
      if (node == null) 
       node = new Tree(start); 
      if (depth > 1) 
      { 
       node.left = CreateTree(node.left, depth - 1, start + 1); 
       node.right = CreateTree(node.right, depth - 1, start + 1); 
      } 
      return node; 
     } 
    } 

    class Program 
    { 
     static void Main(string[] args) 
     { 
      //Tree node = null; 
      Tree tr = Tree.CreateTree(null, 4, 1); 
      Stopwatch sw = Stopwatch.StartNew(); 
      int total = WalkTree(tr);   
      TimeSpan ts = sw.Elapsed; 
      Console.WriteLine("in {0} sec", ts.Seconds); 
      Console.WriteLine("total:{0}", total); 
      connect(tr); 
      Console.ReadLine(); 
     }   

     static void connect(Tree root) 
     { 
      Queue<Tree> nodeQueue = new Queue<Tree>();   
      nodeQueue.Enqueue(root); 
      Console.WriteLine(root._data); 
      connectSiblings(nodeQueue); 
     } 

     static void connectSiblings(Queue<Tree> nodeQueue) 
     { 
      Queue<Tree> childrenQueue = new Queue<Tree>();    
      StringBuilder MsgStr = new StringBuilder(); 
      bool done = false; 

      while (!done) 
      { 
       while (nodeQueue.Count != 0) 
       { 

        Tree parent = nodeQueue.Dequeue();     
        if (parent.left != null) 
        { 
         childrenQueue.Enqueue(parent.left); 
        } 
        if (parent.right != null) 
        { 
         childrenQueue.Enqueue(parent.right); 
        }   
       } 

       Tree prevNode = null; 
       Tree currNode = null; 
       while (childrenQueue.Count != 0) 
       { 
        currNode = childrenQueue.Dequeue(); 
        nodeQueue.Enqueue(currNode);     

        if (prevNode != null) 
        {      
         MsgStr.Append(string.Format("\t{0}",currNode._data));     
        } 
        else 
        { 
         prevNode = currNode;       
         MsgStr.Append(string.Format("\t{0}",prevNode._data)); 
        }   
       }     
       Console.WriteLine(MsgStr.ToString()); 
       MsgStr.Remove(0, MsgStr.Length); 

       if (nodeQueue.Count == 0 && childrenQueue.Count == 0) 
        done = true; 
      } 
     } 
    } 
} 

Answer 1

これは、前のノード、深さごとに1の配列を使用して、再帰的に兄弟を接続することが可能です：

void connect(Node node, int depth, List<Node> prev) 
{ 
    if (node == null) 
    return; 
    if(prev.Size <= depth) 
    prev.Add(depth); 
    else { 
    prev[depth].sibling = node; 
    prev[depth] = node; 
    } 
    connect(node.left, depth+1, prev); 
    connect(node.right, depth+1, prev); 
} 

Answer 2

私はO（1）のスペース複雑で質問をしようとしている中でJavaの...

public void setSibling(Node root){ 
     Node start = null; 
     if (root == null) return; 
     do{ 
      if(root.left!=null) { 
       root.left.sibling = getNextSibling(root,"left"); 
       if(start == null) start = root.left; 
      } 
      if(root.right!=null){ 
       root.right.sibling = getNextSibling(root,"right"); 
       if(start == null) start = root.right; 
      } 
      root = root.sibling; 
     }while(root!=null); 
     root = start; 
     setSibling(root); 

    } 


    public Node getNextSibling(Node root,String marker){ 
     if (marker.equals("left")){ 
      if(root.right!=null)return root.right; 
     } 
     Node nextSibling = null; 
     root = root.sibling; 
     while(nextSibling == null && root != null){ 
      if (root.left != null) nextSibling = root.left; 
      else if (root.right != null) nextSibling = root.right; 
      else root = root.sibling; 
     } 
     return nextSibling; 
    } 

そのエレガントではないかもしれないが、それは動作します。..