从顶部开始,您将如何逐级打印出二叉树中的数据？

Question

这是一个面试问题

我想到了一个解决方案.它使用队列.

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);  
        }   
    }
}    

有什么想法比这更好的解决方案,它不使用Queue？

Answer 1

逐级遍历被称为广度优先遍历.使用队列是执行此操作的正确方法.如果你想进行深度优先遍历,你会使用堆栈.

你拥有它的方式并不是很标准.这是它应该如何.

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

五

6

Answer 2

由于问题需要逐级打印树,因此应该有一种方法来确定何时在控制台上打印新行字符.这是我的代码,它试图通过将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;
}

Answer 3

让我们看看一些Scala解决方案.首先,我将定义一个非常基本的二叉树:

case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])

我们将使用以下树:

    1
   / \
  2   3
 /   / \
4   5   6

您可以像这样定义树:

val myTree = Tree(1, 
                  Some(Tree(2, 
                            Some(Tree(4, None, None)), 
                            None
                       )
                  ),
                  Some(Tree(3,
                            Some(Tree(5, None, None)),
                            Some(Tree(6, None, None))
                       )
                  )
             )

我们将定义一个breadthFirst函数,它将遍历树,将所需的函数应用于每个元素.有了这个,我们将定义一个打印功能并使用它如下:

def printTree(tree: Tree[Any]) = 
  breadthFirst(tree, (t: Tree[Any]) => println(t.value))

printTree(myTree)

现在,Scala解决方案,递归,列出但没有队列:

def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
  def traverse(trees: List[Tree[T]]): Unit = trees match {
    case Nil => // do nothing
    case _ =>
      val children = for{tree <- trees
                         Some(child) <- List(tree.left, tree.right)} 
                         yield child
      trees map f
      traverse(children)
  }

  traverse(List(t))
}

接下来,Scala解决方案,队列,没有递归:

def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
  import scala.collection.mutable.Queue
  val queue = new Queue[Option[Tree[T]]]
  import queue._

  enqueue(Some(t))

  while(!isEmpty) 
    dequeue match {
      case Some(tree) => 
        f(tree)
        enqueue(tree.left)
        enqueue(tree.right)
      case None =>
    }
}

这种递归解决方案功能齐全,但我有一种不安的感觉,它可以进一步简化.

队列版本不起作用,但它非常有效.关于导入对象的一点在Scala中是不寻常的,但在这里很好用.

Answer 4

C++：

  struct node{
    string key;
    struct node *left, *right;
  };

  void printBFS(struct node *root){
    std::queue<struct node *> q;
    q.push(root);

    while(q.size() > 0){
      int levelNodes = q.size();
      while(levelNodes > 0){
        struct node *p = q.front(); 
        q.pop();
        cout << " " << p->key ;
        if(p->left != NULL) q.push(p->left);
        if(p->right != NULL) q.push(p->right);
        levelNodes--;
      }
      cout << endl;
    }
  }

输入 ：

平衡树创建自：

 string a[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n"};

输出：

 g 
 c k 
 a e i m 
 b d f h j l n 

算法：

1. 创建链表节点的 ArrayList。
2. 使用队列进行层序遍历（广度优先搜索）。
3. 为了获取每个级别的所有节点，在从队列中取出节点之前，将队列的大小存储在一个变量中，假设您将其称为 levelNodes。
4. 现在，当 levelNodes > 0 时，取出节点并打印它，并将它们的子节点添加到队列中。
5. 在这个 while 循环之后放置一个换行符。

PS：我知道OP说，不用排队。我的回答只是为了表明是否有人正在寻找使用队列的 C++ 解决方案。