二叉树数据结构简介 | Baeldung中文网

1. Introduction

In this article, we’re going to learn the binary tree data structure and its properties. Next, we’ll learn six types of binary trees with an illustration.

Finally, we’ll explore different applications of a binary tree.

2. Definition

A binary tree is a hierarchal data structure in which each node has at most two children. The child nodes are called the left child and the right child.

To start with, let’s describe the linked list representation of a binary tree in which each node has three fields:

Pointer to store the address of the left child
Data element
Pointer to store the address of the right child

Let’s see an example of a binary tree:

example_bt-1

3. Properties

Let’s now focus on some basic properties of a binary tree:

A binary tree can have a maximum of $2^{l}$ nodes at level if the level of the root is zero.
When each node of a binary tree has one or two children, the number of leaf nodes (nodes with no children) is one more than the number of nodes that have two children.
There exists a maximum of $(2^{h}-1)$ nodes in a binary tree if its height is , and the height of a leaf node is one.
If there are leaf nodes in a binary tree, then it has at least $\lceil \log_2 L \rceil$ and at most levels.
A binary tree of nodes has $\log_{2}(n+1)$ minimum number of levels or minimum height.
The minimum and the maximum height of a binary tree having nodes are $\lceil \log_{2}n \rceil$ and , respectively.
A binary tree of nodes has null references.

4. Types of Binary Trees

In this section, we’re going to discuss six types of binary trees and describe each with an illustration.

4.1. Full Binary Tree

A binary tree is said to be a full binary tree when each internal node has zero or two children:

full binary tree

4.2. Perfect Binary Tree

A perfect binary tree is a special type of binary tree in which all the leaf nodes are at the same level, and each internal node has two children:

perfect binary tree

4.3. Complete Binary Tree

A binary tree is referred to as a complete binary tree when all of its levels are completely filled. The only exception is possibly the lowest level in which the nodes must lean as left as possible:

complete binary tree

4.4. Degenerate or Pathological Tree

A degenerate or pathological tree is a type of binary tree in which each internal node has a single child, either the left child or the right child:

degenerate tree

4.5. Skewed Binary Tree

A binary tree is said to be a skewed binary tree if all of its internal nodes have exactly one child, and either left children or right children dominate the tree. In particular, there exist two types of skewed binary trees: left-skewed binary tree and the right-skewed binary tree:

skewed binary tree

4.6. Balanced Binary Tree

A balanced binary tree is also a special type of binary tree in which the difference of height between the left and the right subtrees for each node is at most one:

balanced binary tree

5. Applications

There are many other data structures that are derived from the idea of a binary tree, such as binary search tree, syntax tree, heap, hash tree, red-black tree, binary trie, AVL tree, GGM tree, T-tree, and Treap.

Other real-life applications of a binary tree include binary space partition, heap sort, Huffman coding, virtual memory management, and indexing.

6. Conclusion

In this article, we’ve learned the binary tree data structure along with its basic properties.

Then, we’ve discussed six types of binary trees with illustrative examples. At last, we’ve listed various applications of a binary tree.

Persistence

REST

Security