Java语言描述二叉树的深度和宽度

解释：

二叉树的深度：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
二叉树的宽度：二叉树的每一层中都有一定数量的节点，节点数最多的那一层的节点数叫做二叉树的宽度。

思路：递归实现。

1.每个节点都可以看作根节点
2.根节点（任意一个节点）的深度等于它的左子树或右子树深度最大值+1
3.从根结点开始遍历，若遍历到叶子节点，深度为0

  //二叉树的深度
  public static int Depth(node root){
    if(root == null){
      return 0;
    }
    int dl = Depth(root.leftchild);
    int dr = Depth(root.rightchild);
    return dl>dr? dl+1:dr+1;
  }

二、二叉树的宽度

思路：层序遍历时添加一个计数器，记录每层的节点数

1.每层出队列时记录下一层的节点数，其实就是队列的Size()
2.每层遍历结束时，比较最大宽度与当前层节点数，记录最大值

public static int Width(node root) {
	if(root == null)
	    return 0;
	Queue<node> q = new LinkedList<node>();
	q.add(root);
	int width = 1;
	//最大宽度
	int len = 1;
	//当前层节点数
	while(q.size()>0){
		while(len-->0){
			node node = q.poll();
			if(node.leftchild != null){
				q.add(node.leftchild);
			}
			if(node.rightchild != null){
				q.add(node.rightchild);
			}
		}
		len = q.size();
		//每层循环结束后记录下一层的节点数
		width = width>q.size() ? width : q.size();
	}
	return width;
}

总结

