二叉树基础及常见类型

labuladong原创约 1976 字

I believe the binary tree is the most important basic data structure, bar none.

If you are a beginner, it is difficult to fully explain the reasons for this conclusion at this stage. You need to study the following content on this site carefully to gradually understand. Let me summarize two points for now:

The binary tree itself is a relatively simple basic data structure, but many complex data structures are based on binary trees, such as red-black trees (binary search trees), multi-way trees, binary heaps, graphs, trie, union-find, and so on. If you master binary trees, these data structures will not be a problem; if you don't understand binary trees, it will be hard to manage these advanced data structures.
The binary tree is not just a data structure; it also represents a way of thinking about recursion. All recursive algorithms, like backtracking, BFS, dynamic programming, essentially abstract specific problems into tree structures. Once you abstract them, these problems eventually return to binary tree problems. While others see a string of text in a piece of algorithm code, you see a tree, and you can modify it however you want, and it will always be correct. It is just that simple.

The data structure chapters that follow include extensive explanations and exercises on binary trees. If you study in the order prescribed by this site, I will help you fully understand binary trees, and then you will understand why I emphasize binary trees so much.

Several Common Types of Binary Trees

The main difficulty with binary trees is in solving algorithm problems. The structure itself is not that hard; it is just a tree structure like this:

The above is an ordinary binary tree. Here are some terms you need to understand:

The nodes directly connected below a node are called child nodes, and the nodes directly connected above are called parent nodes. For example, the parent node of node 3 is 1, its left child node is 5, and its right child node is 6. The parent node of node 5 is 3, its left child node is 7, and it has no right child node.
The node at the top with no parent node, 1, is called the root node. The nodes at the bottom with no child nodes, 4, 7, and 8, are called leaf nodes.
The number of nodes from the root node to the bottommost leaf node is called the maximum depth/height of the binary tree. The maximum depth of the tree above is 4, which is the number of nodes from root node 1 to leaf node 7 or 8.

There is not much else to say; it is that simple.

There are some slightly special binary trees with their own names, which you should know. When you encounter these terms in problems later, you will understand what the problem is talking about.

Full Binary Tree

It's easier to understand by looking at a picture. A full binary tree is one where every level of the tree is completely filled, making the whole tree look like an equilateral triangle:

The advantage of a full binary tree is that it's easy to calculate the total number of nodes. If the depth is h, the total number of nodes is 2^h - 1, which we can derive from the sum of a geometric series—a concept we all learned in school.

Complete Binary Tree

A complete binary tree is one where all levels are fully filled except possibly the last one, and all nodes are as far left as possible:

You'll notice that a full binary tree is actually a special case of a complete binary tree.

A key characteristic of a complete binary tree is that because its nodes are compactly arranged, the index of parent and child nodes follows a clear pattern if you number the nodes from left to right, top to bottom.

This characteristic will be discussed in more detail when we talk about the Principle and Implementation of Binary Heaps, and it’s also useful in solving algorithm problems.

Note on Definitions

There is a slight difference between Chinese and English definitions for complete and full binary trees.

In Chinese, what we call a complete binary tree corresponds to the English term "Complete Binary Tree", which is the same concept.

However, what we call a full binary tree should technically be translated as "Full Binary Tree", but in fact, it corresponds to the English "Perfect Binary Tree".

In English, a "Full Binary Tree" refers to a binary tree where every node has either zero or two children.

These definitions are sourced from Wikipedia. This is just a side note. The terminology doesn't really matter as long as you are aware of these differences when reading English resources.

Binary Search Tree

A Binary Search Tree (BST) is a common type of binary tree, defined as follows:

For each node in the tree, the value of every node in its left subtree is less than the value of the node, and the value of every node in its right subtree is greater than the value of the node. Simply put, "left small, right large."

I've emphasized "every node in the subtree" because beginners often make the mistake of only looking at the child nodes. You need to consider all nodes in the entire subtree.

For example, the following tree is a BST:

The value of all nodes in the left subtree of node 7 is less than 7, and the value of all nodes in the right subtree is greater than 7. Similarly, the value of all nodes in the left subtree of node 4 is less than 4, and the value of all nodes in the right subtree is greater than 4, and so on.

Conversely, the following tree is not a BST:

