完全二叉树和几乎完全二叉树的区别 [英] difference between complete and almost complete binary tree

问题描述

完整树是每一层都完全填充的树，几乎完整的树是一棵树，如果最后一层没有完全填充，则所有节点尽可能地离开.我的困惑在于以下二叉树示例:

A complete tree is a tree in which every level is completely filled and an Almost complete tree is a tree in which if last level is not completely filled then all nodes are as far as left as possible. my confusion is in following example of binary tree:

            O
          /   
         O      O
       /      / 
      O    O  O   O
     / 
    O   O

根据定义它应该是一棵不完全二叉树，但它是一棵完整的二叉树.如果有人能详细说明这个完整的二叉树是怎样的，为什么不是一个不完整的二叉树?

According to definition it should be an incomplete binary tree but it is a complete binary tree. if someone could elaborate how is this complete binary tree and why not an incomplete binary tree?

推荐答案

你的例子是一棵完全二叉树:一棵完全二叉树可以有一个不完整的最后一层，只要它的所有叶子都向左推.

Your example is a complete binary tree: a complete binary tree can have an incomplete last level, as long as all the leaves in it are pushed across to the left.

完美二叉树是最后一层为满的完全二叉树.

A perfect binary tree is a complete binary tree in which the last level is full.

几乎完整的二叉树是完整但不完美的二叉树.所以你的例子也差不多完成了.

An almost complete binary tree is a complete but not perfect binary tree. So your example is also almost complete.

术语令人困惑，但几乎完整的二叉树也是完整的.

The terminology is confusing, but an almost complete binary tree is also complete.

这篇关于完全二叉树和几乎完全二叉树的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！