网站建设营销型,wordpress登录界面修改,h5手机网站实例,苏州网上商城搭建目录
1.什么是二叉树#xff08;可以跳过 目录跳转#xff09;
2.特殊的二叉树#xff08;满二叉树/完全二叉树#xff09;
2.1 基础知识
2.2 满二叉树
2.3 完全二叉树
3.二叉树的数学奥秘#xff08;主体#xff09;
3.1 高度与节点个数
3.2* 度
4.运用二叉树的…目录
1.什么是二叉树可以跳过 目录跳转
2.特殊的二叉树满二叉树/完全二叉树
2.1 基础知识
2.2 满二叉树
2.3 完全二叉树
3.二叉树的数学奥秘主体
3.1 高度与节点个数
3.2* 度
4.运用二叉树的数学奥秘做题
4.1 P1
4.2 P2
4.3 P3
4.4 P4 1.什么是二叉树可以跳过 目录跳转 数据结构当中树是一种很重要的结构在树当中二叉树又是极为特殊、应用广泛的一种那什么是二叉树呢 我们首先回忆一下“度”的概念树是由节点组织起来的每一个节点都有自己的分叉即自己的子树个数。如图中的 1节点它的度就是3因为 1节点是有三个分叉 / 子树 2 3 4。再如图中的 4节点它的度就是1因为 1节点是有三个分叉 / 子树 8。再比如图中的 9节点它的度就是0因为它压根就没有分叉 / 子树。 而二叉树就是在树的基础上规定 1. 二叉树的所有节点的度都是小于等于2的二叉树不存在度大于2的节点。通俗一点理解二叉树的节点最多有两个叉 / 子树也可能只有一个叉甚至没有叉。 2. 二叉树有左右子树之分一个节点最多有两个分叉一个节点的左边的子树叫做左子树右边的子树叫做右子树。举个下图中的例子3节点的左子树就是2子树3节点的右子树就是8子树8的左子树是6子树8节点的右子树是空NULL空树;4节点的左右子树都是空树NULL。还有这个节点的子树的左右顺序是固定的次序不能颠倒也因此二叉树是有序树。 轻松一下例如现实当中下面这棵树就是一棵二叉树当然你需要把这棵树倒转一下看度都小于等于2 2.特殊的二叉树满二叉树/完全二叉树
2.1 基础知识 首先对一个普通二叉树我们要建立层与高度的概念如图根节点3是第一层第一层有2个节点节点2和节点8组成了第二层第二层有2个节点节点2 3 6处在二叉树的第三层二叉树的第三层有3个节点。这棵二叉树的高度h5。 2.2 满二叉树 在这个基础之上我们引入满二叉树的概念如果一个二叉树高h那么满二叉树就是每一层的节点的个数都达到了MAX最大值也就是对于第k层来说它一定有2 ^k-1个节点。所以根据等比数列来说这个满二叉树它的总结点个数一定是2^0 2^1 2^2 2^3 ...... 2^(h-1) 2^h - 1个节点。反过来讲如果一棵满二叉树的总节点个数为N那它的高度就是log2(N1)。 如上面的三个图第一个图和第二个图他们都是满二叉树因为他们的每一层节点的个数都已经达到了最大值第k层都是2^(k-1)个节点。但是第三个图这个二叉树的最后一层也就是第4层个数没有达到这一层所能达到的最大值所以第三个图就不是满二叉树。 不过第三个图它虽然不是满二叉树但是他是完全二叉树 2.3 完全二叉树 先不去看复杂的概念我们假设一棵完全二叉树有h层就拿图中这个完全二叉树它有的高度h是4。 那么如果只看最后一层往上的h-1个层本例中就是上3层暂时不看最后一层不看第4层如果一棵整树是完全二叉树那么上h-1层就是一棵满二叉树你看第1 2 3层组成的二叉树就是一棵满二叉树这是第一点完全二叉树所满足的。 然后第二点我们只看最后一层如果一棵整树是完全二叉树那么这最后一层也就是图上的第4层的所有节点在顺序上是连续的没有跳跃间隔的关于连续的没有跳跃间隔的我们看一下例子就明白了 看第一个图我们看最后一层的所有节点它就不是完全连续的是有间断的所以这棵树不是完全二叉树第二个图的的最后一层的所有节点它是完全连续的所以这棵树是完全二叉树第三个图的最后一层的所有节点它就不是完全连续的是有间断的所以这棵树不是完全二叉树。 所以只要满足以下两点这就是一棵完全二叉树设其高度为h 1.上h-1层构成一棵满二叉树。 2.第h层所有节点在顺序上是连续的没有跳跃间隔的。 所以其实一棵满二叉树一定是一棵完全二叉树因为满二叉树上h-1层是满二叉树且其最后一层也是连续的没有跳跃间隔的。 3.二叉树的数学奥秘主体
3.1 高度与节点个数 在假设根节点是第1层不讨论空树的情况下 秘密1如果树有h层。对于某一层来说比如对于第k层这一层所有节点的个数最多是2^(k-1)个。 秘密2如果树有h层那这棵树总结点的最大个数就是2^h - 1个。 秘密3如果一棵满二叉树的高度为h那它的所有节点个数和是2^h - 1。 如果一棵满二叉树的总节点个数和为N那它的高度就是log2(N1)。 秘密4如果一棵完全二叉树的高度为h那它的所有节点个数和是在这样一个区间 ( 2^(h-1)2^h - 1 ]左开右闭。 如果一棵完全二叉树的节点个数和为N那么它的高度就是log2(N1)必须注意 log2(N1)可能不是整数如果不是整数那就默认往大取整。其实很好区分如果N1恰好是2的指数的结果那么高度就是log2(N1)而如果N1不是2的指数的结果那么高度就是把N1往大补成2的指数的结果高度是往大取整的log2(N1)。 详情练习请跳转至4.1。 3.2* 度 度每一个节点都有自己的度度就是一个节点的分叉数即往下有多少棵子树。 对于任何一棵二叉树度为0的节点的数量也即叶子节点的数量为n0度为2的分支节点的数量为n2。那么一定满足n0 n2 1。也即度为0的节点的数量永远比度为2的节点的数量多1个 我们随便举几个例子你可以发现度都满足上述关系 如果二叉树只有一个根节点它的度是0度为2的节点不存在n0 1n2 0n0 n2 1。 如上图二叉树节点1的度为1节点2的度为0n0 1n2 0n0 n2 1。 如上图二叉树节点1的度为2节点2的度为0节点3的度为0n0 2n2 1n0 n2 1。 如上图二叉树节点1的度为2节点2的度为1节点3的度为0节点4的度是0n0 2n2 1n0 n2 1。 如上图二叉树节点1的度为2节点2的度为1节点3的度为1节点4的度是0节点5的度为0n0 2n2 1n0 n2 1。 由此迭代判断其实所有的二叉树都是满足n0 n2 1这个数学奥秘的。度为0的节点永远比度为2的节点的数量多一个 简单的从数学的角度证明一下这个结论 一棵二叉树的总度数n度数为0的节点的数量n0×0度数为1的节点的数量n1×1度数为2的节点的数量n2×2。 一棵二叉树的总度数n同时所有节点个数n0n1n2-1。 由上述两个式子可得n12n2n0n1n2-1。 所以有n0n21。 4.运用二叉树的数学奥秘做题
4.1 P1 1.某二叉树共有399个结点。其中有199个度为2的结点。 则读二又树中的叶子结点数为() A. 不存在这样的二叉树 B. 200 C. 198 D. 199 提取题目信息n0 n1 n2399n2 199而且结合我们知道的数学秘密n0 n2 1所以n0 200。所以题干给的第一句话是废的我们只要通过第二句话结合n0 n2 1就可以知道叶子节点的个数即度为0的节点的个数为200。故选B。 4.2 P2 2.在具有2n个结点的完全二叉树中叶子结点个数为() A. n B. n1 C. n-1 D. n/2 提取题目信息n0 n1 n2 2n和是一个偶数。然后这是一棵完全二叉树完全二叉树有一个十分重要的特点注意观察下图度为1的节点个数只能有1个或0个然后再无其他个数最后一层的节点的度都是0上面是一个满二叉树出现度为1的节点数目只能最多有1个,所以完全二叉树中度为1的节点个数 n1 非0即1非1即0。 n0 n2 1这个奥秘我们结合题设n0 n1 n2 2n则2*n2 1 n1 2n。等式左侧的2*n2 1是一个奇数然后这个奇数加上了n1等式的右侧2n是一个偶数。奇数只能通过加一个奇数才能得到偶数所以n1是奇数。 n1非0即1n1是奇数所以n1 1。 所以2*n2 1 1 2n所以度为2的节点的个数n2 n-1。所以叶子节点的个数n0 n2 1 n - 1 1 n故选A。 4.3 P3 3.一棵完全二叉树的节点数为531个那么这棵树的高度为 A 11 B 10 C 8 D 12 我们直接根据3.1当中的规律N531我们把N1 532log2(532)往大取整就是层数2^9 512 532 2^10 1024往上取整则一共有10层。故选B。 4.4 P4 4.一个具有767个节点的完全二叉树其叶子节点个数为 A 383 B 384 C 385 D 386 n0 n1 n2 767完全二叉树n1不是1就是0n0 n2 n0 n0 - 1 2*n0 - 1是一个奇数。2*n0 - 1 n1 767右侧是奇数所以左侧的奇数2*n0 - 1必须通过加一个偶数才能保持其是奇数所以n1是偶数又n1 非1即0所以n1 0。 所以2*n0 - 1 767所以叶子节点的个数n0 768/2 384。故选B。
