二叉树 vs. 二叉搜索树 | Baeldung中文网

1. Overview

In this tutorial, we’ll discuss two popular tree data structures: binary tree and binary search tree. We’ll present formal definitions with properties and examples of both tree structures.

Finally, we’ll explain the core conceptual differences between them.

2. Introduction to Binary Trees

A binary tree is a popular and widely used tree data structure. As the name suggests, each node in a binary tree can have at most two children nodes: left and right children. It contains three types of nodes: root, intermediate parent, and leaf node.

A root node is a topmost node in a binary tree. A leaf node can be defined as a node without any children nodes. Finally, excluding the root and leaf nodes, all other nodes are the intermediate parent nodes. Let’s look at an example:

dacsasd.drawio 2

First of all, let’s check if the tree T_1 is a binary tree or not. The primary and most important property is that each node can have at most two children nodes. Therefore, we can see that our sample tree T_1 obeys this property. Hence, it’s a binary tree.

Here, the node $\mathsf{1}$ is the root node of the binary tree T_1 . Moreover, the nodes 4, 5, and are the leaf nodes. Finally, the nodes and are the intermediate parent nodes.

Each node in a binary tree contains three fields: pointer to the left children, data, pointer to the right children. Let’s look at the logical representation of the binary tree T_1 :

sdacsasd.drawio 1

There’re various types of binary trees. Some of them are the full, perfect, complete, skewed, balanced binary trees. Moreover, the binary tree data structure supports four main operations: searching, insertion, deletion, and traversal.

3. Properties

Let’s discuss some important properties of the binary tree data structure.

There can be a maximum of $\mathbf{(2^{h} -1)}$ nodes in a binary tree with height $\mathbf{h}$ . Let’s take a look at the binary tree T_1 . The leaf nodes are at the height of . Hence, the height of T_1 is $\mathsf{3}$ .

Additionally, the height of the root is $\mathsf{1}$ . Hence, the maximum number of nodes with height $\mathsf{1}$ can be $(2^{1} -1) = 1$ . Similarly, the maximum number of nodes T_1 can contain would be $(2^{3} -1) = 7$ .

Now given the total number of nodes in a binary tree, the minimum height or level of the binary tree would be $\mathbf{\lceil Log_{2}(N + 1)\rceil}$ . In T_1 , there’re nodes. Hence, the minimum height or level would be $\lceil Log_{2}(6 + 1)\rceil = 3$ .

We can have a maximum of $\mathbf{2^{L}}$ nodes at the $\mathbf{L}$ level of a binary tree. It can be verified easily. The level of the root node of a binary tree is always . Hence, there can be a maximum of 2^0 =1 node, which is valid for all binary trees.

Additionally, a detailed explanation with algorithms on how to calculate the exact number of nodes and level of a binary tree can be found in the tutorial: Number of Nodes in a Binary Tree With Level N.

Let’s assume a binary tree has leaves. According to the binary tree structure, it should have at least $\mathbf{(|Log_{2}L| + 1)}$ levels. In the case of T_1 , we have leaves. Hence, according to this property, T_1 should have at least $(|Log_{2}3| + 1) = 2$ levels which is true.

Now, based on the definition of a binary tree, each node can contain up to two children nodes. Therefore, consider a scenario where all the nodes in a binary tree either contain or children. In such a case, the number of nodes with $\mathbf{2}$ children is always one less than the number of nodes with no children.

In T_1 , there’re nodes (nodes with key 4, 5, and ) with no children and nodes (nodes with key and ) with children. Hence, this example verifies the property.

4. Introduction to Binary Search Tree

A binary search tree is a sorted tree data structure. Moreover, it follows the properties of the binary tree with some additional properties. Hence, each node can have at most two children nodes. But here, the key of the left subtree is less than the key value of its parent node. Similarly, the key of the right subtree is greater than the key value of its parent node.

Let’s look at an example:

sdADA.drawio

Let’s first determine whether it’s a binary search tree or not. The left children of the root node contain a key that has less value than the key of the root node. Similarly, the right children of the root node contain the key with a greater value than the root node. Finally, the rest of the tree follows both binary tree and binary search tree properties. Hence, we can say that it’s a binary search tree.

Let’s look at another example:

sdADA.drawio 1

Here, the tree is a binary tree as the root and intermediate parent nodes contain children nodes each. Although, it’s not a binary search tree. If we look at the leaf nodes of the left subtree, we can observe that it violates the property of the binary search tree. Hence, it’s a binary tree but not a binary search tree.

A more detailed discussion on binary search tree data structure and possible tree operations can be found in the tutorial: A Quick Guide to Binary Search Trees.

5. Differences

There’re similarities between a binary search tree and a binary tree. Both are tree data structures, and each node in both structures can contain at most two children nodes. Regardless of the similarities, they have some core structural and functional differences. Let’s discuss the key differences between them:

Binary Tree

Binary Search Tree

A non-linear tree data structure with the possibility of having at most two children for each node.

A variant of binary tree with extra node based properties.

May or may not be a binary search tree.

Always a binary tree.

Not required to organize the nodes.

Required to organize the nodes based on the key value.

Unordered tree data structure.

Ordered tree data structure .

Slow in carry out the tree operations.

Efficient and fast in carry out the tree operations.

6. Conclusion

In this tutorial, we discussed two tree data structures: binary tree and binary search tree. We explained both data structures with examples and presented key differences between them.

Persistence

REST

Security