数据结构-----树的易错点
1.树的度和m叉树
•度为m的树（度表示该结点有多少个孩子（分支））
任意结点的度<=m(最多m个孩子)
至少又一个结点度=m(有m个孩子)
一定是非空树，至少有m+1个结点
•m叉树
任意结点的度<=m(最多有m个孩子)
允许所有结点的度都<m
可以是空树
2.m叉树第i层至多有
个结点或度为m的树第i层至多有个结点
二叉树第i层至多有个结点
3.高度为h的m叉树至多
个结点
高度为h的二叉树至多有个结点
注：
在这里，树的高度和深度可以看作相同的概念，因为这里侧重于树有几层，但是如果侧重于结点，那么高度和深度的概念就不同了
树的深度：(从上往下数)
- 节点 D、E 和 F 的深度都为 2，因为从根节点 A 到节点 D ，E，F需要经过 2 条边。
树的高度：(从下往上数)
- 节点 D、E 和 F 的高度都为 1，因为它们都到达任意叶子节点的路径长度最短，只需要经过 1 条边。
总的来说：
- 树的深度是指从根节点到某个节点的路径长度。
- 树的高度是指从某个节点到达任意叶子节点的最长路径长度。
4.高度为h的m叉树至少有h个结点（高度为h，度为m的树至少有h+m-1个结点）
5.具有n个结点的m叉树的最小高度为
最小高度----每一个结点都有m个孩子
•
•
•
•=
(向上取整)
6.二叉树
(1).设非空二叉树中度为0，1，和2的结点个数分别为n0，n1，n2,则n0=n2+1（叶子节点的个数要比二分支节点的个数多一个）
假设结点总数为n
①n=n0+n1+n2
②n=n1+2n2+1(树的节点数=总度数+1)
(2).满二叉树
高度为h的二叉树，有个结点
1.只有最后一层有叶子结点
2.不存在度为1的结点
3.按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1,结点i的父节点为i/2（向下取整）
6/2=3，7/2(向下取整)=3,所以6，7的父节点为3
(3).完全二叉树
将叶子节点从大到小删去的，都可以称为完全二叉树，例如
右下角的图，6号结点在满二叉树中本来应该为7，所以序号变了，不是完全二叉树
得出结论
完全二叉树不一定是满二叉树，满二叉树一定是完全二叉树
①只有最后两层可以有叶子节点
②最多只有1个度为1的结点
③按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1,结点i的父节点为i/2（向下取整）
④如果一个完全二叉树有n个结点，那么(向下取整)为分支节点，
(向下取整)为叶子节点
⑤如果某个节点只有1个结点，那么这个结点只可能是左孩子，不会是右孩子
⑥两个结论均正确
•具有n个（n>0）结点的完全二叉树的高度h（深度）为(向上取整)
推导过程
高为(h)的满二叉树共有个结点
高为(h-1)的满二叉树共有个结点
•具有n个（n>0）结点的完全二叉树的高度h（深度）为(向下取整)
高为h的完全二叉树至少个结点
高为h的完全二叉树至少个结点
(向下取整)
⑦对于完全二叉树，可以优结点数n，推出度为0，1和2的结点个数为n0，n1和n2
完全二叉树最多只有一个度为1的结点，即
n1=0或1
n0=n2+1--->n0+n1一定为奇数
若完全二叉树有2k个结点，则必有n1=1，n0=k，n2=k-1
若完全二叉树有2k个结点，则必有n1=0，n0=k，n2=k-1
(4).二叉排序树
1.左子树上所有结点的关键字均小于根结点的关键字;
3.左子树和右子树又各是一棵二叉排序树。
(5).平衡二叉树
树上任一结点的左子树和右子树深度(高度)之差不超过1
