⼆叉树的基本性质及证明
性质1：⼀棵⾮空⼆叉树的第i层上最多有2^(i-1)个结点，（i>=1）。
性质2：⼀棵深度为k的⼆叉树中，最多具有2^k-1个结点，最少有k个结点。
性质3：对于⼀棵⾮空的⼆叉树，度为0的结点（即叶⼦结点）总⽐度为1的结点多⼀个，即叶⼦结点数为n0，度为2的结点数为n2，则有n0=n2+1。
二叉树的基本性质证明：如果n0表⽰度为0（即叶⼦结点）的结点数，⽤n1表⽰度为1的结点数，n2表⽰度为2的结点数，n表⽰整个完全⼆叉树的结点总数，则有n=n0+n1+n2，根据⼆叉树和树的性质，可知n=n1+2xn2+1（所有结点的度数之和加1等于结点总数），根据两个等式可知n0+n1+n2=n1+2xn2+1，即n2=n0-1，也即n0=n2+1。
性质4：具有n个结点的完全⼆叉树深度为(log2(n))+1。
证明：根据性质2，深度为k的⼆叉树，最多有2^k-1个结点，且完全⼆叉树的定义是与同深度的满⼆叉树前边的编号相同，即它们的结点总数n位于k层和k-1层的满⼆叉树容量之间，即2^(k-1)-1< n <=2^k-1之间，或2^(k-1) <= n <2^k，两边同时取对数得，k-1<=log2(n)<k，⼜因层数为整数，故log2(n)=k-1，即k=log2(n)+1。
性质5：对具有n个结点的完全⼆叉树，如果按照从上⾄下和从左⾄右的顺序对⼆叉树的所有结点从1开始编号，则对于任意的序号为i的结点有：
如果i>1，那么序号为i的结点的双亲结点序号为i/2；
如果i=1，那么序号为i的结点为根节点，⽆双亲结点；
如果2i<=n，那么序号为i的结点的左孩⼦结点序号为2i；
如果2i>n，那么序号为i的结点⽆左孩⼦；
如果2i+1<=n，那么序号为i的结点右孩⼦序号为2i+1；
如果2i+1>n，那么序号为i的结点⽆右孩⼦。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。