满二叉树、完全二叉树和完美二叉树的区别

1. Introduction

Binary trees are an important part of Computer Science algorithms.

In this tutorial, we’ll look at specific types of binary trees: a full binary tree, a complete binary tree, and a perfect binary tree. We’ll look at the properties of each of these binary trees with illustrations.

2. Trees and Binary Trees

2.1. Definition

A tree is a hierarchical data structure that has a set of connected nodes in a hierarchy like a tree. There is one node, commonly called the root node, which can be connected to a set of child nodes in the form of branches.

When we restrict the tree’s definition to specify that any node can have at most two child nodes attached, this becomes a Binary tree. A binary tree can have a left child node and a right child node.

2.2. Types of Binary Trees

Binary trees can take many types and forms. A Binary Tree can be categorized based on the properties of the child nodes, the number of child nodes, the height of the subtrees, etc.

Here are a few common binary tree types:

Full Binary Tree: Every node has either 0 or 2 child nodes, i.e., left and right or no children
Complete Binary Tree: All levels, except possibly the last, are filled, and all nodes are as left as possible
Perfect Binary Tree: All nodes have exactly two children, and all leaf nodes are at the same level
Balanced Binary Tree: The heights of any node’s left and right subtrees differ by at most one
Binary Search Tree (BST): A binary tree in which the left child node is smaller, and the right child node is greater than the parent node
Threaded Binary Tree: Each node of the binary tree contains extra information, called threads, that allows for efficient tree traversal without recursion or a stack
Heap: A complete binary tree that satisfies the heap property

In this tutorial, we’ll focus on the first three.

3. Creating a Binary Tree

In this section, we’ll implement a binary tree using recursion. We construct a binary tree of height , which is taken as input:

algorithm CreateBinaryTree(height):
    // INPUT
    //    height = the height of the tree
    // OUTPUT
    //    Returns a binary tree of the specified height
    
    if height = 0:
        return null
    
    node <- make a new tree node
    node.data <- getSomeData()
    node.left <- CreateBinaryTree(height - 1)
    node.right <- CreateBinaryTree(height - 1)    
    return node

4. Full Binary Tree

A full binary tree is one where every node has either 0 or 2 children:

Properties of a full binary tree:

The height of a full binary tree with levels is equal to
The total number of nodes in a full binary tree is , where is the height of the tree
Every node of a full binary tree can have a degree of 0 or 2
The total number of nodes in a full binary tree can be expressed in two ways:
- , where is the number of internal or non-leaf nodes
- , where is the number of leaves
A full binary tree is always balanced

5. Complete Binary Tree

In a complete binary tree, all levels are filled except the lowest level nodes, which are filled from the left:

Rendered by QuickLaTeX.com

Properties of a complete binary tree:

The number of nodes at a depth is
The height of a complete binary tree with nodes is
All leaf nodes in a complete binary tree are present in the last level or the penultimate level

6. Perfect Binary Tree

A perfect binary tree, as the name suggests, is the most perfect kind of binary tree with all its nodes with exactly two children, and all leaf nodes at the same level:

Rendered by QuickLaTeX.com

Properties of a perfect binary tree:

The number of leaf nodes in a perfect binary tree with internal nodes is equal to the number of
The number of nodes in a Perfect Binary Tree of height is
All internal nodes of a perfect binary tree have a degree of 2
All leaf nodes of a perfect binary tree have a degree of 0
The height of a perfect binary tree with number of nodes is
Perfect binary trees are always symmetrical and balanced