“This is the 17th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”.
This paper introduces in detail the basic concept of binary tree, and various binary trees, and the implementation of binary tree in Java, including the implementation of sequential results and chain structure.
A binary tree is a special kind of tree, which is defined as: a binary tree is a finite set of N (n>=0) nodes, which is either an empty set (called an empty binary tree), or consists of a root node and two disjoint left and right subtrees called root nodes respectively.
1 The definition of binary tree
A binary tree is a special kind of tree, which is defined as: a binary tree is a finite set of N (n>=0) nodes, which is either an empty set (called an empty binary tree), or consists of a root node and two disjoint left and right subtrees called root nodes respectively. If you are not familiar with the concept of trees, you can read this article: Data Structure-Tree introduction and Java implementation cases.
Here is a binary tree:
2 Properties of binary trees
Three features:
- Each node has at most two subtrees, so there is no node with a degree greater than 2 in a binary tree. Notice that instead of only having two subtrees, there are at most. It’s okay to have no subtrees or one subtree.
- The left and right subtrees are ordered and cannot be reversed arbitrarily.
- Even if there is only one subtree on a node in the tree, it is important to distinguish between left and right subtrees.
The following example: a tree of 3 nodes, for ordinary tree and binary tree, how many forms? 
Special binary trees
3.1 Oblique binary tree
A binary tree in which all nodes have only left subtrees is called a left inclined tree. All nodes are binary trees with only right subtrees called right-inclined trees. These two are collectively known as inclined trees.
Left oblique tree:
Right inclined tree:
3.2 Full binary tree
In a binary tree, if all branches have left and right subtrees and all leaves are on the same level, such a binary tree is called a full binary tree, also known as a perfect binary tree.
Full binary tree features:
- Leaves can only appear in the bottom layer. Balance is not possible on other layers.
- The degree of the non-leaf node must be 2. Otherwise, you’re missing arms and legs.
- In the same depth of the binary tree, the full binary tree has the largest number of nodes and leaves.
3.3 Complete binary tree
Complete binary tree: remove the last layer of leaf nodes, it is a full binary tree, and the nodes of the last layer can only be concentrated on the left side, a full binary tree must be a complete binary tree, a complete binary tree is not necessarily a full binary tree. 
- Leaf nodes can only appear in the bottom two layers.
- The lowest level of leaves must be concentrated in the left continuous position.
- In the penultimate layer, if there are leaf nodes, they must be concentrated in the right continuous position.
- If the node degree is 1, the node has only left children, that is, there is no right subtree.
- A complete binary tree with the same number of nodes has the smallest depth.
3.4 Balancing binary trees
Balanced binary tree is also called AVL tree (different from AVL algorithm), which has the following properties:
- It must be a binary sort tree;
- It is an empty tree or the absolute value of the difference in height between the left and right subtrees is no more than 1, and both subtrees are balanced binomial trees.
Balancing binary trees is the key and difficult point, which is not described here and will be dealt with separately in later articles.
Properties of binary trees
There are about six properties that can be used directly to implement binary trees:
-
There are at most 2^(i-1) nodes (I ≥1) on the i-th layer of the binary tree;
-
The binary tree with depth of K has at most 2^ K-1 nodes (k≥1) and at least K nodes.
-
For any binary tree, if the number of leaf nodes is N0 and the total number of nodes of degree 2 is N2, then N0=N2+1;
-
The complete binary tree with n nodes depth for | | log2n + 1 (x | | says the biggest integer no greater than x).
-
If all nodes in a complete binary tree with N nodes are stored in sequence and I is the node number (starting from 1), the relationship between nodes is as follows:
- If I = 1, node I is the root of the binary tree; If I > 1, the parent node is numbered I/2, the left child node is numbered 2 * I (if it exists), and the right child node is numbered 2 * I + 1 (if it exists).
- If 2 * I <= N, the number of its left child (the root node of the left subtree) is 2 * I; If 2 * I > N, there is no left or right child;
- If 2 * I + 1 <= N, the node number of its right child is 2 * I + 1. If 2 * I + 1 > N, there is no right child.
-
If all nodes of a complete binary tree with N nodes are stored in sequence and I is the node number (starting from 0), the relationship between nodes is as follows:
-
If I = 0, node I is the root of the binary tree; If I > 0, the parent node is numbered (i-1)/2, the left child node is numbered 2 * I + 1 (if any), and the right child node is numbered 2 * I + 2 (if any).
-
If 2 * I +1 <= N, the number of its left child (the root node of the left subtree) is 2 * I +1; If 2 * I + 1 > N, there is no left or right child;
-
If 2 * I + 2 <= N, the node number of its right child is 2 * I + 2. If 2 * I + 2 > N, there is no right child.
-
The figure above is a complete numbered binary tree with N=10 nodes. Let I start at 1 and verify each feature below:
- The node where I = 1 is really the root node; If I = 5 > 0, then the parent node is numbered 5/2, which is 2.
- If I=5, 2 * 5 = 10, the left child of the node numbered 5 is numbered 2 * 5 = 10. If I=6, 2 * 6 > 10, the node numbered 6 has no left child.
- If I = 4, 2 * 4 + 1 < 10, the child on the right of the node numbered 4 is numbered 2 * 4 + 1 = 9. If I=5, 2 * 5 + 1 > 10, node 5 has no right child.
The last feature: given n nodes, f(n) different binary trees can be formed. F (n)Carter LAN numberThe NTH term of:
5 Storage structure of binary trees
5.1 Sequential Storage Structure
5.1.1 Overview of sequential Storage Architecture
Sequential storage structures are difficult to implement for trees, which are one-to-many relational structures. But binary tree is a special kind of tree, because of its particularity, it can be realized by sequential storage structure.
The sequential storage structure of binary tree is to use a one-dimensional array to store nodes in the binary tree, and the storage location of nodes, that is, the subscript of the array, should reflect the logical relationship between nodes, such as the relationship between parents and children, the relationship between left and right brothers, etc.
At this point, the regularity and superiority of complete binary trees appear:
Because of the properties of complete binary trees, the complete binary tree in the figure above can be traversed from top to bottom and from left to right, and then stored in the corresponding positions of the array index in order:
For general binary trees, we can “borrow” the idea of complete binary trees and empty the empty node positions:
As in the ordinary binary tree shown above, it is “converted” to a full binary tree when stored, and non-existent nodes are filled with NULL:
In the extreme case, a right-slanted tree of depth K, with only K nodes, needs to allocate 2^ K -1 memory cells, which obviously wastes a lot of space.
Therefore, the sequential storage structure only applies to complete or full binary trees.
5.1.2 Simple implementation of sequential storage structure
Provides a simple implementation of the sequential storage structure of a binary tree, nodes are not allowed to be NULL.
It can be seen that the addition and acquisition of child nodes and parent nodes are all dependent on the fifth formula of binary tree properties. Here, the binary tree to be realized is regarded as a complete binary tree, which is relatively simple, but may waste memory space.
/** * simple implementation of binary tree sequential storage structure */
public class ArrayBinaryTree<E> {
/** * depth */
private int deep;
/** * Capacity, also the number of nodes */
private int capacity;
/** * the underlying array */
private Object[] elements;
/** * Actual number of nodes */
private int size;
/** * specifies the tree depth, initializes the array **@paramDeep tree depth */
public ArrayBinaryTree(int deep) {
this.deep = deep;
this.elements = new Object[capacity = (int) Math.pow(2, deep) - 1];
}
/** * Specifies the tree depth and root node **@param deep
* @param root
*/
public ArrayBinaryTree(int deep, E root) {
this(deep);
addRoot(root);
}
/** * Add the root node **@paramRoot Root node data */
public void addRoot(E root) {
checkNullData(root);
elements[0] = root;
size++;
}
/** ** Add child nodes **@paramParentIndex Index of the parent node *@paramData Node data *@paramLeft is the left child node. False no *@returnAdd the index */ of the child node
public int addChild(int parentIndex, E data, boolean left) {
checkParentIndex(parentIndex);
checkNullData(data);
int childIndex;
if (left) {
childIndex = parentIndex * 2 + 1;
} else {
childIndex = parentIndex * 2 + 2;
}
addChild(childIndex, data);
size++;
return childIndex;
}
/** * Add child node **@paramChildIndex Indicates the index of a child node@paramData Data of the child node */
private void addChild(int childIndex, E data) {
if(elements[childIndex] ! =null) {
throw new IllegalStateException("The parent node already exists the child node");
}
elements[childIndex] = data;
}
/** * is an empty tree **@returnIs true; False no * /
public boolean isEmpty(a) {
return elements[0] = =null;
}
/** * returns the number of nodes **@returnNode number * /
public int size(a) {
return size;
}
/** * Gets the parent of the index node **@paramThe index index *@returnParent node data */
public E getParent(int index) {
if (index == 0) {
return null;
}
return (E) elements[(index - 1) / 2];
}
/** * gets the right child of the index node **@paramThe index index *@returnData of the right child node */
public E getRight(int index) {
if (2 * index + 1 >= capacity) {
return null;
}
return (E) elements[index * 2 + 2];
}
/** * gets the left child of the index node **@paramThe index index *@returnLeft child */
public E getLeft(int index) {
if (2 * index + 1 >= capacity) {
return null;
}
return (E) elements[2 * index + 1];
}
/** * get the root node **@returnRoot node data */
public E getRoot(a) {
return (E) elements[0];
}
/** * retrieves the first index position **@paramData Node data *@returnNode index, or -1-- the node */ does not exist
public int indexOf(E data) {
for (int i = 0; i < capacity; i++) {
if (elements[i].equals(data)) {
returni; }}return -1;
}
/** * Check whether the child node already exists@paramMessage message * /
private void checkChild(int childIndex, String message) {
if (elements[childIndex] == null) {
throw newIllegalStateException(message); }}/** * data is null **@paramData Indicates the added data */
private void checkNullData(E data) {
if (data == null) {
throw new NullPointerException("Data cannot be null"); }}/** * Check whether the parent node has **@paramParentIndex Index of the parent node */
private void checkParentIndex(int parentIndex) {
if (elements[parentIndex] == null) {
throw new NoSuchElementException("Parent node does not exist"); }}}Copy the code5.2 Chain storage structure
It is more flexible to use the chain storage structure. A data field and two reference variables are designed for the tree node, one saves the reference of the left child node and the other saves the reference of the right child node. We call such linked list as binary linked list. You can also add references to variables in a save parent node if necessary.
5.2.1 Simple implementation of chain storage structure
The following is a simple implementation of a binary tree chain storage structure with no references to the parent node. Finding the parent node is difficult and requires traversing the entire tree, so it is recommended to add references to the parent node.
/** * simple implementation of binary tree chain storage structure */
public class LinkedBinaryTree<E> {
/** * Externally holds a reference to the root node */
private BinaryTreeNode<E> root;
/** * The number of nodes in the tree */
private int size;
/** * Internal node object **@param<E> Data type */
public static class BinaryTreeNode<E> {
/ / data domain
E data;
// Left child node
BinaryTreeNode<E> left;
// Right child node
BinaryTreeNode<E> right;
public BinaryTreeNode(E data) {
this.data = data;
}
public BinaryTreeNode(E data, BinaryTreeNode<E> left, BinaryTreeNode<E> right) {
this.data = data;
this.left = left;
this.right = right;
}
@Override
public String toString(a) {
returndata.toString(); }}/** * empty constructor */
public LinkedBinaryTree(a) {}/** * constructor to initialize the root node **@paramRoot Root node data */
public LinkedBinaryTree(E root) {
checkNullData(root);
this.root = new BinaryTreeNode<>(root);
size++;
}
/** * Add child node **@paramParent A reference to the parent node@paramData Node data *@paramLeft is the left child node. False no * /
public BinaryTreeNode<E> addChild(BinaryTreeNode<E> parent, E data, boolean left) {
checkNullParent(parent);
checkNullData(data);
BinaryTreeNode<E> node = new BinaryTreeNode<>(data);
if (left) {
if(parent.left ! =null) {
throw new IllegalStateException("The parent node already has a left child, adding failed");
}
parent.left = node;
} else {
if(parent.right ! =null) {
throw new IllegalStateException("The parent node already has a right child, adding failed");
}
parent.right = node;
}
size++;
return node;
}
/** * is an empty tree **@returnIs true; False no * /
public boolean isEmpty(a) {
return size == 0;
}
/** * returns the number of nodes **@returnNode number * /
public int size(a) {
return size;
}
/** * get the root node **@returnThe root node. Or null-- an empty tree */
public BinaryTreeNode<E> getRoot(a) {
return root;
}
/** * gets the left child node **@paramParent Parent node reference *@returnLeft child or NULL -- there is no left child */
public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
return parent == null ? null : parent.left;
}
/** * get the right child node **@paramParent Parent node reference *@returnRight child or NULL -- there is no right child */
public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
return parent == null ? null : parent.right;
}
/** * data is null **@paramData Indicates the added data */
private void checkNullData(E data) {
if (data == null) {
throw new NullPointerException("Data cannot be null"); }}/** * Check whether the parent node is null **@paramParent Parent node references */
private void checkNullParent(BinaryTreeNode<E> parent) {
if (parent == null) {
throw new NoSuchElementException("The parent node cannot be null"); }}}Copy the code6 summarizes
Introduction to this article to introduce the binary tree of knowledge, such as the concept of binary tree, characteristics, properties, etc., these things are a lot of is dead, but we need to understand the memory, finally introduced the binary tree storage structure, simple implementation, as well as the Java language for more special binary trees, such as red and black tree, they also have their own unique implementation, This will be covered in subsequent articles.
In addition, in the implementation case, there is no tree traversal, and the creation of the whole tree and other operations, this part is more content, will be introduced separately in the subsequent article, you can pay attention to the update of the article. Finally, if you are not too clear about the concept of trees, you can read this article: Data Structure – Tree introduction principles and Java implementation cases.
Related articles:
- Big Talk Data Structure
- “The algorithm”
- Diagram of algorithms
If you don’t understand or need to communicate, you can leave a message. In addition, I hope to like, collect, pay attention to, I will continue to update a variety of Java learning blog!