数据结构-----树的易错点

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