Shulou(Shulou.com)06/03 Report--

This article shows you how to understand binary tree, the content is concise and easy to understand, absolutely can make your eyes shine, through the detailed introduction of this article I hope you can gain something.

binary tree

For example, now there is an array that stores many user names. What is the fastest way to find the specified user name from this array?

We think of binary search, which is fast, but there's one more thing we need to do to be fastest: array ordering.

If we can sort the usernames directly when inserting them, the final structure will be ordered.

So someone designed a data structure: a binary search tree, also known as a binary tree.

As shown below: This is a binary tree structure.

binary tree

Based on the example above, assume that Herry is at the top and Alice, Mike, Ivy, Tom are below. From left to right, from top to bottom, the final order is Alice->Herry->Ivy->Mike->Tom, which is indeed alphabetical.

Name Sort Description

There are four terms that need clarification: node, left node, right node, and root node.

Each red sphere counts as a node. The nodes connected to the left and bottom of the node are called left nodes, while the nodes connected to the right are called right nodes. For example Alice is called the left node of the Herry node and Mike is called the right node of the Herry node. There will only be one root node, belonging to the top node. Herry in the above diagram is the root node.

For each of these nodes, the value of the left child node is smaller than it, and the value of the right child node is larger than it. Alice, for example.

< Herry < Mike。 假设现在我们想要查找 Ivy，首先检查根节点，发现比 Herry 大，所以往下继续找，找到了根节点的右节点 Mike，再继续找，比 Mike 小，所以找 Mike 的左节点，正好找到 Ivy。 二叉查找树中查找节点时，平均运行时间是 O(logn)，最糟糕的情况下所需时间为 O(n); 而在有序数组中查找时，及时最糟糕的情况，二分查找最多也是 O(logn)，所以你可能会觉得，二分查找比二叉查找要快很多。但是二叉查找树的插入和删除操作的速度是要快很多的。这里我们做一个对比：

Comparison of Binary Tree and Binary Search Algorithm

But binary trees also have disadvantages:

No random access. For example, if you want to find the tenth element, you can't return the tenth element, but the array can be found by index.

Binary tree exists unbalanced situation, such as the root node as the middle boundary, found that the number of nodes on the right far exceeds the number of nodes on the left, then left and right imbalance, the efficiency of the search is very low. As shown below:

The number of nodes on the right is much greater than the number of nodes on the left.

Is there a balanced binary tree? Of course, there are, that is, red and black trees, limited by space and emphasis, this will be discussed in the next chapter

Meaning of binary tree

binary tree definition

A binary tree is a tree in which each node can have only two subtrees, and there are left and right points.

A binary tree is a finite set of n(n>=0 ) nodes, either empty (called an empty binary tree) or consisting of a root node and two disjoint left and right subtrees called root nodes.

Binary tree has 5 forms

Empty binary tree.

A binary tree with only one root node.

Only left subtree

Only the right tree.

Complete binary tree.

node degree

Definition: The number of subtrees a node has is called the degree of the node.

Let's look at the picture below and see what's clear.

mark

For example, node B has degree 2 and node E has degree 1.

The degree of the tree is the maximum of the degrees of all nodes, which is 2.

node hierarchy

As shown in the following figure: the root node is the first layer, and so on.

Binary tree characteristics

Each node has at most one subtree, so there is no node with degree greater than 2 in the binary tree.

The left and right subtrees are ordered, and the order cannot be reversed arbitrarily.

Even if a node has only one subtree, it is necessary to distinguish whether it is a left subtree or a right subtree.

traversal of binary tree

Binary tree traversal: Starting from the root node of the binary tree, all nodes in the binary tree are visited in turn according to a certain order, so that each node can be visited once and only once.

Binary tree access order can be divided into four types:

Preorder traversal.

Intermediate order traversal.

Subsequent traversal.

Sequence traversal.

Preorder traversal: popular is to start from the root node of the binary tree, when the first time to reach the node on the output node data, according to the first left and then right direction access.

In order to traverse: that is, starting from the root node of the binary tree, when the second time to reach the node on the output node data, according to the first left and then right direction access.

Post-order traversal: that is, starting from the root node of the binary tree, when the third time to reach the node on the output node data, according to the first left and then right direction access.

Hierarchical traversal: that is, according to the tree hierarchy from top to bottom traversal binary tree.

mark

The result of traversing according to the preamble is BADCE.

The result of this traversal is ABCDE.

The result of subsequent iterations is ACEDB.

The result of the hierarchical traversal is BADCE.

The above content is how to understand binary tree. Have you learned knowledge or skills? If you want to learn more skills or enrich your knowledge reserves, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.