首页 > 编程知识 正文

二叉树的性质4证明,完全二叉树性质证明

时间:2023-05-04 12:03:28 阅读:161017 作者:2492

性质1 )非空二叉树的第I层最多有2^(I-1 )个节点,(i=1)。

性质2 )在深度为k的二叉树中,最多拥有2^k-1个节点,至少拥有k个节点。

性质3 :在非空二叉树中,度为0的节点,也就是叶的节点,比度为1的节点多一个,也就是说叶的节点数为n0,度为2的节点数为n2的话,n0=n2 1。

证明:假设n0为度0=叶的节点,度1的节点数为n-1,度2的节点数为n2,完全二叉树整体的节点总数为n=n0 n1 n2,根据二叉树和树的性质,n=n1 2xn2 1 (所有节点的度数之和加1等于节点总数

性质4 )具有n个节点的完全二叉树的深度为(log2(n ) ) 1。

证明:根据性质2,深度为k的二叉树最多具有2k-1个节点。 而且完全二叉树的定义与相同深度的二叉树的前边的编号相同。 也就是说,这些节点总数n位于k层和k-1层二叉树的容量之间。 即2(k-1(-1n=2k-1之间或2 ) k-1 )=n 2^k

性质5 :对于具有n个节点的完全二叉树,如果按照从上到下和从左到右的顺序对二叉树的所有节点从1开始编号,则对于任意编号I的节点:

如果是i1,则号码I的节点的父母的节点号码为i/2;

i=1时,序号I的节点是根节点,没有父母;

2i=n时,编号I节点的左孩子的节点编号为2i;

2in的情况下,号码I的节点中没有左边的孩子;

在2i 1=n的情况下,号码I的节点右边的孩子的号码是2i 1;

2i 1n的情况下,号码I的节点上没有右边的孩子。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。