Come stampare i dati in un albero binario, di livello in livello, partendo dall'alto?
https://stackoverflow.com/questions/1104644
-
12-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Questa è una domanda di intervista
Penso a una soluzione.Utilizza la coda.
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);
}
}
}
C'è qualcosa che può pensare che la soluzione migliore di questa, che non fa uso di Coda?
Soluzione
Di livello in livello di attraversamento è noto come Breadth-first attraversamento.Utilizzando una Coda è il modo corretto di fare questo.Se si voleva fare una profondità prima di attraversamento che si dovrebbe utilizzare una pila.
Il modo in cui hai non è abbastanza standard, anche se.Ecco come dovrebbe essere.
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
}
}
}
Modifica
Ecco l'algoritmo al lavoro.Diciamo che aveva un albero, in questo modo:
1
/ \
2 3
/ / \
4 5 6
Primo, principale (1) sarebbe accodato.Il ciclo è poi entrato.primo elemento della coda (1) è annullato e stampato.1 i figli sono accodato da sinistra a destra, la coda ora contiene {2, 3} torna all'inizio del ciclo primo elemento della coda (2) è annullato e stampato 2 i figli sono accodato forma da sinistra a destra, la coda ora contiene {3, 4} torna all'inizio del ciclo ...
La coda di contenere questi valori su ogni loop
1: {1}
2: {2, 3}
3: {3, 4}
4: {4, 5, 6}
5: {5, 6}
6: {6}
7:{}//vuoto, ciclo termina
Output:
1
2
3
4
5
6
Altri suggerimenti
Dal momento che la domanda richiede la stampa l'albero di livello in livello, ci dovrebbe essere un modo per determinare quando per stampare il carattere di nuova riga sulla console.Ecco il mio codice che tenta di fare lo stesso aggiungendo NewLine nodo alla coda,
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;
}
Vediamo qualche Scala di soluzioni.In primo luogo, definire le basi di albero binario:
case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])
Useremo la seguente struttura:
1
/ \
2 3
/ / \
4 5 6
Si definisce albero come questo:
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))
)
)
)
Definiamo un breadthFirst funzione che consente di attraversare l'albero applicando la funzione desiderata per ogni elemento.Con questo, è necessario definire una funzione di stampa e di utilizzarlo come questo:
def printTree(tree: Tree[Any]) =
breadthFirst(tree, (t: Tree[Any]) => println(t.value))
printTree(myTree)
Ora, Scala soluzione ricorsiva, elenchi, ma niente code:
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))
}
A quel punto, Scala soluzione, coda, senza ricorsione:
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 =>
}
}
Che soluzione ricorsiva è completamente funzionale, anche se ho una sensazione di disagio che non può essere ulteriormente semplificata.
La coda di versione non è funzionale, ma è molto efficace.Il po ' di importazione di un oggetto è insolito, in Scala, ma messo a buon uso qui.
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;
}
}
Ingresso :
Equilibrata albero creato da:
string a[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n"};
Output:
g
c k
a e i m
b d f h j l n
- Creare un ArrayList di una Lista Collegata Nodi.
- Fare l'ordine dei livelli di attraversamento usando la coda(Breadth First Search).
- Per raggiungere tutti i nodi ad ogni livello, prima di un nodo dalla coda, memorizzare la dimensione della coda in una variabile, diciamo è chiamare levelNodes.
- Ora, mentre levelNodes > 0, i nodi e la stampa e aggiungere i loro bambini in coda.
- Dopo questo ciclo while inserire un'interruzione di riga.
P. S:So che l'OP ha detto, senza coda.La mia risposta è solo per mostrare se qualcuno è alla ricerca di un C++ soluzione usando la coda.
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();
}
}
}
}
Per stampare da un livello, è possibile memorizzare le informazioni a livello con il nodo, come una tupla da aggiungere alla coda.Quindi è possibile stampare una nuova riga ogni volta che il livello è cambiato.Qui è un codice Python per farlo.
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))
Penso che ciò che si aspetta è quello di stampare i nodi ad ogni livello separati da uno spazio o una virgola e i livelli di essere separati da una nuova linea.Questo è come vorrei codice dell'algoritmo.Sappiamo che quando facciamo una ricerca breadth-first su un grafico o un albero e inserire i nodi in coda, tutti i nodi in coda coming out sarà allo stesso livello di quello precedente o di un nuovo livello superiore livello + 1 e nient'altro.
Così, quando siete a un livello mantenere stampa i valori del nodo e non appena si scopre che il livello del nodo aumenta di 1, quindi è possibile inserire una nuova riga prima di avviare la stampa di tutti i nodi a quel livello.
Questo è il mio codice che non usano molta memoria e solo la coda è necessario per tutto.
Supponendo che l'albero inizia dalla radice.
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
Alla fine tutto è la coda per il trattamento.
Ho modificato la risposta, in modo che il null nodi e di stampa per l'altezza.In realtà era abbastanza decente per testare l'equilibrio di un rosso nero albero.può
anche aggiungere il colore in stampa check nero altezza.
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");
}
Prova questo (Completo di codice) :
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;
}
}
Naturalmente non è necessario utilizzare la coda.Questo è in 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)
Provare con sotto il codice.
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();
}
}
}
ecco la mia risposta.
//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)}
}
}
i bambini è una matrice qui che memorizza i figli di un nodo.
