devbox
Guff_9hys
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树的层序遍历 + 通过层序遍历实现二叉树的操作_按照层数遍历二叉树

作者：Guff_9hys | 2024-07-18 15:59:00

赞

踩

按照层数遍历二叉树

目录

一、二叉树的层序遍历

二、int sizeOf(TreeNode root) ：获取树中结点个数

三、 int  leafSizeOf(TreeNode root) ：获取叶子结点的个数

四、带层数的层序遍历

1. 使用打包的方式： class TreeNodeWithLevel 

2. 使用两个队列：nodeQueue 和 levelQueue

五、int getKLevelSize(TreeNode root , int k) ：获取第 k 层结点的个数

六、int heightOf(TreeNode root) ：获取二叉树的高度

七、boolean isCompleteTree(TreeNode root)：判断一棵树是否是完全二叉树

一、二叉树的层序遍历

     凡是广度优先遍历，都要用到队列。使用队列确保先进先出（FIFO）。

     层序遍历要求从上往下（每个结点负责其孩子），从左往右（先左子树再右子树）。取出一个元素，就把其相应的左右孩子放入队列中（null 的不用放入）。

代码：

  1.    public static void levelorder(TreeNode root) {
  2.         if (root == null) {
  3.             return;
  4.         }
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         //先将根结点放入，再进行循环判断
  7.         //1. 取出队首元素
  8.         //2. 打印队首元素值
  9.         //3. 将队首元素的左孩子和右孩子依次放入队列中，为 null 的结点不放入
  10.         queue.offer(root);
  11.         while (!queue.isEmpty()) {
  12.             TreeNode p = queue.poll();
  13.             System.out.println(p.toString());
  14.             if (p.left != null) {
  15.                 queue.offer(p.left);
  16.             }
  17.             if (p.right != null) {
  18.                 queue.offer(p.right);
  19.             }
  20.         }
  21.     }

二、int sizeOf(TreeNode root) ：获取树中结点个数

思路：层序遍历，利用队列，每取出一个元素，size++

代码：

  1.     public static int sizeOf(TreeNode root) {
  2.         if (root == null) {
  3.             return 0;
  4.         }
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.offer(root);
  7.         int size = 0;
  8.         while (!queue.isEmpty()) {
  9.             TreeNode p = queue.poll();
  10.             size++;
  11.             if (p.left != null) {
  12.                 queue.offer(p.left);
  13.             }
  14.             if (p.right != null) {
  15.                 queue.offer(p.right);
  16.             }
  17.         }
  18.         return size;
  19.     }

三、 int  leafSizeOf(TreeNode root) ：获取叶子结点的个数

思路：跟统计结点数类似，只有当是叶子结点时，size 才进行 +1

代码：

  1.     public static int leafSizeOf(TreeNode root) {
  2.         if (root == null) {
  3.             return 0;
  4.         }
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.offer(root);
  7.         int size = 0;
  8.         while (!queue.isEmpty()) {
  9.             TreeNode p = queue.poll();
  10.             if (p.left == null && p.right == null) {
  11.                 size++;
  12.             }
  13.             if (p.left != null) {
  14.                 queue.offer(p.left);
  15.             }
  16.             if (p.right != null) {
  17.                 queue.offer(p.right);
  18.             }
  19.         }
  20.         return size;
  21.     }

四、带层数的层序遍历

1. 使用打包的方式： class TreeNodeWithLevel 

     使用打包的方式，新建一个类，将结点和该结点相应的层数作为属性放入该类中。使用是将TreeNode 替换成 TreeNodeWithLevel，并且向队列中添加元素时，传入结点的同时，传入 level 层数即可。（若 node 的层数为 level，那么 node 的左右孩子的层数就为 level + 1）

代码：

  1.     static class TreeNodeWithLevel {
  2.         public TreeNode node;
  3.         public int level;
  4.  
  5.         public TreeNodeWithLevel(TreeNode node, int level) {
  6.             this.node = node;
  7.             this.level = level;
  8.         }
  9.  
  10.         @Override
  11.         public String toString() {
  12.             return String.format("%s-%d",node.toString(),level);
  13.         }
  14.     }
  15.  
  16.     //层序遍历 （带层数）
  17.     public static void levelorderWithLevel(TreeNode root) {
  18.         if (root == null) {
  19.             return;
  20.         }
  21.         Queue<TreeNodeWithLevel> queue = new LinkedList<>();
  22.         queue.offer(new TreeNodeWithLevel(root,1));
  23.         while (!queue.isEmpty()) {
  24.             TreeNodeWithLevel node = queue.poll();
  25.             TreeNode p = node.node;
  26.             int level = node.level;
  27.             System.out.println(node);
  28.             if (p.left != null) {
  29.                 queue.offer(new TreeNodeWithLevel(p.left,level + 1));
  30.             }
  31.             if (p.right != null) {
  32.                 queue.offer(new TreeNodeWithLevel(p.right,level + 1));
  33.             }
  34.  
  35.         }
  36.     }

