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

在 LL 中实现树是一个值得怀疑的想法。我强烈建议查看 Graphs，对于类似这样的事情，它是一个更好的选择。

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

Answer 2

所以基本上一个节点指向它的直接右兄弟节点，它也可以指向它最左边的子节点。 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
    }
}

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

N-ary tree breadth first traversal / check complete or full

java

algorithm

tree