数据结构二叉树BinaryTree之性质+推导

数据结构,二叉树,性质,推导

Posted by Naah on Thursday, Aug 17,2017 10:42:52

由于无法打出上下标效果,所以本节采用截图形式

性质1:在二叉树的第i层上至多有2^(i-1)个结点(i>=1)

性质2:深度为k的二叉树至多有2^(k-1)个结点(k>=1)

性质3:对任何一颗二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0 = n_2+1.

性质4:具有n个结点的满二叉树深度为log_2^(n+1)

性质5:如果对一颗有n个结点的完全二叉树(其深度为[log_2^n]+1)的结点按层序编号(从第1层到第[log_2^n]+1层,每层从左到右),对任意一个结点i(1<=i<=n)有: