Как вы распечатываете данные в двоичном дереве, уровень за уровнем, начиная с вершины?

Ответ 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

5

6

Ответ 2

Поскольку вопрос требует печати уровня дерева по уровню, должен быть способ определить, когда печатать новый символ строки на консоли. Здесь мой код, который пытается сделать то же самое, добавив NewLine node в очередь,

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

Ответ 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))
                       )
                  )
             )

Мы определяем ширину первой функции, которая будет пересекать дерево, применяя желаемую функцию к каждому элементу. При этом мы определяем функцию печати и используем ее следующим образом:

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, но используется для использования здесь.

Ответ 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. После этого пока цикл ставит разрыв строки.

PS: я знаю, что ОП сказал, нет очереди. Мой ответ просто показать, если кто-то ищет решение C++, использующее очередь.

Ответ 5

public class LevelOrderTraversalQueue {     

    Queue<Nodes> qe = new LinkedList<Nodes>();

    public void printLevelOrder(Nodes root)     
    { 
        if(root == null) return;

        qe.add(root);
        int count = qe.size();

        while(count!=0)
        {   
            System.out.print(qe.peek().getValue());
            System.out.print("  ");
            if(qe.peek().getLeft()!=null) qe.add(qe.peek().getLeft());
            if(qe.peek().getRight()!=null) qe.add(qe.peek().getRight());
            qe.remove(); count = count -1;
            if(count == 0 )
            {
                System.out.println("  ");
                count = qe.size();
            }
        }           
    }

}

Ответ 6

Чтобы распечатать по уровню, вы можете сохранить информацию уровня с помощью node в качестве кортежа для добавления в очередь. Затем вы можете печатать новую строку всякий раз, когда уровень изменяется. Вот код Python для этого.

from collections import deque
class BTreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def printLevel(self):
        """ Breadth-first traversal, print out the data by level """
        level = 0
        lastPrintedLevel = 0
        visit = deque([])
        visit.append((self, level))
        while len(visit) != 0:
            item = visit.popleft()
            if item[1] != lastPrintedLevel:  #New line for a new level
                lastPrintedLevel +=1
                print
            print item[0].data,
            if item[0].left != None:
                visit.append((item[0].left, item[1] + 1))
            if item[0].right != None: 
                visit.append((item[0].right, item[1] + 1))

Ответ 7

Я думаю, что вы ожидаете, чтобы напечатать узлы на каждом уровне, разделенные пробелом или запятой, а уровни должны быть разделены новой строкой. Вот как я бы кодировал алгоритм. Мы знаем, что когда мы выполняем поиск в ширину по графику или дереву и вставляем узлы в очередь, все выходящие в очередь узлы будут либо на том же уровне, что и предыдущий, либо на новом уровне, который является родительским уровнем +1 и больше ничего.

Поэтому, когда вы находитесь на уровне, продолжайте распечатывать значения узлов и, как только вы обнаружите, что уровень узла увеличивается на 1, вы вставляете новую строку перед началом печати всех узлов на этом уровне.

Это мой код, который не использует много памяти и только очередь нужна для всего.

Предполагая, что дерево начинается с корня.

queue = [(root, 0)]  # Store the node along with its level. 
prev = 0
while queue:
  node, level = queue.pop(0)
  if level == prev:
    print(node.val, end = "")
  else:
    print()
    print(node.val, end = "")
  if node.left:
    queue.append((node.left, level + 1))
  if node.right:
    queue.append((node.right, level + 1))
  prev = level

В конце все, что вам нужно, это очередь для всей обработки.

Ответ 8

Я отредактировал ответ так, чтобы он показывал нулевые узлы и печатал его по высоте.  Был на самом деле достаточно приличным для проверки баланса красного черного дерева. может
 также добавьте цвет в линию печати, чтобы проверить высоту черного.

    Queue<node> q = new Queue<node>();
    int[] arr = new int[]{1,2,4,8,16,32,64,128,256};
    int i =0;
    int b = 0;
    int keeper = 0;
    public void BFS()
    {


        q.Enqueue(root);
        while (q.Count > 0)
        {

            node n = q.Dequeue();

            if (i == arr[b])
            {

                System.Diagnostics.Debug.Write("\r\n"+"("+n.id+")"); 
                b++;
                i =0 ;
            }
            else {

                System.Diagnostics.Debug.Write("(" + n.id + ")"); 

            }
            i++; 


            if (n.id != -1)
            {



                if (n.left != null)
                {

                    q.Enqueue(n.left);
                }
                else
                {
                    node c = new node();
                    c.id = -1;
                    c.color = 'b';
                    q.Enqueue(c);
                }

                if (n.right != null)
                {

                    q.Enqueue(n.right);
                }
                else
                {
                    node c = new node();
                    c.id = -1;
                    c.color = 'b';
                    q.Enqueue(c);

                }
            }

        }
        i = 0;
        b = 0;
        System.Diagnostics.Debug.Write("\r\n");
    }

