首页 > itarticle > 二叉树的级别遍历

二叉树的级别遍历

admin 1月 18, 2021 0

Question

给定二叉树，逐级打印其节点。即应首先打印存在于级别1的所有节点，然后再打印第2级的节点等等。任何级别的所有节点应该从左到右打印。

     1
   /   
  2     3
 /    / 
4   5 6   7
         / 
        8   9

输出：1 2 3 4 5 6 7 8 9

Code

import java.util.*;


public class A043{
 TreeNode root;
   public static void levelTraversal(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();  
        queue.push(root);  
  
        while (!queue.isEmpty()) {  
            TreeNode cur = queue.removeFirst();  
            System.out.print(cur.data + " ");  
            if (cur.left != null) {  
                queue.add(cur.left);  
            }  
            if (cur.right != null) {  
                queue.add(cur.right);  
            }  
        }  
    }
    public static void main(String args[]) {
       TreeNode tree = new TreeNode(1);
         tree.left = new TreeNode(2);
         tree.right = new TreeNode(3);
        tree.left.left = new TreeNode(4);
        tree.left.right = new TreeNode(5);
       tree.left.left.left = new TreeNode(6);
       tree.left.left.right = new TreeNode(7);
          tree.left.left.right.left = new TreeNode(8); 
        tree.left.left.right.right = new TreeNode(9); 
       levelTraversal(tree); 
 }     
}
class TreeNode {
     int data;
    TreeNode left, right;

   TreeNode(int item) {
      data = item;
     left = right = null;
    }
}