Abstract: In daily life, many things can be described by trees, such as the contents of books, the organizational structure of work units and so on. Tree is a very important data structure in computer. Tree storage can improve the efficiency of data storage and reading.
This article is shared by Huawei Cloud community “[Yunzhushu Co-create] Want to understand binary tree, read this article is enough”, author: Liuzhen007.
preface
Trees can be used to describe many things in daily life, such as the contents of books, the organizational structure of work units and so on. Tree is a very important data structure in computer. Tree storage can improve the efficiency of data storage and reading.
First, the basic definition of tree
In daily life, many things can be described using a tree, the tree is a data structure is very important in computer, tree storage can improve the efficiency of data storage, reading, such as using the binary sort tree, can not only guarantee the speed of data retrieval, at the same time, also can ensure that data insert, delete, modify the speed.
In fact, there are many kinds of trees, such as ordinary binary tree, complete binary tree, full binary tree, clue binary tree, Huffman tree, binary sorting tree, balanced binary tree, AVL balanced binary tree, red black tree, B tree, B+ tree, heap and so on. The main content of today’s introduction is the basic knowledge of binary trees and several basic types of binary trees.
Terms related to binary trees
Before the formal lecture, we first introduce some professional terms and terms about binary tree, including node, degree of node, leaf node, branch node, level of node, degree of tree, depth of tree, etc. Understanding these basic professional terms and terms is very important for us to understand the characteristics of binary tree.
1) Node: contains a data element and some information pointing to subtree branches.
2) Degree of node: the data of a node with subtree becomes the degree of node.
3) Leaf node: also known as terminal node, node without subtree or node with zero degree.
4) Branch node: also called non-terminal node, the node whose degree is not zero becomes non-terminal node.
5) Node hierarchy: Starting from the root node, the level of the root node is 1, the level of the direct successor of the root is 2, and so on.
6) Degree of tree: the maximum degree of all nodes in the tree.
7) Tree depth: the maximum level of nodes in the tree.
1. Characteristics of trees
As a special data structure, tree has many characteristics, such as:
1) Each node has multiple or zero children
2) Nodes with no parents become root nodes, and nodes with no children become leaves
3) Each non-root node has only one parent
4) Each node and its descendants can be regarded as a tree on the whole, which is called a subtree with the current node as the root
2. Basic definition of binary tree
1) A binary tree is a tree with a degree of 2 or less, and each node has at most two children
2) The nodes of binary tree are divided into left node and right node
3. Full binary tree
1) If the node degree of each layer of the binary tree reaches the maximum value, the binary tree is a full binary tree
2) A full binary tree of depth N, with 2^n-1 nodes
4. Complete binary tree
Leaf nodes can only appear at the lowest and lower levels, with the last leaf node continuous on the left and the second-to-last leaf node continuous on the right. This is called a complete binary tree.
Create a binary tree
Next, we describe binary trees by code, using Java as an example, where the node class is defined as follows:
The binary lookup tree class is defined as follows:
After the relevant classes are defined, we will look at the specific method implementation, which will be introduced separately below.
1. Size () method
The size () method is relatively simple, each time add one element, delete the element minus one, maintain a common variable num, the code implementation is as follows:
2. Put (Key Key, Value Value) method
The put (Key Key, Value Value) method can use the overloaded put (Node x, Key Key, Value Value) method, so the implementation is relatively simple, where the first parameter only needs to pass the root Node, the code implementation is as follows:
3. Put (Node x, Key Key, Value Value)
The PUT (Node x, Key Key, Value Value) method should be relatively complex to implement in the entire class.
In the first case, there is no node in the tree, and the newly inserted node is used as the root.
In the second case, the current tree is not empty, so we start at the root. This can be broken down into three cases:
1) If the key of the new node is smaller than the key of the current node, continue to find the left child of the current node.
2) If the key of the new node is greater than the key of the current node, continue to find the right child of the current node.
3) If the key of the new node is equal to the key of the current node, then such a node already exists in the tree, and the value of this node can be replaced.
The specific code is as follows:
4. Get (Key Key) method
The get (Key Key) method is similar to the put (Key Key, Value Value) method. You can also use the overloaded get (Node x, Key Key) method to implement the code as follows:
5. Get (Node x, Key Key)
Get (Node x, Key Key) starts from the root Node. If the Key to be queried is smaller than the Key of the current Node, continue to find the left child of the current Node. If the key is greater than the key of the current node, continue to find the right child of the current node. If the key is equal to the key of the current node, return the value of the current node.
The specific code is as follows:
From the above code, we can see that the get () method is similar to the PUT () method in that it is implemented through recursive calls.
6. Delete (Key Key) method
Delete (Key Key); delete (Key Key);
7. Delete (Node x, Key Key)
Take the most complex case as an example, first find the deleted node, find the smallest node minNode in the right subtree of the deleted node, delete the smallest node in the right subtree, and make the left subtree of the deleted node become the left subtree of the smallest node minNode. Let the right subtree of the deleted node be the right subtree of minNode, and let the parent of the deleted node point to minNode.
The specific code is as follows:
Now that the code is done, let’s verify with the code to see if we got it right:
Answer output:
3
Li si
2
Nice, great, the program has been proven to be correct by the output above.
Find the smallest and largest keys in the binary tree
For example, binary trees are used to record salary and name data of employees in a company, or ranking and name data of students in a class. How to find the data of the highest and lowest students quickly?
In that case, what to do? In fact, the following four methods can also be sorted out and defined as follows:
1. Min () method
The min () method is similar to the get () and put () methods mentioned above, and can also be implemented using the following overloaded methods:
Public key min() {return min(root).key; }Copy the code2. Min (Node x) method
The min (Node x) method needs to find the smallest Node in the left subtree according to the location of the Node passed in. If it is empty, it directly returns empty. The specific code is as follows:
Public Node min(Node x) {if (x == null) {return x; } Node minNode = x; while (minNode.left ! = null) { minNode = minNode.left; } return minNode; }Copy the code3. Max () method
The Max () method is similar to the min () method mentioned above, and can also be implemented using the following overloaded methods:
Public key Max () {return Max (root).key; }Copy the code4. Max (Node x) method
Max (Node x) = Max (Node x) = Max (Node x) = Max (Node x) = Max (Node x)
Public Node min(Node x) {if (x == null) {return x; } Node maxNode = x; while (maxNode.right ! = null) { maxNode = maxNode.right; } return maxNode; }Copy the codeFive, binary tree traversal
There are three ways of traversal of binary tree, namely, pre-order traversal, middle-order traversal and post-order traversal.
1. Preorder traversal
First access the root node, then access the left subtree, and finally access the right subtree, such as the binary tree in the following figure. The result of the preceding traversal is as follows:
EBADCGFH.
2. Middle order traversal
First access the left subtree, then access the root, and finally access the right subtree, such as the binary tree in the following figure, middle order traversal results are as follows:
ABCDEFGH.
3. Back-order traversal
First access the left subtree, then access the right subtree, and finally access the root node, such as the binary tree in the following figure. The result of the sequential traversal is as follows:
ACDBFHGE.
conclusion
Binary tree not only has very important research significance in basic data structure, but also has very important application scenarios in practical application. It takes into account the advantages of conventional data structure array and linked list, while avoiding the inherent disadvantages of both. The data structure abstracted from many practical problems is often in the form of binary tree, so as to make use of the storage structure and algorithm characteristics of binary tree, so learning binary tree is very necessary. I hope that the introduction of this article will help you to understand and master binary trees.
Click to follow, the first time to learn about Huawei cloud fresh technology ~