-
树的高度
2019-03-10 15:29:20现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度 输入描述: 输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成, 下面是n-1行,每行有两个...题目描述
现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度
输入描述:
输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成,
下面是n-1行,每行有两个整数,第一个数表示父节点的编号,第二个数表示子节点的编号
输出描述:
输出树的高度,为一个整数
示例1
输入
5
0 1
0 2
1 3
1 4
输出
3#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<string> #include<cctype> #include<iostream> using namespace std; vector<int> G[1005]; int n; int dfs(int x){ if(G[x].size()==0) return 1; else if(G[x].size()==1) return 1 + dfs(G[x][0]); else return 1 + max(dfs(G[x][0]), dfs(G[x][1])); } int main(){ scanf("%d",&n); int deg[1005]; memset(deg,-1,sizeof(deg)); int u,v; for(int i=0;i<n-1;i++){ scanf("%d%d",&u,&v); G[u].push_back(v); deg[v]=u; } int root; for(int i=0;i<n;i++){ if(deg[i] == -1){ root = i; break; } } cout<<dfs(root)<<endl; return 0; }
-
树的高度和深度以及结点的高度和深度
2018-11-16 16:46:20对于 树的高度和深度(以及结点的高度和深度) 看了几本不同的书,都有各自的说法,多方查证吧,花了很多时间,最后归纳一个能说服我的说法吧。(´。• ᵕ •。`) ♡ 树的高度和深度 深度是从上往下定义的,从根...有个缺点,看到什么东西不管是不是重点只要说不通总是爱钻牛角尖。
对于 树的高度和深度(以及结点的高度和深度) 看了几本不同的书,都有各自的说法,多方查证吧,花了很多时间,最后归纳一下。(´。• ᵕ •。`) ♡
树的高度和深度
深度定义是从上往下的,高度定义是从下往上的。(其实不用在意这个,反正树的深度高度怎么数都一样的)。
深度和高度涉及到结点的层数,有的教材规定根结点在第0层,有的则规定根结点在第1层。原理都是一样的,因教材而异。
树从根结点开始往下数,叶子结点所在的最大层数称为 树的深度。
有的教材对于树的高度定义是高度就是深度(层数是0123,深度=高度=3;层数是1234,深度=高度=4);而有的教材树的高度则是看一共有几层。也就是说不论根节点在第几层,树的深度都是和最大层的叶子节点一样。而树的高度只要看有几层就行了(0123是四层,1234也是四层)。总之在我看来:
有两种说法:
- 高度就是深度
- 看层数:
如果根结点第0,层数=深度=高度-1
如果根结点第1,层数=深度=高度
举个栗子_(:3 」∠ )_:
图 左 右 层数 从第0层开始 从第1层开始 最大层数 4 5 深度 4 5 高度(高度=深度) 4 5 高度(数层数) 5 5 补充:
根节点在第0层时候,按照北大数据结构视频的说法就是高度数结点数,深度数路径。从A到G,节点是5层,中间有4段路径,所以深度4,高度5。
其实也可以理解为数高度时候叶子结点从1开始数。因此空数高度0,只有一个根节点高度1。但是在清华大学 邓俊辉数据结构书中如下:
这本书中可以看出数高度时候叶子结点是从0开始的,因此空数高度-1,只有一个根节点高度0。
结点的高度和深度
结点的深度也是从根结点开始数,是第几层也决定于根结点在第0层还是第1层。根结点的高度则取决于它的子树,该节点子树中最远的那个叶子结点作为1开始数。例如对于BCD三个点:
B的子树是C和D,数B的高度时候,B的子树中离B最远的叶子节点是G,所以G高度为1,B高度4,D高度3。但是C是叶子节点,C没有真子树,C高度就是1。
图 左 右 BCD高度(叶子节点>=0) 4 1 3 4 1 3 BCD高度(叶子节点>0) 3 0 2 3 0 2 BCD深度 1 2 2 2 3 3
参考书籍和视频课:
- 《数据结构(C++版) 》 第二版 清华大学出版社 王红梅
- 《数据结构(C++语言版)》 第三版 清华大学出版社 邓俊辉
- 《数据结构(用面向对象方法与C++语言描述) 》 第二版 清华大学出版社 殷人昆
- 《数据结构高分笔记》2019版 机械工业出版社 天勤考研
- 北京大学 数据结构与算法
- 华南理工大学 数据结构与算法
(*´ω`)人(´ω`*)我是萝莉安,今天钻牛角尖也成功了呢
-
计算树的高度
2018-07-22 10:55:10树的高度就是数的层数。那怎么计算树的高度呢?我们可以分贝将左节点的高度计算出来和右 节点的高度计算出来,在比较大小。大的就是树的高度。 其实不管是求树的高度还是叶子节点个数,都是在遍历整个树,只...树的高度就是数的层数。那怎么计算树的高度呢?我们可以分贝将左节点的高度计算出来和右
节点的高度计算出来,在比较大小。大的就是树的高度。
其实不管是求树的高度还是叶子节点个数,都是在遍历整个树,只不过在遍历的过程中满足了某种条件就做出一定的处理,所以树的遍历是最基本的。
typedef struct BiTNode
{
int data;
struct BiTNode* lchild, *rchild;
}BiTNode;int Deepth(BiTNode *root)
{
int deepthleft = 0;
int deepthright = 0;
int deepcount = 0;
if (root == NULL)
{
deepcount = 0;
return deepcount;
}
//求左子树的高度
deepthleft = Deepth(root->lchild);
//求右子树的高度
deepthright = Deepth(root->rchild);//每次都要加上根节点的高度
deepcount = 1+ ((deepthleft > deepthright) ? deepthleft : deepthright);
return deepcount;
}void main()
{
BiTNode t1, t2, t3, t4, t5;
memset(&t1, 0, sizeof(BiTNode));
memset(&t2, 0, sizeof(BiTNode));
memset(&t3, 0, sizeof(BiTNode));
memset(&t4, 0, sizeof(BiTNode));
memset(&t5, 0, sizeof(BiTNode));t1.data = 1;
t2.data = 2;
t3.data = 3;
t4.data = 4;
t5.data = 5;t1.lchild = &t2;
t1.rchild = &t3;
t2.rchild = &t4;
t3.lchild = &t5;
int deep=Deepth(&t1);
printf("deep=%d ", Deepth(&t1));
system("pause");
} -
树的理解(一):树的高度
2020-03-20 11:11:15树的高度 树的高度的递归思想: 根据树的高度的定义,对于任意一个节点来说,树的高度都等于左子树和右子树中比较大的那个 + 该节点高度1之和。 如果节点为空节点,那么高度就为0,因此,树的高度可以利用递归思想求...树的高度
树的高度的递归思想:
根据树的高度的定义,对于任意一个节点来说,树的高度都等于左子树和右子树中比较大的那个 + 该节点高度1之和。
如果节点为空节点,那么高度就为0,因此,树的高度可以利用递归思想求出:public int maxDepth(TreeNode root) { if(root == null) return 0; return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1; }
平衡二叉树
那么根据树的高度,由此可以引申出树是否平衡这一概念,也就是平衡二叉树。
平衡二叉树的递归思想:
根据平衡二叉树的定义,一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
想要知道每个节点的左右子树的高度差,首先要知道左右子树的高度。
根据树的高度的递归思想,可以轻松得出左右子树的高度,那么进而判断二者之间的绝对值是否大于1,就可以得出答案。public boolean isBalanced(TreeNode root) { int[] isBalanced = {1}; isBalanced(root,isBalanced); return isBalanced[0] > 0; } //isBalanced用来判断一棵树是否平衡 private int isBalanced(TreeNode root,int[] isBalanced) { if(root == null)return 0; int lh = isBalanced(root.left,isBalanced);//分别求出左右子树的高度, int rh = isBalanced(root.right,isBalanced); if(Math.abs(lh - rh) > 1)//如果高度差大于1,就说明树不平衡 isBalanced[0] = -1; return Math.max(lh,rh) + 1; }
二叉树的直径
二叉树的直径是一个新的概念,我们先来看它的定义:
“一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。”
“注意:两结点之间的路径长度是以它们之间边的数目表示。”这个定义看起来还是很抽象,我们不容易从中发现他的特性,但是通过举例,我们可以很容易将这一概念和树的高度联系起来。
我们来看下面的例子:
1 / \ 2 3 / \ 4 5
这棵二叉树的直径长度为3,它的长度是路径 [4,2,1,3] 或者 [5,2,1,3],我们根据这两个路径的起始节点和结束节点可以发现其实就是以左叶子节点中的一个到右叶子节点中的一个的距离。
那么回头再看定义中"任意两个结点路径长度中的最大值",就可以发现,树的直径无非就是求树的左子树高度与右子树的高度之和。
根据这一思路,和上面树的高度的递归思想,不难写出如下代码:public int diameterOfBinaryTree(TreeNode root) { int[] res = {0}; findMaxHeight(root,res); return res[0]; } private int findMaxHeight(TreeNode root,int[] res) { if(root == null)return 0; int lh = findMaxHeight( root.left, res); int rh = findMaxHeight( root.right, res); res[0] = Math.max(res[0],lh + rh); return Math.max(lh,rh) + 1; }
树的最小深度
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/submissions/
树的最小深度就是根节点到叶子节点的最小距离,和树的最大深度正好相反,所以根据文章开头的树的最大深度的代码来讲,只需要将最后的返回条件改为Math.min(left,right)即可。
class Solution { public int minDepth(TreeNode root) { if(root == null) return 0; int left = minDepth(root.left); int right = minDepth(root.right); //下面这行代码的出现是因为如果有了左右子树其中一个为空时,最短深度就为另外一个不为空的树(根据题意的设定) if(left == 0 || right == 0) return left + right + 1; return Math.min(left,right) + 1; } }
另外一种递归解法
class Solution { public int minDepth(TreeNode root) { if(root == null)return 0; int[] res = {Integer.MAX_VALUE}; minDepth(root,res,1); return res[0]; } private void minDepth(TreeNode node,int[] res,int cur_Dep) { if(node.left == null && node.right == null) { res[0] = Math.min(res[0],cur_Dep); return; } if(cur_Dep >= res[0])return; if(node.left != null) minDepth(node.left,res,cur_Dep + 1); if(node.right != null) minDepth(node.right,res,cur_Dep + 1); } }
总结
无论是平衡树的概念,还是二叉树的直径的概念。其实核心概念都是树的高度。
-
获取树的高度
2020-07-27 20:08:54返回树的高度:层次遍历 求树的高度可以采用递归,层次遍历两种方法。本文选用层次遍历的方法,本质就是在层次遍历的过程中计数,当计数器达到本层元素个数时意味着进入了新的一层。 以下代码: int maxDepth... -
树的高度,节点的深度和高度
2020-07-22 14:45:36节点深度高度以及树的高度,不同的教材可能定义不同,本文是参考的《数据结构与算法python》第八章201页的定义 1 节/结点的深度和高度 1.1 深度depth 假定p是树T中的一个节点,那么p的深度就是节点p的祖先的个数,不... -
求树的高度
2017-12-26 08:56:40一提到树 大家想到的应该就是递归求解,今天来学习下树的高度求解。 假设用一个函数getHeight(x)表示x节点的树的高度,那么 x节点的树的高度就是 x的左节点或者右节点的最大高度 + 1. 即 getHeight(x) = Math.... -
关于树的高度深度
2020-06-08 14:58:47关于树的高度深度的一些总结结点和树的深度和高度 结点和树的深度和高度 结点的深度:从上往下数 根据从树根到n结点处的路径长度来数(n-1),有的地方把树根深度定义为1,有的地方把树根深度定义为0(本书); 结点... -
红黑树的高度
2018-08-14 21:41:07在复习红黑树的特性时,产生了这样的一个疑问,红黑树的高度是多少呢?在Java8,HashMap所使用的拉链法散列表中,如果储存元素的键值与原来储存元素的键值发生了Hash冲突,如果val值不一样,会将该元素存放在红黑树的... -
树的高度python
2018-05-10 20:38:17碰到一道数据结构相关题目:题目描述现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度输入描述:输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1... -
树的高度和深度
2019-09-02 22:42:48树的高度和深度 深度定义是从上往下的,高度定义是从下往上的。(其实不用在意这个,反正树的深度高度怎么数都一样的)。 深度和高度涉及到结点的层数,有的教材规定根结点在第0层,有的则规定根结点在第1层。原理都... -
多叉树的构建和树的高度的计算
2018-04-10 21:33:05题目描述现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度输入描述:输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成, 下面是n-1行,每行... -
树的高度和深度的区别
2018-10-30 16:55:10对于树的基本概念上理解,对于才接触数据结构的人来说,树的高度和深度是一个容易混淆的知识点,现解释如下: 1.高度 对于高度的理解,我们不管他数据结构什么什么知识,就拿楼房来说,假如一个人提问:楼房的高度... -
【二叉搜索树 Binary search tree、平衡二叉树Balanced binary tree】时间复杂度与树的高度h相关,所以需要...
2017-09-18 16:52:331.search:时间复杂度为O(h),h为树的高度2.traversal:时间复杂度为O(n),n为树的总结点数。3.insert:时间复杂度为O(h),h为树的高度。4.delete:最坏情况下,时间复杂度为O(h)+指针的移动开销。可以看到,二叉... -
判断一棵树是否为平衡树及求树的高度
2017-07-24 17:41:35所以判断一棵树是否为二叉树,不难想到可以先求出树的高度,再求出左右子树的高度差来判断,那么就想先求树的高度。 求树的高度可以用递归方法,树的高度其实是返回左右子树中高度较高的那一个,求当前的高度则还要... -
树的高度,宽度
2019-05-16 15:55:17//树的孩子兄弟结点定义 typedef struct CSNode { char data; CSNode *nextchild,*nextsibling; } CSNode,*CSTree; /* ...//树的高度 int Height(CSTree bt) { int hl,hr; if(bt ==NULL)... -
2、树的高度
2018-09-18 18:33:46现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度。 输入描述: 输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成, 下面是n-1行,每行有... -
树的高度和深度概念
2019-06-23 12:33:54树的高度和深度概念1.高度2.深度3.总结 1.高度 对于高度的理解,我们不管他数据结构什么什么知识,就拿楼房来说,假如一个人提问:楼房的高度有好高?我们会下意识的从底层开始往上数,假如楼有6层,则我们会说,这...
-
【数据分析-随到随学】Python数据获取
-
python 通过字典实现的并查集按秩合并(并查集merge中size的优化) 解释及模板
-
excel批量生成word.rar
-
大一上学期总结
-
单元测试UnitTest+Pytest【Selenium3】
-
Digital+Camera+Utility+5.zip
-
和自己和解:方法的借鉴level
-
计算机网络基础
-
【数据分析-随到随学】Python语法强化与数据处理
-
Centos8.0: 环境搭建,看这里就够了。
-
webcrawlingNotes.pdf
-
Redhat6.5安装Oracle11g.docx
-
Redis数据库入门与使用
-
【2021】UI自动化测试Selenium3
-
FFmpeg: 抽取音视频数据
-
Vue3 实现 Reactivity
-
【数据分析-随到随学】SPSS调查问卷统计分析
-
数据类型转换、运算符、方法入门
-
30个生涯锦囊,带你跳出迷茫,找到适合你的职业方向
-
转行做IT-第6章 IDEA、方法