锐客网

  1. 首页 > 睿知 > it技术 > >

go语言二叉树的深度 leetcode 二叉树深度( 二 )

IT技术Wamp


性质1：二叉树的第i层上至多有2^（i-1）（i≥1）个节点 。
性质2：深度为h的二叉树中至多含有2^h-1个节点 。
性质3：若在任意一棵二叉树中，有n0个叶子节点 ， 有n2个度为2的节点 ， 则必有n0=n2+1 。
性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数） 。
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n） ， 那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点 。
当i1时，该节点的双亲节点的编号为i/2 。
若2i≤n，则有编号为2i的左节点，否则没有左节点 。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点
二叉树的深度和高度有什么区别??一、概念不同
深度是从根节点数到它go语言二叉树的深度的叶节点，高度是从叶节点数到它的根节点 。
二叉树的深度是指所有结点中最深的结点所在的层数 。
对于整棵树来说，最深的叶结点的深度就是树的深度go语言二叉树的深度；树根的高度就是树的高度 。这样树的高度和深度是相等的 。
对于树中相同深度的每个结点来说，它们的高度不一定相同，这取决于每个结点下面的叶结点的深度 。
二、定义不同
高度和深度是相反的表示，深度是从上到下数的，而高度是从下往上数 。
三、计算方式不同
1、二叉树深度算法如下：
深度为m的满二叉树有2^m-1个结点；
具有n个结点的完全二叉树的深度为[log2n]+1.（log2n是以2为底n的对数） 。
2、分析二叉树的深度（高度）和它的左、右子树深度之间的关系 。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1 。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1。
扩展资料：
树是一种重要的非线性数据结构，直观地看 ， 它是数据元素按分支关系组织起来的结构，很象自然界中的树那样 。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示 。
树在计算机领域中也得到广泛应用，如在编译源程序如下时 ， 可用树表示源源程序如下的语法结构 。又如在数据库系统中，树型结构也是信息的重要组织形式之一 。一切具有层次关系的问题都可用树来描述 。满二叉树 ， 完全二叉树，排序二叉树 。
在计算机科学中，二叉树是每个结点最多有两个子树的有序树 。通常子树的根被称作“左子树”和“右子树” 。二叉树常被用作二叉查找树和二叉堆或是二叉排序树 。
参考资料来源：百度百科-二叉树
二叉树的深度是什么？想知道二叉树的深度就要先要判断节点 ， 以下是计算二叉树的详细步骤：
1、一颗树只有一个节点，它的深度是1；
2、二叉树的根节点只有左子树而没有右子树，那么可以判断 ， 二叉树的深度应该是其左子树的深度加1；
3、二叉树的根节点只有右子树而没有左子树，那么可以判断，那么二叉树的深度应该是其右树的深度加1；
4、二叉树的根节点既有右子树又有左子树，那么可以判断，那么二叉树的深度应该是其左右子树的深度较大值加1 。
扩展资料：
从根结点开始，假设根结点为第1层 ， 根结点的子节点为第2层，依此类推 ， 如果某一个结点位于第L层，则其子节点位于第L+1层 。
由m（m≥0）棵互不相交的树构成一片森林 。如果把一棵非空的树的根结点删除 ， 则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成 。

推荐阅读


上一篇：chatgpt研发金费，研发金额

下一篇：牛肉什么炖汤好吃视频，牛肉炖什么汤好喝