以上就是本文关于Java语言描述二叉树的深度和宽度的全部内容，希望对大家有所帮助。如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • Java的二叉树排序以及遍历文件展示文本格式的文件树

    Java二叉树排序算法 排序二叉树的描述也是一个递归的描述, 所以排序二叉树的构造自然也用递归的: 排序二叉树的3个特征: 1:当前node的所有左孩子的值都小于当前node的值: 2:当前node的所有右孩子的值都大于当前node的值: 3:孩子节点也满足以上两点 package test.sort; public class BinaryNode { private int value;//current value private BinaryNode lChild;//left chil

  • JAVA 实现二叉树（链式存储结构）

    JAVA 实现二叉树（链式存储结构）

    二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

  • Java实现求二叉树的深度和宽度

    这个是常见的对二叉树的操作.总结一下: 设节点的数据结构,如下: 复制代码 代码如下: class TreeNode {     char val;     TreeNode left = null;     TreeNode right = null; TreeNode(char _val) {         this.val = _val;     } } 1.二叉树深度 这个可以使用递归,分别求出左子树的深度.右子树的深度,两个深度的较大值+1即可. 复制代码 代码如下: // 获取最大

  • java使用归并删除法删除二叉树中节点的方法

    本文实例讲述了java使用归并删除法删除二叉树中节点的方法.分享给大家供大家参考.具体分析如下: 实现的思想很简单: first:找到要删除的节点 second:如果删除的节点没有右子树那么左子树链到父节点 third:如果删除的节点没有左子树那么右子树链到父节点 forth:如果删除的节点又左右孩子,那么可以归并删除节点后的子树:方法有两种一种是用删除节点的左子树的最右节点,指向删除节点的右子树,另一种是用删除节点的用字数的最左节点指向删除节点的左子树. Java 实现如下: public v

  • Java中二叉树数据结构的实现示例

    来看一个具体的习题实践: 题目 根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序.中序.后序进行遍历 代码 import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类,定义二叉树节点 */ static class TreeNode { public Str

  • 图解红黑树及Java进行红黑二叉树遍历的方法

    图解红黑树及Java进行红黑二叉树遍历的方法

    红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

  • Java语言描述二叉树的深度和宽度

    解释: 二叉树的深度:从根结点到叶结点依次经过的结点(含根.叶结点)形成树的一条路径,最长路径的长度为树的深度. 二叉树的宽度:二叉树的每一层中都有一定数量的节点,节点数最多的那一层的节点数叫做二叉树的宽度. 思路:递归实现. 1.每个节点都可以看作根节点 2.根节点(任意一个节点)的深度等于它的左子树或右子树深度最大值+1 3.从根结点开始遍历,若遍历到叶子节点,深度为0 //二叉树的深度 public static int Depth(node root){ if(root == null)

  • java语言描述Redis分布式锁的正确实现方式

    分布式锁一般有三种实现方式:1.数据库乐观锁:2.基于Redis的分布式锁:3.基于ZooKeeper的分布式锁.本篇博客将介绍第二种方式,基于Redis实现分布式锁.虽然网上已经有各种介绍Redis分布式锁实现的博客,然而他们的实现却有着各种各样的问题,为了避免误人子弟,本篇博客将详细介绍如何正确地实现Redis分布式锁. 可靠性 首先,为了确保分布式锁可用,我们至少要确保锁的实现同时满足以下四个条件: 互斥性.在任意时刻,只有一个客户端能持有锁. 不会发生死锁.即使有一个客户端在持有锁的期间

  • Java语言描述存储结构与邻接矩阵代码示例

    Java语言描述存储结构与邻接矩阵代码示例

    存储结构 要存储一个图,我们知道图既有结点,又有边,对于有权图来说,每条边上还带有权值.常用的图的存储结构主要有以下二种: 邻接矩阵 邻接表 邻接矩阵 我们知道,要表示结点,我们可以用一个一维数组来表示,然而对于结点和结点之间的关系,则无法简单地用一维数组来表示了,我们可以用二维数组来表示,也就是一个矩阵形式的表示方法. 我们假设A是这个二维数组,那么A中的一个元素aij不仅体现出了结点vi和结点vj的关系,而且aij的值正可以表示权值的大小. 以下是一个无向图的邻接矩阵表示示例: 从上图我们可

  • Java语言描述MD5加密工具类实例代码

    编程中经常有用到MD5加密的情况,Java语言并没有像PHP一样提供原生的MD5加密字符串的函数,需要MD5加密的时候,往往需要自己写. 代码如下: import java.security.MessageDigest; public class MD5 { //公盐 private static final String PUBLIC_SALT = "demo" ; //十六进制下数字到字符的映射数组 private final static String[] hexDigits =

  • Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】

    Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】

    本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.

  • Java实现打印二叉树所有路径的方法

    本文实例讲述了Java实现打印二叉树所有路径的方法.分享给大家供大家参考,具体如下: 问题: 给一个二叉树,把所有的路径都打印出来. 比如,对于下面这个二叉树,它所有的路径为: 8 -> 3 -> 1 8 -> 2 -> 6 -> 4 8 -> 3 -> 6 -> 7 8 -> 10 -> 14 -> 13 思路: 从根节点开始,把自己的值放在一个数组里,然后把这个数组传给它的子节点,子节点同样把自己的值放在这个数组里,又传给自己的子节点,

  • 利用go语言实现查找二叉树中的最大宽度

    利用go语言实现查找二叉树中的最大宽度

    目录 介绍 流程 代码 二叉树结构体 测试代码 查找二叉树最大宽度的代码 代码解读 介绍 这道题是这样的,有一个二叉树,让求出这颗Bt树里面最大的宽度是有几个节点,同时还要求出最大宽度的这些节点在第几层? 比如:下面这颗树,它每层最大的宽度是3,所在的层数是在第3层 流程 这个题主要是使用队列的方式来存储需要遍历的节点 同时还需要几个变量来存储最大的宽度(maxWidth).每层有几个节点(count).最大宽度所在的层(maxInrow).当前层最后一个节点(currentRowEndNode

  • Python语言描述KNN算法与Kd树

    Python语言描述KNN算法与Kd树

    最近邻法和k-近邻法 下面图片中只有三种豆,有三个豆是未知的种类,如何判定他们的种类? 提供一种思路,即:未知的豆离哪种豆最近就认为未知豆和该豆是同一种类.由此,我们引出最近邻算法的定义:为了判定未知样本的类别,以全部训练样本作为代表点,计算未知样本与所有训练样本的距离,并以最近邻者的类别作为决策未知样本类别的唯一依据.但是,最近邻算法明显是存在缺陷的,比如下面的例子:有一个未知形状(图中绿色的圆点),如何判断它是什么形状? 显然,最近邻算法的缺陷--对噪声数据过于敏感,为了解决这个问题,我们可

  • Java语言Consistent Hash算法学习笔记（代码示例）

    本文研究的主要是ConsistentHashing算法代码. 一致性哈希(Consistent Hash) 协议简介 一致性哈希算法在1997年由麻省理工学院提出(参见0),设计目标是为了解决因特网中的热点(Hot pot)问题,初衷和CARP十分类似.一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用. 哈希算法 一致性哈希提出了在动态变化的Cache环境中,哈希算法应该满足的4个适应条件: 平衡性(Balance) 平衡性是指哈希的结果能够尽可能分

随机推荐