二叉树和完全二叉树一些规律

2023-07-23 11:16| 来源: 网络整理| 查看: 265

1、二叉树具有以下规律：

1）二叉树高度为i所在的层至多有 $2^{i}$ 个节点

2）高度为k的二叉树至多有 $2^{k+1}$ -1个节点

3）对于任何一棵二叉树，若度为2的节点数有n2个，则叶子数有n0个，则叶子数n0必定为n2+1即n0=n2+1;

注意：高度是从0开始计算的，也就是说二叉树最后一层的高度为0.

证3）：

二叉树全部节点数为叶子数、度为1的节点数和度为2的节点数之和，即 n = n0 + n1 + n2。

而二叉树的全部节点数可以表示为总分支数加1，即 n = B + 1;

而总分支数 B = n1 + 2n2

综上可得： n1 +2n2 + 1 = no + n1 + n2 ===》 n0 = n2 + 1

2、完全二叉树具有以下规律：

1）节点数为N的完全二叉树，其高度为 $\left \lfloor logN \right \rfloor$ (向下取整),也就是说该树一共有 $\left \lfloor logN \right \rfloor$ + 1 层。如节点数为3的完全二叉树，其高度为1（即两层，第一层高度为0）；.

2）对于完全二叉树，若从上至下、从左至右编号，则编号为i的节点，其左孩子节点编号为2i，右孩子节点编号为2i+1，父亲节点为i/2；

证1）：假设完全二叉树有k层，完全二叉树的总节点数N在k-1层的满二叉树和k层的满二叉树之间，即：

$2^{k-1}$ - 1 < N $\leq$ $2^{k}$ - 1

两边同时加1得：

$2^{k-1}$ < N + 1 $\leq$ $2^{k}$ ====》 $2^{k-1}$ $\leq$ N

【本文地址】

公司简介

联系我们