×

二叉树的高度

二叉树的高度（只有一个节点的二叉树的高度（ 深度）是为0还是1）

admin admin 发表于2023-09-14 06:58:03 浏览40 评论0

抢沙发发表评论

本文目录

只有一个节点的二叉树的高度（ 深度）是为0还是1

按照定义树的深度和高度就是树中最大的结点层数。只有一个节点的二叉树，该节点显然是二叉树的根，该树的总层数为1，因此只有一个节点的二叉树的高度（深度）是为1。如果将该二叉树的根节点所在的层次定义为第0层（也可以定义为第1层），则该二叉树的高度（深度）为1，且根节点第0层。

一个有2001个结点的完全二叉树的高度为

完全二叉树度为1的结点数为要么为1，要么为0；由于度为2的结点数和度为0结点数相差为1；所以两者之和必为奇数，现在总结点数为偶数，所以度为1的结点数应为奇数，所以有一个度为1的结点。

树的高度为11。

由完全二叉树的结点数T与高度h的关系为T = 2^h - 1

可知：2^10 - 1《 2001 《 2 ^11 - 1

所以该完全二叉树的高度为11

扩展资料：

按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱结点；除最后一个结点外，每个结点有且仅有一个直接后继结点。

但是，二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么，二叉树的存储结构中并没有反映出来，只能在对二叉树遍历的动态过程中得到这些信息。

为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。

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

求二叉树高度的原理、算法是什么，越详细越好，C语言，谢谢

首先分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。int Depth (BiTree T ){ // 返回二叉树的深度 if ( !T ) depthval = 0; else { depthLeft = Depth( T-》lchild ); depthRight= Depth( T-》rchild ); depthval = 1 + (depthLeft 》 depthRight ? depthLeft : depthRight); } return depthval;}

有N个节点的二叉树，其高度为多少

有N个节点的二叉树，其高度为Ω(logn)。

高度为h≥0的二叉树至少有h+1个结点； 

高度不超过h(≥0)的二叉树至多有2h+1-1个结点； 

含有n≥1个结点的二叉树的高度至多为n-1；

含有n≥1个结点的二叉树的高度至少为logn；

因此其高度为Ω(logn)。

扩展资料：

二叉树性质

性质1：二叉树的第i层上至多有2i-1（i≥1）个节点。

性质2：深度为h的二叉树中至多含有2h-1个节点。

性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。

性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）。

性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n）。

二叉树的高度是什么

二叉树的高度是高度是从下往上数。

二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。

二叉树性质：

若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点。

当i》1时，该节点的双亲节点的编号为i/2。

若2i≤n，则有编号为2i的左节点，否则没有左节点。

若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。

怎么计算二叉树高度

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

int Depth (BiTree T ){ // 返回二叉树的深度

if ( !T ) depthval = 0;

else {

depthLeft = Depth( T-》lchild );

depthRight= Depth( T-》rchild );

depthval = 1 + (depthLeft 》 depthRight ?

depthLeft : depthRight);

}

return depthval;

}

扩展资料：

一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。

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

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

二叉树的高度是多少

高度为h的二叉树上只有度为0和度为2的结点。则此二叉树中所含的结点数至少为除了root层每层只有两个节点，如果root层为0层，那么结果为b，如果root层为1层，那么结果为c！其实有时候这种选择题模棱两可，你知道解题原理就行了！考试的时候要看你考试的要求作答就没问题了！

什么是完全二叉树，并举例说明， 以及树高度、深度的计算，并举例

除了最后一层结点可以不满，其他各层结点都是满的，即第一层有1个结点（根），第2层有2个，第3层有4个，第i层有2^（i-1）个，并且最后一层的结点是从左向右排列的树的高度最底下的为第1层（有的书定义为第0层），依次向上累加树的深度最定的为第1层（有的书定义为第0层），依次向下累加

已知完全二叉树的节点数怎么求高度

完全二叉树除最后一层，其他层都是满结点的。

所以这里总结点700个，这里是偶数，可以判断度为1的结点是1个。

根据二叉树性质n0 = n2 + 1;叶子结点数量等于度为2的结点数+1

n0 + n1 + n2 = 700

n0 + n1 + n0 -1 =700;

2n0 = 701 -n1 （完全二叉树度为1的结点个数要么1，要么0， 叶子结点数为整数，这里也可以推断出度为1的结点个数是1）

n0 = 350

叶子结点数是350

扩展资料：

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。

具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个节点，至多有2k-1个节点。

什么是完全二叉树，并举例说明，以及树高度，深度的计

完全二叉树是指这样的二叉树：除最后一层外,每一层上的结点数均达到最大值；在最后一层上只连续缺少右边的若干结点.具有n 个结点的完全二叉树的深度为+1=7http://www.zybang.com/question/3649d5a8d555b005f160cf9c6796f0a1.html