网站设计用什么软件做的,口碑好的盐城网站开发,网络营销策略是什么,网络培训的网站建设性质1#xff1a;一棵非空二叉树的第i层上最多有2^(i-1)个结点#xff0c;#xff08;i1#xff09;。
性质2#xff1a;一棵深度为k的二叉树中#xff0c;最多具有2^k-1个结点#xff0c;最少有k个结点。
性质3#xff1a;对于一棵非空的二叉树#xff0c;度为…性质1一棵非空二叉树的第i层上最多有2^(i-1)个结点i1。
性质2一棵深度为k的二叉树中最多具有2^k-1个结点最少有k个结点。
性质3对于一棵非空的二叉树度为0的结点即叶子结点总比度为1的结点多一个即叶子结点数为n0度为2的结点数为n2则有n0n21。
证明如果n0表示度为0即叶子结点的结点数用n1表示度为1的结点数n2表示度为2的结点数n表示整个完全二叉树的结点总数则有nn0n1n2根据二叉树和树的性质可知nn12xn21所有结点的度数之和加1等于结点总数根据两个等式可知n0n1n2n12xn21即n2n0-1也即n0n21。
性质4具有n个结点的完全二叉树深度为(log2(n))1。
证明根据性质2深度为k的二叉树最多有2k-1个结点且完全二叉树的定义是与同深度的满二叉树前边的编号相同即它们的结点总数n位于k层和k-1层的满二叉树容量之间即2(k-1)-1 n 2k-1之间或2(k-1) n 2^k两边同时取对数得k-1log2(n)k又因层数为整数故log2(n)k-1即klog2(n)1。
性质5对具有n个结点的完全二叉树如果按照从上至下和从左至右的顺序对二叉树的所有结点从1开始编号则对于任意的序号为i的结点有
如果i1那么序号为i的结点的双亲结点序号为i/2
如果i1那么序号为i的结点为根节点无双亲结点
如果2in那么序号为i的结点的左孩子结点序号为2i
如果2in那么序号为i的结点无左孩子
如果2i1n那么序号为i的结点右孩子序号为2i1
如果2i1n那么序号为i的结点无右孩子。
