We’ve already talked about arrays, linked lists, hash tables, queues, and so on. In the last article, we briefly introduced the concept of trees. Starting today, we’ll learn about binary trees, one of the interviewers’ favorite questions.
Go back to the tree thing
Before introducing binary trees, we need to look at some key concepts about trees. After all, binary trees are trees.
The first thing we need to understand is that a tree is a nonlinear data structure, and then the data is stored in a one-to-many relationship, which is the most basic concept.
A few concept nouns want to distinguish
Then we need to clarify a key conceptual term for trees.
Node: What is a node? I’ve read a lot of articles, some of them are called nodes, some of them are called nodes, and I think Node is more appropriate, because we like to use Node to define a Node, and Node generally translates to Node.
What is a node:
Simply put, each element stored in a tree structure is called a node
The idea is that the elements stored in a tree are called nodes, and they can be called different things depending on where the nodes are.
For example, the root node, the root node is only one, the top node, and the parent node, child node and brother node, these are actually not difficult to understand, belong to the basic knowledge of the tree, do not understand can see this article, there is a detailed introduction: come on! A complete data structure tree!
In addition to nodes, there are the concepts of subtrees and empty trees, as well as the degree and hierarchy of nodes, and the height or depth of the tree, which can be found in the above article. Here is a brief description of the degree and hierarchy of nodes. Let’s look at a graph first:
Degree: The number of subtrees a node has is called the Degree of the node. For example, in the graph, there are three subtrees (BCD) under the root node A, so the degree of node A is 3.
Degree of tree: The degree of a tree is the maximum degree of each node in the tree. In the graph, the maximum degree of each node is 3, so the degree of the whole tree is 3.
And the height or depth of the tree:
The depth (height) of a tree is the largest level of nodes in the tree. Note that this is for a tree, not a node, because for a tree the height from bottom up and the depth from top down are the same, but for a node the height and depth are different
Tips: It is better to fully understand these basic concepts and know how they work, rather than memorize them mechanically. Otherwise, even if you remember them at the time, you will forget them in a few days
Binary Tree
Now, remember that Binary Tree is 😄, so let’s talk about all the things you need to remember about Binary trees.
Characteristics of binary trees
Any kind of data structure has its own characteristics, which is different from other data structures, and why it is so important, because of these characteristics can stipulate that it is called a binary tree, not a trinomial tree or a quadtree.
For a binary tree, as we know from the name, it has to do with two, two forks, and in a tree structure, the forks are actually nodes, so a binary is basically just two nodes
The degree of each node in a binary tree is at most 2
Remember what degrees are, that’s the number of subtrees that each node has, and basically, how many children are there under a node, and for a binary tree, there’s at most two, there’s at most two subtrees, and this is actually easy to understand, it’s one node, there’s at most two branches, so here you need to know what’s going on here
If you look at this graph, A has three crosses, E has two crosses.
Then we continue to talk about another characteristic of binary tree: the left and right nodes are ordered, what does this mean? For a binary tree, its left and right nodes are ordered, different order is not the same binary tree. If we go back to the figure above, if we have a binary tree with E as the root and K and L as the leaves, then now K is on the left and L is on the right, but if we switch places and K is on the right and L is on the left then we have a new binary tree.
This is also a feature of binary trees.
Then, based on the above characteristics, we can naturally know that even if a node has only one subtree, then we have to distinguish left and right, or two different binary trees.
Properties of binary trees
Let’s continue to analyze some properties of binary trees. In fact, I have read several articles about the properties of binary trees written by others, and I think it is troublesome, and some people think it is unnecessary. Remember that the main two are not called OK.
So, here are two properties of binary trees, and let’s look at them using a graph:
If you look at a binary tree, there are three layers here, you know how this is layered, and it has this property:
The ith level of a non-empty binary tree has at most two to the I minus one nodes, where I is greater than or equal to one
Well, look at the picture above, and see if that’s true for yourself, and then there’s this property:
A binary tree of height h has at most two to the h minus one node
Of course, there are more properties of binary trees than that, but I could do all of them here, just look at other people’s summaries, bring them in, and they don’t make any sense, but the properties here, just remember these two, and you’ll be able to deal with them as long as you’re familiar with what a binary tree looks like.
Think about it, if this gives you a yes or no question, for example: in a binary tree of height h there is at most 2 to the h minus one node, would you say 😂
This piece of the first so learn, after all, there are a few things to confuse you!
Several binary trees, easy to get confused
For a binary tree, there are a few special forms, like a true binary tree, a full binary tree, and a complete binary tree, which I don’t know if you’ve heard of. The appearance rate of full binary tree should make a little, these kinds of binary tree can really make people confused, especially easy to confuse (ha ha, suddenly think of this word)
W so, the next I am by no means a simple machine to introduce the definition of these binary tree, that do not have what meaning, who will be, the Internet search, see definition does not have to, not listen to my useless talk here, so I have to tell you I understand it, how do I understand that several kinds of binary tree, no don’t have what good method does not.
Binary tree
First of all, let’s look at what is a true binary tree. True usually corresponds to false, right? If I say a true binary tree, is it basically saying that there are really two forks? 😂 if there is no two fork is not false.
In fact, when we say a true binary tree, we mean that all the nodes have degrees 0 or 2, and you see, that’s a binary tree, right? (That’s right)
What is a binary tree?
We have mentioned the characteristics of binary trees, properties, I don’t think we have said what is a binary tree? What is a binary tree? A binary tree is definitely a tree, it’s just a special kind of tree, but for a binary tree, its nodes have at most two children, notice that there are at most two children, so it could be one, it could be none.
No, I need to emphasize this:
For a binary tree, a node has at most two children, notice that there are at most two children, so there may be one child, or there may be none.
And then you look at what is a true binary tree?
All of the nodes have degrees either zero or two
You see the difference
This is called a binary tree, but it’s not a real binary tree, because this guy doesn’t have a fork
Hey, Ching, how dare you rip someone off?
And so on… Am I right? Let’s see what a true binary tree is:
All of the nodes have degrees either zero or two
Then look at the picture again, there seems to be no problem, there seems to be a problem, what happened? Actually, that’s not true. Let’s look at the leaf node, because if you think about it, if it’s a leaf node, it must have no children, so it’s a binary tree, it’s a real binary tree, because it’s already a leaf node
But it would be wrong to do so
This can only be a binary tree (a node can have a child node), but it’s not a true binary tree, because a true binary tree requires that, except for leaves, either you have no forks, or you have only two forks.
Think carefully understood to have no, above deliberately say wrong, not intentionally mislead everyone, just for the sake of making everyone’s memory more profound, do not know everyone realized my good heart 😂
Full binary tree
Let’s see what is a full binary tree, let’s guess, the adjective here should be “full”, that means “full”, that means “full”, that’s about it, so if you put it in a binary tree, does that mean that all of the x’s are full, for a binary tree, it means that there are only two x’s?
Ok, so every node has two forks (note, we do not include leaf nodes in this case), but if so, it seems to be a true binary tree.
Wait a minute, all of this is our guess, then what is the actual matter?
Full binary tree: the degree of all nodes is either zero or two, which is actually the definition of a true binary tree, but a full binary tree requires that all the leaves are at the last level
You see, once we know what a true binary tree is and look at this definition, it’s not too hard to understand, but there’s one more condition than a true binary tree:
A full binary tree also requires that all leaf nodes are at the last level
What about this last layer? That’s the basics, right? You know how to layer? Let’s see
It’s important to note that this is not a binary tree, but just to show you how it’s layered, so this is not a full binary tree, right
Because it’s not on the same floor. So this
This seems to be in one layer, but also not, why, full binary tree people require nodes to have two forks ah, although you here are in one layer, but the right side of the goods only a difference, fill a fork on the right
This is a full binary tree, forgive my drawing is a little bit crooked 😂
Arrived here you again think I below say this sentence is correct?
Full binary trees belong to true binary trees
That must be true, because a full binomial tree is a tree that adds conditions to a true binomial tree, and when you add conditions, you’re narrowing down the range, so you’re definitely in the range where you didn’t add conditions before.
So one more thing, in a binary tree of the same height, a full binary tree must have the most leaves and summary trees, a full binary tree must be a true binary tree, but the other way around, a true binary tree does not have to be a full binary tree
To put it simply, a full binary tree is a tree where every branch is full, and all the leaves are at the same level, or it’s a true binary tree.
Perfect binary tree
All right, let’s move on to the last particular kind of binary tree, the perfect binary tree, which is actually the one of the three that’s a little tricky, because the concept is a little bit mythic 😂
If a binary tree with n nodes is numbered in hierarchical order, all nodes are numbered from 1 to N. A tree is a complete tree if all its nodes are in the same position as the nodes numbered from 1 to n of a full tree of the same depth.
Look at this, look at this, I’m at a loss, to put it simply, it’s this:
For a complete binary tree, the leaf nodes only appear in the last 2 layers, and the leaf nodes in the last layer are left-aligned.
I want to add another concept here, which is that the leaves come in pairs. What does that mean? For a binary tree, there are at most two children of a node, and two nodes under one node can be said to come in pairs, like this
That should make sense. So if you look at a perfect binary tree, if the leaves are in the last and the second to last, then the last leaves must be in pairs, and the last leaves can not be in pairs, but if they’re single they have to be to the left, and that’s it
Then let’s look at this definition:
If a binary tree with n nodes is numbered in hierarchical order, all nodes are numbered from 1 to N. A tree is a complete tree if all its nodes are in the same position as the nodes numbered from 1 to n of a full tree of the same depth.
Let’s start by numbering a full binary tree, starting at the root, from top to bottom, left to right
And then we look at this binary tree and we number it
And then compare that to the full binary tree up there
The order here is one to one, so the binary tree is a perfect binary tree, so it’s not one to one. Look at this
So this is not a perfect binary tree.
After all this analysis, we should already know what a perfect binary tree is. Let’s take a look at these little summaries:
1. A complete binary tree must be a full binary tree from the root node to the penultimate layer
2. A full binary tree must be a complete binary tree, but a complete binary tree is not necessarily a full binary tree
And then there are actually these properties for a complete binary tree:
- A node with degree 1 has only the left subtree
- There are either 1 or 0 nodes of degree 1
- With the same number of nodes, the height of the safe binary tree is the smallest
The three special binomial trees are distinguished from relations
First see true binary tree and binary tree, this requires each branch node is full, that is, each node has two fork, which is about child nodes, of course, except the leaf node, meet this is really a binary tree, if coupled with a condition on this condition, all the leaf nodes in the same level, that is full binary tree.
In other words, except for the leaf nodes, every node has left and right child nodes, and that is a true binary tree. If on top of that, all the leaves are at the same level, it’s a full binary tree
For complete binary tree, the leaf node can only in the last two layers, and in addition to the last layer of the leaf node, other nodes are full, the second from bottom, that is, if there is also a leaf node, it must be about child node is complete (in pairs), the last layer of the leaf node can be disgruntled, but can only be left children
Ok, these three goods, everyone should understand well!
How do I store binary trees
This is a relatively difficult point, need to think, otherwise difficult to understand
First of all, you know, the data structure is divided into physical structure and logical structure, such as array data structure is belong to the physical structure, the somebody else is how how is stored in memory, but for logical structure such as the binary tree here, seems can not be saved directly, but the logical structure of data structure can use a variety of physical structure to store
Generally speaking, it is an array and a linked list, these two versatile ah, many things seem to have the bottom of these two goods.
So the same is true for binary trees, you can use linked lists and arrays.
Use a linked list to store
Using a linked list to store data in a tree structure seems like the most intuitive thing to do. Let’s look at the graph
That is to say, each node contains three parts, one is the data stored by the node, and the other two are the memory addresses of the left and right children of the node. This looks very intuitive, and the tree structure is very close to the original appearance.
As a review of linked lists, one after the other, each list node contains a data variable and a next pointer. In the case of a binary tree, there are two next Pointers because we are referring to the left and right child nodes.
Now we’re going to look at using arrays how do we store binary trees
Use an array to store
Arrays are relatively less intuitive. To understand how arrays are stored in binary trees, you must first establish the following concept in your mind:
That is, each node in a binary tree has its own number starting with the node
Why? Don’t arrays have subscripts? There’s a one-to-one correspondence here.
So if you think of a full binary tree, you number each node from the root, left to right, top to bottom, and then you put them in the array, and remember, the array starts at zero.
In other words, the root node is placed at zero, so in this case it’s stored sequentially, and there may be other cases like this
It’s not a full binary tree, it’s not a full binary tree, it’s not a full binary tree, it’s not a full binary tree, it’s not a real binary tree, it’s just a normal binary tree
How do I store this? See the picture
It’s very simple. I’m going to leave the corresponding position empty, which means that the binary tree used to have a 6 position in it, but now it’s gone, so it’s going to have a 5 position in the array, so if it’s not there it’s empty.
Why do we do that? Because it preserves the position of the binary tree, so that we can locate certain nodes in the binary tree according to some of the properties of the binary tree.
And then we have the following formulas for solving the parent and left and right nodes of a binary tree
If a parent node has an index, then its left index is 2index+1 and its right index is 2index+2
The reverse is the same
If the leftindex of a node is leftindex then its parent node is (leftindex-1) /2
But what you’ll see here is, for a representation like this, if a binary tree is empty in a lot of places, then the corresponding array location is also empty, and the array allocates memory, once it allocates, it doesn’t change, so it’s a waste of memory
So you have to think about what kind of binary tree is suitable for arrays!
Ok ok, that’s it, after all, there are many more!
Application of binary trees
We above bala bala said a lot, so this binary tree in the end what use ah, but also make the strange trouble, in practice, the role of the binary tree mainly has two parts:
2. To maintain relative order
What do you mean? Let me explain.
Used to find
Each node of a binary tree can actually be regarded as an index, so a binary tree is a good data structure for searching, and there is a special binary tree structure called a binary search tree, which is mainly used for searching
Since it is a special structure of binary tree, there are some different places relative to binary tree:
1. If the left subtree is not empty, then the values of all nodes in the left subtree are less than the value of the root node 2. If the right subtree is not empty, then the values of all nodes in the right subtree are greater than the value of the root node 3
That is, the values on the left are smaller than the root node, and the values on the right are larger than the root node, so that there are two extreme values, the bottom left is the smallest one, and the bottom right is the largest one
In this way, you can find a value fairly quickly, and you can compare the value you’re looking for to the root node, and then see whether it’s compared to the left node, or to the other nodes, sort of guessing whether it’s bigger or smaller.
We’ll talk about binary search trees separately in the future.
Used to maintain relative order
A binary search tree is also called a binary sort tree because it has a set of values for each node
If you want to insert a new value you have to put it in the right place
But one of the things that can happen when you’re inserting is that you’re inserting all the way to the left, so the root is 10, and then 9,8,7,6,5,4 will look like this
This involves binary tree self-balancing, which can be done in a variety of ways, such as red-black trees (emphasis), AVL trees, tree stacks, etc.
These knowledge points, are also very important and more content, later to write a separate article to introduce (continue to pay attention to my public number: code, to avoid losing contact)
Traversal of a binary tree
Next comes the binomial tree traversal piece, about this piece in fact the first task is to make clear a few more easily confused traversal way, also is not confused, is easy to forget 😂
Binary tree traversal can be divided into two ways. One is to traverse according to the relationship between node positions, and the other is to traverse according to the macro Angle. In the macro… Oh, my god. Let’s see a picture
See, that’s what the traversal looks like, so let’s talk about 😂
The former sequence traversal
Foreorder traversal Remember that the output order is: root, left subtree, right subtree
The other thing to understand here, if you go to the root node, and then you go to the left subtree of the root node, is that when you go to the left subtree, you don’t immediately go to the right subtree, you see if there’s a left subtree in the left subtree, and that’s important to understand.
If you look at the diagram, you understand that the black numbers in the diagram are the order of the preorder traversal.
In the sequence traversal
Output order: left subtree, root node, right subtree
In order traversal is the same as in order traversal, in addition to the need to add a point, the traversal starts from the root node in order to traverse, look at the figure:
After the sequence traversal
The output sequence is left subtree, right subtree, and root node.
Keep looking at the picture:
Sequence traversal
Sequential traversal may sound confusing, but the actual sequence of output is best understood, which is to output from the root node to each node in a hierarchical relationship, remember when we numbered the full binary tree?
Start at the root node, top to bottom, left to right
This is best understood
Depth first and breadth first
What does depth first and breadth first mean?
Depth first, deep, deep, deep, deep, deep, deep, deep, deep, deep
As for breadth first, breadth first focuses on a cross section. Breadth should be broad and don’t go all the way to the end, which is the opposite of depth first!
Ok, here is almost enough, understand the above, go out and talk with the interviewer no problem, but, if you write handwritten code, that you hang, don’t worry, there will be a special article about binary tree related to various code coding, such as various iterations, and storage and so on!
Thank you for reading
When I was in college, I chose to learn Java by myself. When I was working, I found that I had a poor computer foundation and a poor education background. I can only make up for it the day after tomorrow. All the experiences are written, organized into a PDF with a catalog, continue to be original, PDF in the public number continue to update, if you are not willing to mediocrity, then together with me in the code, grow!
In fact, there are not only technologies, but also things beyond those technologies, such as how to be a sophisticated programmer, not a “diaosi”, == programmer itself is a noble existence, isn’t it? = =
Very welcome you to join, in the future, coding, you have me, together to do a == people are not stupid, a lot of money, live long == happy programmers!
Reply to the keyword “PDF”, obtain technical articles collection, has been sorted out, with the directory, welcome to exchange technology!
In addition, reply to “Qingge”, see the surprise gift package prepared by Qingge for you, only for the first time to pay attention to you!
Any questions, you can add Qingo wechat: H653836923, in addition, I have an exchange group, I will not regularly in the group to share learning resources, benefits, interested can say I invite you!
== By the way, if you are a Small white Java, you can also add me wechat, I believe you must encounter a lot of problems in the process of learning, maybe I can help you, after all, I have been there! = =
Thank you for reading 🥰