阳春县建设局网站,广水网站定制,云平台网站建设,家庭装修设计软件哪个好用满二叉树 (Full binary tree)
除最后一层无任何子节点外#xff0c;每一层上的所有结点都有两个子结点二叉树。
国内教程定义#xff1a;一个二叉树#xff0c;如果每一个层的结点数都达到最大值#xff0c;则这个二叉树就是满二叉树。也就是说#xff0c;如果一个二叉树…满二叉树 (Full binary tree)
除最后一层无任何子节点外每一层上的所有结点都有两个子结点二叉树。
国内教程定义一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是(2^k) -1 则它就是满二叉树。
国外(国际)定义:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.
大意为如果一棵二叉树的结点要么是叶子结点要么它有两个子结点这样的树就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点要么它有两个子结点但是反过来不成立因为完全二叉树也满足这个要求但不是满二叉树)
从图形形态上看满二叉树外观上是一个三角形。 从数学上看满二叉树的各个层的结点数形成一个首项为1公比为2的等比数列。
因此由等比数列的公式满二叉树满足如下性质。
1、一个层数为k 的满二叉树总结点数为 。因此满二叉树的结点树一定是奇数个。 2、第i层上的结点数为
3、一个层数为k的满二叉树的叶子结点个数也就是最后一层 完全二叉树 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
可以根据公式进行推导假设n0是度为0的结点总数即叶子结点数n1是度为1的结点总数n2是度为2的结点总数则
①n n0n1n2 其中n为完全二叉树的结点总数又因为一个度为2的结点会有2个子结点一个度为1的结点会有1个子结点除根结点外其他结点都有父结点
②n 1n12*n2 由①、②两式把n2消去得n 2*n0n1-1由于完全二叉树中度为1的结点数只有两种可能0或1由此得到n0n/2 或 n0(n1)/2。
简便来算就是 n0n/2其中n为奇数时n10向上取整n为偶数时n11。可根据完全二叉树的结点总数计算出叶子结点数。 重点出于简便起见,完全二叉树通常采用数组而不是链表存储 对于tree[i]有如下特点
1若i为奇数且i1那么tree的左兄弟为tree[i-1]
2若i为偶数且in那么tree的右兄弟为tree[i1]
3若i1tree的父亲节点为tree[i div 2]
4若2*in那么tree的左孩子为tree[2*i]若2*i1n那么tree的右孩子为tree[2*i1]
5若in div 2,那么tree[i]为叶子结点对应于3
6若i(n-1) div 2.那么tree[i]必有两个孩子对应于4。
7满二叉树一定是完全二叉树完全二叉树不一定是满二叉树。
完全二叉树第i层至多有2^i-1个节点共i层的完全二叉树最多有2^i-1个节点。
特点
1只允许最后一层有空缺结点且空缺在右边即叶子结点只能在层次最大的两层上出现
2对任一结点如果其右子树的深度为j则其左子树的深度必为j或j1。 即度为1的点只有1个或0个