If you only look at each node's left and right children, you might not see the problem. You should look at the entire subtree. Notice that node 7's left subtree contains a node 8, which is greater than 7, thus violating the BST definition.

BSTs are very commonly used data structures. Because of the "left small, right large" property, we can quickly find a particular node or all nodes within a specific range in a BST. This is the advantage of a BST.

For instance, in a regular binary tree where node values have no specific order, finding a node with value x requires traversing the entire tree starting from the root node.

In a BST, you can compare the root node's value with x. If x is greater than the root node's value, you can immediately exclude the entire left subtree and start searching from the right subtree, allowing you to quickly locate the node with value x.

We will cover BSTs in detail in later chapters, with plenty of exercises. For now, these basic concepts should suffice.

Implementing Binary Trees

The most common binary tree structure is similar to a linked list, where each binary tree node has pointers to its left and right children. This method is simple and intuitive.

On platforms like LeetCode, the binary trees you are given are usually constructed in this way. A typical TreeNode class for a binary tree node looks like this:

java 🟢

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { this.val = x; }
}

// You can construct a binary tree like this:
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(6);

// The constructed binary tree looks like this:
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

cpp 🤖

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// You can construct a binary tree like this:
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->right->left = new TreeNode(5);
root->right->right = new TreeNode(6);

// The constructed binary tree is like this:
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

python 🤖

class TreeNode:
    def __init__(self, x: int):
        self.val = x
        self.left = None
        self.right = None

# You can build a binary tree like this:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)

# The constructed binary tree looks like this:
#     1
#    / \
#   2   3
#  /   / \
# 4   5   6

go 🤖

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// You can construct a binary tree like this:
root := &TreeNode{Val: 1}
root.Left := &TreeNode{Val: 2}
root.Right := &TreeNode{Val: 3}
root.Left.Left := &TreeNode{Val: 4}
root.Right.Left := &TreeNode{Val: 5}
root.Right.Right := &TreeNode{Val: 6}

// The constructed binary tree looks like this:
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

javascript 🤖

var TreeNode = function(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}

// you can construct a binary tree like this:
var root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(6);

// the constructed binary tree looks like this:
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

Since the above is a common implementation method, it implies that there are other implementation methods, right?

Yes, in Principles and Implementation of Binary Heap and Detailed Explanation of Union-Find Algorithm, we choose to use arrays to store binary trees based on specific scenarios.

When visualizing recursive functions in the Visualization Panel, a recursive tree is generated from the function stack, which can be considered a form of binary tree implementation.

Additionally, in general algorithm problems, we might abstract the actual problem into a binary tree structure, but we don't need to create a binary tree with TreeNode. Instead, we use structures like Hash Tables to represent binary/multi-way trees directly.

For example, the binary tree above:

We can use a hash table where the keys are parent node IDs, and the values are lists of child node IDs (each node has a unique ID). Thus, a key-value pair represents a multi-way tree node, and the multi-way tree can be represented like this:

java 🟢

// 1 -> [2, 3]
// 2 -> [4]
// 3 -> [5, 6]

HashMap<Integer, List<Integer>> tree = new HashMap<>();
tree.put(1, Arrays.asList(2, 3));
tree.put(2, Collections.singletonList(4));
tree.put(3, Arrays.asList(5, 6));

cpp 🤖

// 1 -> {2, 3}
// 2 -> {4}
// 3 -> {5, 6}

unordered_map<int, vector<int>> tree;
tree[1] = {2, 3};
tree[2] = {4};
tree[3] = {5, 6};

python 🤖

# 1 -> [2, 3]
# 2 -> [4]
# 3 -> [5, 6]

tree = {
    1: [2, 3],
    2: [4],
    3: [5, 6]
}

go 🤖

// 1 -> [2, 3]
// 2 -> [4]
// 3 -> [5, 6]

tree := map[int][]int{
    1: {2, 3},
    2: {4},
    3: {5, 6},
}

javascript 🤖

// 1 -> [2, 3]
// 2 -> [4]
// 3 -> [5, 6]

let tree = new Map([
    [1, [2, 3]],
    [2, [4]],
    [3, [5, 6]]
]);

This way, you can simulate and manipulate binary tree/multi-way tree structures. When we discuss graph theory later, you will learn that it has a new name called Adjacency List.