algorithm - sirve - Nivel de impresión orden transversal del árbol binario en forma de zigzag
para que sirve un arbol binario (5)
// código c ++ simple usando dos pilas
<pre> void zigzag(struct node *root)
{
int lefttoright = 1 ;
struct node *temp ;
if(root == NULL)
return ;
stack<struct node *> current , next ,temp2 ;// temp is used to swap
////current and next
current.push(root);
while(!current.empty())
{temp = current.top();
current.pop();
cout<< temp->data << " " ;
if(lefttoright)
{ if(temp->left)
next.push(temp->left) ;
if(temp->right)
next.push(temp->right) ;
}
else
{if(temp->right)
next.push(temp->right) ;
if(temp->left)
next.push(temp->left) ;
}
if(current.empty()) // make current as next and next as current
//to hold next level nodes
{lefttoright = 1-lefttoright ;
temp2 = current ;
current = next ;
next = temp2 ;
}
}
</pre>
Tengo que imprimir los nodos de un árbol binario utilizando el orden de nivel transversal, pero en forma de espiral, es decir, los nodos de diferentes niveles deben imprimirse en forma de espiral.
por ejemplo: si el árbol parece:
La salida debe ser 10 5 20 25 15 6 4.
El algoritmo que utilicé es simple y es solo una pequeña variación del orden de nivel transversal. Acabo de tomar una variable p.si la variable es igual a 1 que se imprime el orden en un nivel dado de izquierda a derecha, si es -1 se imprime de derecha a izquierda.
void getlevel(struct node *root,int n,int p)
{
if(root==NULL)
return;
if(n==0)
{
printf("%d ",root->info);
return;
}
if(n>0)
{
if(p==1)
{
getlevel(root->left,n-1,p);
getlevel(root->right,n-1,p);
}
if(p==-1)
{
getlevel(root->right,n-1,p);
getlevel(root->left,n-1,p);
}
}
}
Estoy obteniendo la respuesta, pero la complejidad del peor de los casos es probablemente O (n ^ 2) en caso de árbol sesgado.
¿Puede haber un mejor algoritmo para esta tarea? ..
Todo mi programa esta here
El siguiente código hará el trabajo:
Idioma utilizado: Java
// Algorithm for printing nodes in Zigzag order(zigzag tree traversal)
static void zigzagTreeTraversal(Node root)
{
int count=0,c=1,i=0;
boolean odd=false;
Queue<Node> queue=new LinkedList<Node>();
Node temp = null;
queue.add(root);
System.out.print("Printing Tree Traversal in Zigzag form :");
while(true)
{
if(queue.isEmpty())
{
break;
}
for(i=0;i<c;i++)
{
temp=queue.remove();
System.out.print(", " + temp.data);
if(odd)
{
if(temp.right!=null)
{
queue.add(temp.right);
count++;
}
if(temp.left!=null)
{
queue.add(temp.left);
count++;
}
}
else
{
if(temp.left!=null)
{
queue.add(temp.left);
count++;
}
if(temp.right!=null)
{
queue.add(temp.right);
count++;
}
}
}
c=count;
count=0;
odd=!odd;
}
}
Psuedocode para el ordenamiento a nivel de espiral de un árbol binario.
//Define two stacks S1, S2
//At each level,
// S1 carries the nodes to be traversed in that level
// S2 carries the child nodes of the nodes in S1
spiralLevelOrder(root) {
S1 = new Stack()
S2 = new Stack()
S1.push(root)
spiralLevelOrderRecursion(S1, S2, 1)
}
spiralLevelOrderRecursion(S1, S2, level) {
while(S1 not empty) {
node = S1.pop()
visit(node)
if (level is odd) {
S2.push(node.rightNode)
S2.push(node.leftNode)
}
else {
S2.push(node.leftNode)
S2.push(node.rightNode)
}
}
if (S2 not empty)
spiralLevelOrderRecursion(S2, S1, level+1)
}
Árbol de muestra: formato 1- (2- (4,5), 3- (5,6)): raíz- (leftchild, rightchild)
Aplicando el pseudocódigo:
spiralLevelOrderRecursion ([1], [], 1)
S2 - [] -> [3] -> [2, 3]
visit order : 1
spiralLevelOrderRecursion ([2,3], [], 2)
S2 - [] -> [4] -> [5,4] -> [6, 5, 4] -> [7, 6, 5, 4]
visit order : 2, 3
spiralLevelOrderRecursion ([7,6,5,4], [], 3)
visit order : 7, 6, 5, 4
Sí.
Puedes hacer algo similar al ordenamiento normal de nivel.
Tienes que usar dos pilas
- Primera pila para imprimir de izquierda a derecha.
- Segunda pila para imprimir de derecha a izquierda.
Comience desde el nodo raíz. Almacena a los niños en una pila. En cada iteración, tienes nodos de un nivel en una de las pilas. Imprima los nodos y empuje los nodos del siguiente nivel en otra pila. Repite hasta que alcances el nivel final.
Complejidad temporal O (n) y complejidad espacial O (n).
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
public class ZigZagTraversal {
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryTree bt = new BinaryTree();
int[] array = {2,5,1,3,11,7,8,9,4,10,6};
/*
* 2
* / /
* / /
* / /
* 5 1
* / / / /
* / / / /
* 3 11 7 8
* / / / /
* 9 4 10 6
*
* */
bt=BinaryTree.buildATree(bt, array);
//BinaryTree.inOrderTraversal(bt);
zigZagTraversal(llForAllNodesAtEachDepth(bt));
zigZagDisplay(bt);
}
public static void zigZagDisplay(BinaryTree bt){
Stack<BinaryTree> s = new Stack<>();
if(s.isEmpty())
s.push(bt);
boolean flag = true;
while(!s.isEmpty()){
Stack<BinaryTree> temp = new Stack<>();
while(!s.isEmpty()){
BinaryTree b = s.pop();
System.out.print(b.data+" ");
if(flag){
if(b.left!=null)
temp.push(b.left);
if(b.right!=null)
temp.push(b.right);
}
else{
if(b.right!=null)
temp.push(b.right);
if(b.left!=null)
temp.push(b.left);
}
}
s=temp;
flag=!flag;
}
}
public static ArrayList<LinkedList<BinaryTree>> llForAllNodesAtEachDepth(BinaryTree bt){
ArrayList<LinkedList<BinaryTree>> res = new ArrayList<LinkedList<BinaryTree>>();
return createLlForAllNodesAtEachDepth(res,bt, 0);
}
public static ArrayList<LinkedList<BinaryTree>> createLlForAllNodesAtEachDepth(ArrayList<LinkedList<BinaryTree>> res, BinaryTree bt, int level){
if(bt==null)
return null;
if(level==res.size()){
LinkedList<BinaryTree> list = new LinkedList<BinaryTree>();
list.add(bt);
res.add(list);
createLlForAllNodesAtEachDepth(res,bt.left,level+1);
createLlForAllNodesAtEachDepth(res,bt.right,level+1);
}
else{
res.get(level).add(bt);
createLlForAllNodesAtEachDepth(res,bt.left,level+1);
createLlForAllNodesAtEachDepth(res,bt.right,level+1);
}
return res;
}
public static void zigZagTraversal(ArrayList<LinkedList<BinaryTree>> res){
boolean flag=true;
for(int i=0;i<res.size();i++){
LinkedList<BinaryTree> temp = res.get(i);
if(flag){
for(int j=0;j<temp.size();j++){
System.out.print(temp.get(j).data+" -> ");
}
flag=false;
}
else{
for(int j=temp.size()-1;j>=0;j--){
System.out.print(temp.get(j).data+" -> ");
}
flag=true;
}
System.out.println();
}
}
}