树的入门与习题 _结点

在数据结构中，树是比较抽象而去最重要的内容，但是它公式多，而去变化多，问法多，很难理解，现在是本人从个人学习的角度出发，尝试着给大家分享我对树的理解和一些习题的理解首先，树不要干巴巴看它概念，它其实是一种类似家族关系的很温馨的分支层次关系的数据结构，你看它的称呼“孩子，兄弟，父结点，堂兄弟”，多温馨，我一直都努力把它往更生动形象的现实的例子去想，去套，发现也确实能够更好理解它。概念：
（1）度：
一个结点的孩子个数，称之为【该结点的度】（理解为这个结点生育的孩子的总数）
所有结点的度数中，最大的度数称为【树的度】（某个结点剩余的孩子的最大数，称之为这个家族树的生育最大（度）数，最能生，代表着该家族的生育能力天花板）
（2）深度：从上往下数，根结点深度1，根结点的子结点深度2，以此类推…
（3）高度：从下往上数，叶子结点所在层高度1，以此类推
深度 = = 高度
设总结点数为n （4）结点总度数：所有结点的度数之和，不用数，思考：除根结点外，每个结点头顶上都仅连着一条边，一个结点对应一条边，n个结点就一定会有n-1条边（记住除了头顶上没有边的根结点），一条边就会贡献一个度，所以，总度数应该就是： n - 1 （除去头顶上没有边的，不能奉献度的根结点）
结点总度数 = 总结点数 - 1
（5）总结点数：即一棵树共有多少个结点，按照上面式子简单可以得到：
总结点数 = 结点总度数 + 1
（一般考察的时候题目肯定要么给出总度数，要么给出总结点数，公式只是简单的 + 1 -1关系）
巧记：根结点因为是所有子孙结点的祖宗，所以它比较老，头上一根毛都没有，求总度数（树家族成员总毛数）的时候，要记得仅仅根结点没毛，其它每个成员有一根毛，也就贡献一个度，N个成员N-1根毛
（6）树的路径长度：从树的根结点，到每个结点的路径长度的总和。
想像成老祖宗要去探望每一个孙子们，走过的路的总和，就是树的路径长度。
（7）公式：高度为H，度为m，则该树总结点数至少有：n = h+m-1
理解：要使结点数最少，你想象你是一个抠门的大汉，要完成一个工程：高度H，度为M，要最少的结点数（预算）
那你是不是想，随便一层度为m，赶紧满足它的要求，除了那一层，其余每1层我都只放1个结点
那么就有：h-1 层每层放1个，即 h-1 个；第h层我就敷衍满足你放m个
所以就使最少的结点数至少至少有：n = h + m -1

文章插图
总结点数为N，度为m，高度至多是：h = n - m + 1
理解：你还是一个抠门的大汉，但是这次预算给你卡死了n，要求最高的高度，则每层只放一个结点，到最后一层才放m个结点，这样就满足度为n，且要高度最高
那么开始放的时候，先拿掉m个结点，即剩下 n-m 个结点, 每层放一个，就可以放 n-m层；最后一层放m个，就一共是 n-m+1层
所以 h = n-m+1
例：对于一棵有n个结点，度为4的树来说，最大高度为：
首先抽出 4 个，n-4
剩下n-4个结点，每层放一个，前面共放了n-4层，最后一层把抽出的4个放上去
即 h = n - 4 + 1 = n -3 层
例：度为4，高度为h的树，结点数至少有：
首先留出一层放4个
其余h-1层每层放1个，共h-1个
所以共： h-1+4 = h+3 个
例：一棵度为3的树，结点数 50，则最小高度是：5
这次预算n=50，度m=3，你还是那个抠门大汉，让你尽可能使高低搭得低一点，那么很明显，除了根结点1没办法改变，其余每一层尽可能多地塞满结点，即可让高度最低