二叉树的深度和高度有什么区别??

Question

为什么有时候书上写
深度:[log2 n]+1;
高度:[log2 (n+1)];
两个有本质区别啊!

Answer 1

一、概念不同

深度是从根节点数到它的叶节点，高度是从叶节点数到它的根节点。

二叉树的深度是指所有结点中最深的结点所在的层数。

对于整棵树来说，最深的叶结点的深度就是树的深度；树根的高度就是树的高度。这样树的高度和深度是相等的。

对于树中相同深度的每个结点来说，它们的高度不一定相同，这取决于每个结点下面的叶结点的深度。

二、定义不同

高度和深度是相反的表示，深度是从上到下数的，而高度是从下往上数。

三、计算方式不同

1、二叉树深度算法如下：

深度为m的满二叉树有2^m-1个结点；

具有n个结点的完全二叉树的深度为[log2n]+1.（log2n是以2为底n的对数）。

2、分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。

扩展资料：

树是一种重要的非线性数据结构，直观地看，它是数据元素按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。

树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。满二叉树，完全二叉树，排序二叉树。

在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”和“右子树”。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

参考资料来源：百度百科-二叉树

Answer 2

区别：深度是从根节点数到它的叶节点，高度是从叶节点数到它的根节点。
二叉树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样的。

Answer 3

图片画错了，最多有两个度

Answer 4

没区别