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
7.在n个结点的二叉链表中,有n+1个空指针域
n个结点中,若每个结点都有左孩子和右孩子,那么最多有2n个指针
反过来,每个结点有且仅有一个父节点,除了头结点以外,所以最少有n-1个指针,那么空指针为2n-(n-1)=n+1