Ответ 9

Попробуйте этот (полный код):

class HisTree
{
    public static class HisNode
    {
        private int data;
        private HisNode left;
        private HisNode right;

        public HisNode() {}
        public HisNode(int _data , HisNode _left , HisNode _right)
        {
            data = _data;
            right = _right;
            left = _left;
        }
        public HisNode(int _data)
        {
            data = _data;
        }
    }

    public static int height(HisNode root)
    {
        if (root == null)
        {
            return 0;
        }

        else
        {
            return 1 + Math.max(height(root.left), height(root.right));
        }
    }


    public static void main(String[] args)
    {
//          1
//         /  \ 
//        /    \
//       2      3
//      / \    / \  
//     4    5 6   7
//    /
//   21

        HisNode root1 = new HisNode(3 , new HisNode(6) , new HisNode(7));
        HisNode root3 = new HisNode(4 , new HisNode(21) , null);
        HisNode root2 = new HisNode(2 , root3 , new HisNode(5));
        HisNode root = new HisNode(1 , root2 , root1);
        printByLevels(root);
    }


    private static void printByLevels(HisNode root) {

        List<HisNode> nodes = Arrays.asList(root);
        printByLevels(nodes);

    }

    private static void printByLevels(List<HisNode> nodes)
    {
        if (nodes == null || (nodes != null && nodes.size() <= 0))
        {
            return;
        }
        List <HisNode> nodeList = new LinkedList<HisNode>();
        for (HisNode node : nodes)
        {
            if (node != null)
            {
                System.out.print(node.data);
                System.out.print(" , ");
                nodeList.add(node.left);
                nodeList.add(node.right);
            }
        }
        System.out.println();
        if (nodeList != null && !CheckIfNull(nodeList))
        {
            printByLevels(nodeList);    
        }
        else
        {
            return;
        }

    }


    private static boolean CheckIfNull(List<HisNode> list)
    {
        for(HisNode elem : list)
        {
            if (elem != null)
            {
                return false;
            }
        }
        return true;
    }
}

Ответ 10

Конечно, вам не нужно использовать очередь. Это в python.

# Function to  print level order traversal of tree
def printLevelOrder(root):
    h = height(root)
    for i in range(1, h+1):
        printGivenLevel(root, i)


# Print nodes at a given level
def printGivenLevel(root , level):
    if root is None:
        return
    if level == 1:
        print "%d" %(root.data),
    elif level > 1 :
        printGivenLevel(root.left , level-1)
        printGivenLevel(root.right , level-1)


""" Compute the height of a tree--the number of nodes
    along the longest path from the root node down to
    the farthest leaf node
"""
def height(node):
    if node is None:
        return 0
    else :
        # Compute the height of each subtree 
        lheight = height(node.left)
        rheight = height(node.right)
        return max(lheight, reight)

Ответ 11

Попробуйте с приведенным ниже кодом.

public void printLevelOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> nodesToVisit = new LinkedList<>();
    nodesToVisit.add(root);

    int count = nodesToVisit.size();

    while (count != 0) {
        TreeNode node = nodesToVisit.remove();

        System.out.print(" " + node.data);

        if (node.left != null) {
            nodesToVisit.add(node.left);
        }

        if (node.right != null) {
            nodesToVisit.add(node.right);
        }

        count--;

        if (count == 0) {
            System.out.println("");
            count = nodesToVisit.size();
        }
    }
}

Ответ 12

вот мой ответ.

//for level order traversal
    func forEachLevelOrder(_ visit : (TreeNode) -> Void) {

        visit(self)
        var queue = Queue<TreeNode>()
        children.forEach {
            queue.Enqueue($0)
        }
        while let node = queue.Dequeue() {
            visit(node)
            node.children.forEach { queue.Enqueue($0)}
        }

    }

children - это массив, в котором хранятся дочерние элементы узла.