如何从顶层开始逐层打印二进制树中的数据?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (42)

我的解决方案。它使用队列。

public Void BFS()    
{   
   Queue q = new Queue();    
   q.Enqueue(root);    
   Console.WriteLine(root.Value);  

   while (q.count > 0)  
   {  
      Node n = q.DeQueue();  
      if (n.left !=null)  
       {  
          Console.Writeln(n.left);  
          q.EnQueue(n.left);  
        }   
       if (n.right !=null)  
       {  
          Console.Writeln(n.right);  
          q.EnQueue(n.right);  
        }   
    }
}    

有比这更好的解决方案(不使用队列)?

提问于
用户回答回答于

如下:

public Void BFS()    
{      
 Queue q = new Queue();
 q.Enqueue(root);//You don't need to write the root here, it will be written in the loop
 while (q.count > 0)
 {
    Node n = q.DeQueue();
    Console.Writeln(n.Value); //Only write the value when you dequeue it
    if (n.left !=null)
    {
        q.EnQueue(n.left);//enqueue the left child
    }
    if (n.right !=null)
    {
       q.EnQueue(n.right);//enque the right child
    }
 }
}

编辑

这是工作中的算法。假设你有这样一棵树:

     1
    / \
   2   3
  /   / \
 4   5   6

首先,根(1)将被排队。循环然后进入。队列(1)中的第一项出列并打印。1的孩子从左到右排队,队列现在包含{2,3}回到队列开始的第一个项目(2)出列并打印2的孩子从左到右排队,队列现在包含{3, 4}回到循环开始...

队列将在每个循环中包含这些值

1: {1}

2: {2, 3}

3: {3, 4}

4: {4, 5, 6}

5: {5, 6}

6: {6}

7:{} //空,循环终止

输出:

1

2

3

4

5

6

用户回答回答于

这是我的代码,它试图通过将NewLine节点附加到队列来完成相同的操作,

void PrintByLevel(Node *root)
{
   Queue q;
   Node *newline = new Node("\n");
   Node *v;
   q->enque(root);
   q->enque(newline);

   while(!q->empty()) {
      v = q->deque();
      if(v == newline) {
         printf("\n");
         if(!q->empty())
            q->enque(newline);
      }
      else {
         printf("%s", v->val);
         if(v->Left)
            q-enque(v->left);
         if(v->right)
            q->enque(v->right);
      }
   }
   delete newline;
}

所属标签

可能回答问题的人

  • EatRice

    16 粉丝0 提问10 回答
  • 富有想象力的人

    5 粉丝0 提问3 回答
  • 最爱开车啦

    9 粉丝503 提问3 回答
  • 成都加米谷大数据

    5 粉丝0 提问3 回答

扫码关注云+社区

领取腾讯云代金券