N叉树广度优先遍历/检查完成或全

Question

class Node { 
    Node subtree, next; 
    int data; 

    public Node(int _data) { 
    subtree = null; 
    next = null; 
    data = _data; 

    } 
} 


class listTree { 
    private Node root; 
    public listTree() { 
    root = null; 
    } 

    public static final Scanner sc = new Scanner(System.in); 

    public void display(Node r) { 
    if (r != null) 
     System.out.print("Current: " + r.data + " "); 
    if (r.subtree == null) 
     System.out.print("Down: null "); 
    else 
     System.out.print("Down: " + r.subtree.data + " "); 
    if (r.next == null) 
     System.out.println("Next: " + null); 
    else 
     System.out.println("Next: " +r.next.data); 
    } 

    public Node addRoot(int r) { 
    root.data = r; 
    return root; 
    } 

    public void addChild(int c) { 
    root = addChild(root, c); 
    } 

    private Node addChild(Node node, int c) { 
    char ch= 'x'; 
    if (node == null) 
      node = new Node(c); 
    else { 
     do { 
     display(node); 
     System.out.println("[D]own or [N]ext?"); 
     ch = sc.next().charAt(0); 
     if (ch == 'n' || ch == 'N') 
      node.next = addChild(node.next, c); 
     else if (ch == 'd' || ch == 'D') 
      node.subtree = addChild(node.subtree, c); 
     else 
      System.out.print("Invalid input. No movement made. "); 
     } while ((ch != 'd') && (ch != 'D') && (ch != 'n') && (ch != 'N')); 
    } 
    return node; 
    } 

    public void postOrderTraversal() { 
    postOrderTraversal(root); 
    } 

    private void postOrderTraversal(Node r) 
    {  
    if (r != null) { 
     postOrderTraversal(r.subtree); 
     System.out.print(r.data +" "); 
     postOrderTraversal(r.next); 
    } 
    } 

    public void preOrderTraversal() { 
    preOrderTraversal(root); 
    } 

    private void preOrderTraversal(Node r) { 
    if (r != null) { 
     System.out.print(r.data +" "); 
     preOrderTraversal(r.subtree); 
     preOrderTraversal(r.next); 
    } 
    } 

    public void breathFirstTraversal(){ 
    breathFirstTraversal(root); 
    } 

    private void breathFirstTraversal(Node root) { 
    Queue<Node> queue = new LinkedList<Node>(); 
    if (root == null) 
     return; 
    queue.clear(); 
    queue.add(root); 
    while(!queue.isEmpty()){ 
     Node node = queue.remove(); 
     System.out.print(node.data + " "); 
     if(node.next != null) queue.add(node.next); 
     if(node.subtree != null) queue.add(node.subtree); 
    } 
    } 

    private boolean checkComple(Node node) { 

} 

public class treeAssignment { 
    public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); 
    listTree lt = new listTree(); 
    do { 
     System.out.println("Enter integer element:"); 
     lt.addChild(sc.nextInt()); 
     System.out.println("Done? Y/N"); 
    } while (sc.next().charAt(0) == 'n'); 
    System.out.println("PostOrder Traversal:"); 
    lt.postOrderTraversal(); 
    System.out.println(); 
    System.out.println("PreOrder Traversal:"); 
    lt.preOrderTraversal(); 
    System.out.println(); 
    lt.breathFirstTraversal(); 
    } 
} 

试图找出如何实现给定的n进制树的结构在图像呼吸优先遍历方法。

Answer 1

所以基本上一个节点指向其直接右兄弟，也可以指向它的最左边的子节点。 BFS实现起来很简单，对二叉树的BFS进行一些小修改也是一样的想法。

Deque<Node> queue = new ArrayDeque<Node>(); 
queue.add(root); 
while(!queue.isEmpty()) { 
    Node node = queue.poll(); 
    while (node != null) { 
     System.out.println(node.data); 
     if (node.subtree != null) { 
      queue.add(node.subtree); // to visit the nodes on the next level 
     } 
     node = node.next; // to visit the other nodes on the same level 
    } 
} 

Answer 2

将树实现为LL是一个值得怀疑的想法。我强烈建议看看Graphs，这是一个更好的选择。

这里是读一个例子：http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/