A binary tree is that simple
This article puts aside some very bitter, difficult to understand the concept of binary trees, just start to watch (or review)….
First, let’s talk about what a tree is:
- Tree is a kind of nonlinear data structure. Compared with linear data structure (linked list, array), the average running time of tree is shorter (often the complexity of tree-related sorting time is not high).
In real life, our average tree looks like this:
But in the programming world, we tend to “reverse” the tree to make it easier to analyze:
The average tree has lots and lots of branches, and lots and lots of branches under branches, and that can be very cumbersome to study in a program. Because trees are nonlinear, and our computer’s memory is linear, we can’t design it if it’s too complicated.
So let’s start with the simple and often used binary tree
1.1 Some concepts of trees
I will take the above picture to draw to explain:
A binary tree means that each node can have no more than two sons, as shown in the figure above.
- A tree will have at least one node (root node)
- A tree consists of nodes, the data structure of each node is as follows:
- Therefore, when we define a tree, we often use **-> define nodes -> nodes to form a tree, and the definition of a node is: one data, two Pointers (if there is a node to point to the node, no node to point to null).
1.2 Statically Creating a Binary Tree
As mentioned above, a tree is composed of several nodes, which are connected to form a tree, and the node consists of one data and two Pointers
- So creating a tree is essentially creating nodes and then joining them
First, define a node using a Java class:
public class TreeNode {
// Left node (son)
private TreeNode lefTreeNode;
// Right node (son)
private TreeNode rightNode;
/ / data
private int value;
}
Copy the codeLet’s take this binary tree as an example to build it:
To make it easier to build, I gave it a constructor with arguments and a set and get method:
public TreeNode(int value) {
this.value = value;
}
Copy the codeSo we have now created five nodes:
public static void main(String[] args) {
// Root node -->10
TreeNode treeNode1 = new TreeNode(10);
// Left child -->9
TreeNode treeNode2 = new TreeNode(9);
// Right child -->20
TreeNode treeNode3 = new TreeNode(20);
// The left child of 20 -->15
TreeNode treeNode4 = new TreeNode(15);
// The right child of 20 -->35
TreeNode treeNode5 = new TreeNode(35)}Copy the codeTheir current state looks like this:
So let’s connect it up:
// The left and right children of the root node
treeNode1.setLefTreeNode(treeNode2);
treeNode1.setRightNode(treeNode3);
// About 20 children
treeNode3.setLefTreeNode(treeNode4);
treeNode3.setRightNode(treeNode5);
Copy the codeOnce connected, our tree is created.
1.3 Traversing the binary tree
Our tree creation is complete. If we can iterate over it like an array (see its data), then it is complete
It is worth noting that there are three ways to traverse a binary tree
- The first sequence traversal
- First access the root node, then the left node, and finally the right node (root -> left -> right)
- In the sequence traversal
- First access the left node, then the root node, and finally the right node (left -> root -> right)
- After the sequence traversal
- First access the left node, then the right node, and finally the root node (left -> right -> root)
Take the above binary tree as an example:
- If it isThe first sequence traversal:
10-20 - > > 9 - > 15 - > 35 - If it isIn the sequence traversal:
9-10-15 - > 20 - > > > 35- Possible explanation: after visiting 10 nodes, we go to 20 nodes, but there are children at 20 nodes, so we first visit 15 nodes, the left son of 20. Because node 15 has no sons. So go back to 20 nodes and visit 20 nodes. Finally, visit 35 nodes
- If it isAfter the sequence traversal:
9-15-35-20 - > > > > 10- Possible explanation: 9 nodes are visited first, then 20 nodes should be visited, but there are children at 20, so 15 nodes, the left son of 20, is visited first. Because node 15 has no sons. So we go to 35 nodes, and since 35 has no sons, we return 20 nodes, and we return 10 nodes
Summary in one sentence: first order (root -> left -> right), middle order (left -> root -> right), rear order (left -> right -> root). If accessing a node with children, process the children first and return later
Regardless of traversal first, traversal of each node if it visits a node with children will process the children first (logic is the same)
- So it’s easy to think of recursion
- The exit of recursion is: when there are no children, return
Therefore, we can write sequential traversal code like this:
/** * traverses * in order@paramRootTreeNode Root node */
public static void preTraverseBTree(TreeNode rootTreeNode) {
if(rootTreeNode ! =null) {
// Access the root node
System.out.println(rootTreeNode.getValue());
// Access the left node
preTraverseBTree(rootTreeNode.getLefTreeNode());
// Access the right nodepreTraverseBTree(rootTreeNode.getRightNode()); }}Copy the codeThe result is the same as what we just said:
Let’s call the middle order traversal again:
/** **@paramRootTreeNode Root node */
public static void inTraverseBTree(TreeNode rootTreeNode) {
if(rootTreeNode ! =null) {
// Access the left node
inTraverseBTree(rootTreeNode.getLefTreeNode());
// Access the root node
System.out.println(rootTreeNode.getValue());
// Access the right nodeinTraverseBTree(rootTreeNode.getRightNode()); }}Copy the codeThe result is the same as what we just said:
The interesting thing is that we can restore the original binary tree by preordering and middle or middle and last, but we can’t restore the original binary tree by preordering and subsequent
- In other words: we can determine a binary tree by middle order and pre-order or middle order and post-order!
Create a binary tree dynamically
We create the binary tree manually, usually: give you an array, let you turn the array into a binary tree, then we need to create the binary tree dynamically.
There is also a special kind of binary tree: binary search tree
- Definition:The left side of the current root node is all smaller than the root node and the right side of the current root node is all larger than the root node.
- And you can see that this is very convenient for us to find a number
Most of the time when we create binary trees on the fly, we create binary search trees
2.1 Dynamic Binary Tree Creation Experience
Int [] Arrays = {3, 2, 1, 4, 5};
So the steps to create a binary tree look like this:
- Let’s start with 3 as the root
- And then 2 comes in, let’s compare it to 3, smaller than 3, so it’s to the left of 3
- And then 1 comes in, and we compare it to 3, it’s less than 3, so it’s to the left of 3, so it’s 2 to the left of 3, so it’s less than 2, it’s to the left of 2
- And then 4 comes in, and we compare it to 3, so it’s bigger than 3, so it’s to the right of 3
- And then 5 comes in, and we compare it to 3, so it’s bigger than 3, so it’s to the right of 3, so there’s 4 to the right of 3, so it’s bigger than 4, so it’s to the right of 4
So we have a binary search tree, and whatever subtree we have, the left side is smaller than the root, and the right side is larger than the root
2.2 Code Implementation
Our code implementation is also very simple, if smaller than the current root node, put it to the left of the current root node, if larger, put it to the right of the current root node.
Because it is created dynamically, we use a class to represent the root node
public class TreeRoot {
private TreeNode treeRoot;
public TreeNode getTreeRoot(a) {
return treeRoot;
}
public void setTreeRoot(TreeNode treeRoot) {
this.treeRoot = treeRoot; }}Copy the codeCompare with the root who is big, big to the right, small to the left:
/** * dynamically create binary lookup tree **@paramTreeRoot root *@paramValue Specifies the value of the node */
public static void createTree(TreeRoot treeRoot, int value) {
// If the root is empty (first access), use the first value as the root node
if (treeRoot.getTreeRoot() == null) {
TreeNode treeNode = new TreeNode(value);
treeRoot.setTreeRoot(treeNode);
} else {
// Current root
TreeNode tempRoot = treeRoot.getTreeRoot();
while(tempRoot ! =null) {
// The current value is greater than the root value, go to the right
if (value > tempRoot.getValue()) {
// There is no root on the right side
if (tempRoot.getRightNode() == null) {
tempRoot.setRightNode(new TreeNode(value));
return ;
} else {
If there is a root on the right, go to the root on the righttempRoot = tempRoot.getRightNode(); }}else {
// If there is no root on the left, insert it directly
if (tempRoot.getLefTreeNode() == null) {
tempRoot.setLefTreeNode(new TreeNode(value));
return;
} else {
If there is a root on the left, go to the root on the left
tempRoot = tempRoot.getLefTreeNode();
}
}
}
}
}
Copy the codeTest code:
int[] arrays = {2.3.1.4.5};
// Create a tree dynamically
TreeRoot root = new TreeRoot();
for (int value : arrays) {
createTree(root, value);
}
// Walk through the tree in order
preTraverseBTree(root.getTreeRoot());
System.out.println("--------------- official account: Java3y");
// Middle order traversal tree
inTraverseBTree(root.getTreeRoot());
System.out.println("--------------- official account: Java3y");
Copy the code
Query binary search tree correlation
3.1 Querying the tree depth
To query the depth of the tree, we can think of it as: the ratio of the number of words on the left subtree to the number of words on the right is greater than that of the left subtree, and then we can add the root node +1
public static int getHeight(TreeNode treeNode) {
if (treeNode == null) {
return 0;
} else {
// The left subtree depth
int left = getHeight(treeNode.getLefTreeNode());
// Right subtree depth
int right = getHeight(treeNode.getRightNode());
int max = left;
if (right > max) {
max = right;
}
return max + 1; }}Copy the code3.1 Querying the Maximum value of the tree
When traversing the binary search tree in order from above, careful students may find that the result of traversing the binary search tree in order is ~
So, if our binary tree is not a binary search tree, how do we query its maximum value?
It can go like this:
- Find the maximum on the left -> recursion
- Find the maximum on the right -> recursion
/** * find the maximum value of the tree **@param rootTreeNode
*/
public static int getMax(TreeNode rootTreeNode) {
if (rootTreeNode == null) {
return -1;
} else {
// Find the maximum value on the left
int left = getMax(rootTreeNode.getLefTreeNode());
// Find the maximum value on the right
int right = getMax(rootTreeNode.getRightNode());
// Compare to the current root node
int currentRootValue = rootTreeNode.getValue();
// Assume that the left side is the largest
int max = left;
if (right > max) {
max = right;
}
if (currentRootValue > max) {
max = currentRootValue;
}
returnmax ; }}Copy the codeFour, the last
Recursion is used to traverse the tree, find the depth, find the maximum, recursion is used very much in nonlinear data structures…
Tree application is also very wide, this article simply explained the tree data structure, advanced things I did not understand, may be used in the future will continue to in-depth…
If the article has the wrong place welcome to correct, everybody exchanges with each other. Students who are used to reading technical articles on wechat and want to get more Java resources can follow the wechat public account :Java3y