MENU

简单理解一下完全二叉树?

• November 12, 2020 •

完全二叉树是具有某种特征的树结构,下面几棵二叉树带你了解什么是完全二叉树


仔细观察下列树结构,带星标的即是完全二叉树

判断一颗完全二叉树,首先想到相同深度的满二叉树,按照层序遍历给各结点编号,结点的编号和位置都能和满二叉树对应起来,就是完全二叉树

简单地说,二叉树中间没有缺少结点,就是完全二叉树

[期末] 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树



在上图中,图一是一个满二叉树,当然是完全二叉树

图二的6结点前缺少一个结点

图三不是满二叉树,但所有编号和位置能和图一对应起来,中间不缺少结点,是完全二叉树

图四 4结点后面缺少一个结点

图五 中间不缺少结点,因此是完全二叉树

图六 2结点前缺少一个结点


完全二叉树的重要特征:

  1. 有n个结点的完全二叉树,层数(深度)为log2(n+1)
  2. 如何找双亲结点,左孩子结点,右孩子结点?
    (1)当前结点编号为m,双亲节点为m/2;

(2)当前结点编号为m,如果有左孩子结点,编号就为2m;
(3)当前结点编号为m,如果有右孩子结点,编号就位2m+1;

Archives QR Code Tip
QR Code for this page
Tipping QR Code