2. 使用两个队列：nodeQueue 和 levelQueue

     使用两个队列，一个队列存放结点，另一个队列存放相应的层数。需要注意的是两个队列对应的元素个数一样，所以在 while() 条件判断时，取任意一个队列的元素不为空即可。

代码：

  1.     public static void levelorderWithLevel2(TreeNode root) {
  2.         if (root == null) {
  3.             return;
  4.         }
  5.         Queue<TreeNode> nodeQueue = new LinkedList<>();
  6.         Queue<Integer> levelQueue = new LinkedList<>();
  7.  
  8.         nodeQueue.offer(root);
  9.         levelQueue.offer(1);
  10.  
  11.         while (!nodeQueue.isEmpty()) {
  12.             TreeNode p = nodeQueue.poll();
  13.             int level = levelQueue.poll();
  14.             System.out.println( p + " + " + level);
  15.  
  16.             if (p.left != null) {
  17.                 nodeQueue.offer(p.left);
  18.                 levelQueue.offer(level + 1);
  19.             }
  20.             if (p.right != null) {
  21.                 nodeQueue.offer(p.right);
  22.                 levelQueue.offer(level + 1);
  23.             }
  24.         }
  25.     }

五、int getKLevelSize(TreeNode root , int k) ：获取第 k 层结点的个数

思路：使用带层数的层序遍历，当从队列中取出的元素的 level == k 时，size++。 

代码：

  1.     public static int getKLevelSize(TreeNode root,int k) {
  2.         if (root == null) {
  3.             return 0;
  4.         }
  5.  
  6.         Queue<TreeNodeWithLevel> queue = new LinkedList<>();
  7.         queue.offer(new TreeNodeWithLevel(root,1));
  8.  
  9.         //定义变量，记录 k 层结点的个数
  10.         int size = 0;
  11.         while (!queue.isEmpty()) {
  12.             TreeNodeWithLevel node = queue.poll();
  13.             TreeNode p = node.node;
  14.             int level = node.level;
  15.  
  16.             if (level == k) {
  17.                 //说明是第 k 层了
  18.                 size++;
  19.             }
  20.             if (p.left != null) {
  21.                 queue.offer(new TreeNodeWithLevel(p.left,level + 1));
  22.             }
  23.             if (p.right != null) {
  24.                 queue.offer(new TreeNodeWithLevel(p.right,level + 1));
  25.             }
  26.         }
  27.         return size;
  28.     }

六、int heightOf(TreeNode root) ：获取二叉树的高度

思路：使用带层数的层序遍历，返回最后一个加入队列结点的 level 值即可。

代码：

  1.     public static int heightOf(TreeNode root) {
  2.         if (root == null) {
  3.             return 0;
  4.         }
  5.         Queue<TreeNodeWithLevel> queue = new LinkedList<>();
  6.         queue.offer(new TreeNodeWithLevel(root,1));
  7.  
  8.         //定义一个变量记录 height
  9.         //height 的值可以根据 level 确定
  10.         int height = -1;
  11.         while (!queue.isEmpty()) {
  12.             TreeNodeWithLevel node = queue.poll();
  13.             TreeNode p = node.node;
  14.             int level = node.level;
  15.  
  16.             height = level;
  17.  
  18.             if (p.left != null) {
  19.                 queue.offer(new TreeNodeWithLevel(p.left,level + 1));
  20.             }
  21.             if (p.right != null) {
  22.                 queue.offer(new TreeNodeWithLevel(p.right,level + 1));
  23.             }
  24.  
  25.         }
  26.         //此时 height 就为最后一个 level ，即最大的 level
  27.         return height;
  28.     }

七、boolean isCompleteTree(TreeNode root)：判断一棵树是否是完全二叉树

思路：将所有元素依次加入队列，当取出的元素为 null 时停止元素添加。因为二叉树碰到 null 有两种情况：

  • null 之后所有元素也都为 null，则说明是完全二叉树
  • null 之后还有元素,则说明不是完全二叉树

代码：

  1.     public static boolean isCompleteTree(TreeNode root) {
  2.         if (root == null) {
  3.             return true;
  4.         }
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.offer(root);
  7.  
  8.         //循环终止的条件，从队列中取出的元素是 null
  9.         while (true) {
  10.             TreeNode p = queue.poll();
  11.             if (p == null) {
  12.                 break;
  13.             }
  14.             //因为这里需要根据本身的树进行判断，所以不用再判断左右孩子是否为 null
  15.             queue.offer(p.left);
  16.             queue.offer(p.right);
  17.         }
  18.  
  19.         //判断取出元素为 null 后，其后面是否还有元素，即判断后面元素是否 == null
  20.         //当后面元素存在 != null 时，说明不是完全二叉树，返回 false
  21.         //当后面元素都 == null 时，说明是完全二叉树，返回 true
  22.         while (!queue.isEmpty()) {
  23.             TreeNode q = queue.poll();
  24.             if (q != null) {
  25.                 return false;
  26.             }
  27.         }
  28.         return true;
  29.     }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/846544
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号