新公司网站设计,做图挣钱的网站,网站策划书的基本内容,家具定制十大名牌1.树的度和m叉树
•度为m的树#xff08;度表示该结点有多少个孩子#xff08;分支#xff09;#xff09;
任意结点的度m(最多m个孩子)
至少又一个结点度m(有m个孩子)
一定是非空树#xff0c;至少有m1个结点 •m叉树
任意结点的度m(最多有m个孩子)
允许所…1.树的度和m叉树
•度为m的树度表示该结点有多少个孩子分支
任意结点的度m(最多m个孩子)
至少又一个结点度m(有m个孩子)
一定是非空树至少有m1个结点 •m叉树
任意结点的度m(最多有m个孩子)
允许所有结点的度都m
可以是空树 2.m叉树第i层至多有个结点或度为m的树第i层至多有个结点
二叉树第i层至多有个结点 3.高度为h的m叉树至多个结点
高度为h的二叉树至多有个结点 注 在这里树的高度和深度可以看作相同的概念因为这里侧重于树有几层但是如果侧重于结点那么高度和深度的概念就不同了 树的深度(从上往下数) 节点 D、E 和 F 的深度都为 2因为从根节点 A 到节点 D EF需要经过 2 条边。 树的高度(从下往上数) 节点 D、E 和 F 的高度都为 1因为它们都到达任意叶子节点的路径长度最短只需要经过 1 条边。 总的来说 树的深度是指从根节点到某个节点的路径长度。树的高度是指从某个节点到达任意叶子节点的最长路径长度。 4.高度为h的m叉树至少有h个结点高度为h度为m的树至少有hm-1个结点 5.具有n个结点的m叉树的最小高度为
最小高度----每一个结点都有m个孩子
•
•
•
•(向上取整) 6.二叉树
(1).设非空二叉树中度为01和2的结点个数分别为n0n1n2,则n0n21叶子节点的个数要比二分支节点的个数多一个
假设结点总数为n
①nn0n1n2
②nn12n21(树的节点数总度数1)
(2).满二叉树
高度为h的二叉树有个结点 1.只有最后一层有叶子结点 2.不存在度为1的结点 3.按层序从1开始编号结点i的左孩子为2i右孩子为2i1,结点i的父节点为i/2向下取整 6/237/2(向下取整)3,所以67的父节点为3 (3).完全二叉树
将叶子节点从大到小删去的都可以称为完全二叉树例如 右下角的图6号结点在满二叉树中本来应该为7所以序号变了不是完全二叉树 得出结论 完全二叉树不一定是满二叉树满二叉树一定是完全二叉树 ①只有最后两层可以有叶子节点 ②最多只有1个度为1的结点
③按层序从1开始编号结点i的左孩子为2i右孩子为2i1,结点i的父节点为i/2向下取整
④如果一个完全二叉树有n个结点那么(向下取整)为分支节点(向下取整)为叶子节点
⑤如果某个节点只有1个结点那么这个结点只可能是左孩子不会是右孩子
⑥两个结论均正确
•具有n个n0结点的完全二叉树的高度h深度为(向上取整)
推导过程
高为(h)的满二叉树共有个结点
高为(h-1)的满二叉树共有个结点 •具有n个n0结点的完全二叉树的高度h深度为(向下取整)
高为h的完全二叉树至少个结点
高为h的完全二叉树至少个结点 (向下取整)
⑦对于完全二叉树可以优结点数n推出度为01和2的结点个数为n0n1和n2
完全二叉树最多只有一个度为1的结点即
n10或1
n0n21---n0n1一定为奇数
若完全二叉树有2k个结点则必有n11n0kn2k-1
若完全二叉树有2k个结点则必有n10n0kn2k-1 (4).二叉排序树
1.左子树上所有结点的关键字均小于根结点的关键字;
3.左子树和右子树又各是一棵二叉排序树。 (5).平衡二叉树
树上任一结点的左子树和右子树深度(高度)之差不超过1
