The concept of binary tree
A binary tree is a finite set of n (n>=0) nodes. This set is either an empty set (empty binary tree), or consists of a root node and two binary trees that do not intersect each other, called the root node and the right subtree respectively.
Characteristics of binary trees
Each node has at most two subtrees, so there are no nodes with a degree greater than 2 in the binary tree. Each node in the binary tree is an object, and each data node has three pointers, namely pointers to the parent, left child and right child. Each node is connected to each other through a pointer. The relationship between the connected pointers is all father-son relationship.
Definition of binary tree nodes
The binary tree node is defined as follows:
The code copy is as follows:
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
Five basic forms of binary trees
Empty binary tree
There is only one root node
The root node has only the left subtree
The root node has only the right subtree
The root node has both a left and a right subtree
There are only two cases for ordinary trees with three nodes: two or three. However, since the binary tree has to distinguish left and right, it will evolve into the following five forms:
Special binary tree
Slanted tree
As shown in the second and third small pictures in the penultimate sub-picture above.
Full binary tree
In a binary tree, if all branch nodes have left and right subtrees, and all leaves are on the same layer, such a binary tree is called a full binary tree. As shown in the figure below:
Complete binary tree
A completely binary tree means that the last layer is full on the left, the right side may be full or not, and the rest of the layers are full. A binary tree with a depth of k and a number of nodes of 2^k - 1 is a full binary tree (complete binary tree). It is a tree with a depth of k and no space.
The characteristics of a completely binary tree are:
Leaf nodes can only appear in the lowest two layers.
The lowest leaf must be concentrated in a continuous position on the left.
In the penultimate layer, if there are leaf nodes, they must be in continuous positions on the right.
If the node degree is 1, then the node has only the left child.
For binary trees with the same node tree, the complete binary tree has the smallest depth.
Note: A full binary tree must be a completely binary tree, but a completely binary tree may not be a full binary tree.
The algorithm is as follows:
The code copy is as follows:
bool is_complete(tree *root)
{
queue q;
tree *ptr;
// Perform breadth priority traversal (hierarchical traversal) and put NULL nodes into the queue as well
q.push(root);
while ((ptr = q.pop()) != NULL)
{
q.push(ptr->left);
q.push(ptr->right);
}
// Determine whether there are still nodes that have not been accessed
While (!q.is_empty())
{
ptr = q.pop();
// If there are non-NULL nodes that are not accessed, the tree has a void and is a non-complete binary tree.
if (NULL != ptr)
{
return false;
}
}
return true;
}
Properties of binary trees
Property 1 of the binary tree: There are at most 2^(i-1) nodes on the i-th layer of the binary tree (i>=1)
Property 2 of binary tree: Binary tree with depth k has at most 2^k-1 nodes (k>=1)
Sequential storage structure of binary trees
The sequential storage structure of a binary tree is to use a one-dimensional array to store each node in the binary tree, and the storage location of the nodes can reflect the logical relationship between nodes.
Binary link list
Since the sequential storage method is not very applicable, we must consider the chain storage structure. According to international practice, binary tree storage generally adopts a chain storage structure.
Each node of a binary tree has at most two children, so it is a natural idea to design a data field and two pointer fields for it. We call such a linked list a binary linked list.
Traversal of binary trees
Traversing binary tree refers to accessing all nodes in the binary tree in a certain order from the root node, so that each node is accessed once and only once.
There are three ways to traverse binary trees, as follows:
(1) Pre-order traversal (DLR), first accessing the root node, then traversing the left subtree, and finally traversing the right subtree. Abbreviated root - left - right.
(2) In-order traversal (LDR), first traversal the left subtree, then access the root node, and finally traversal the right subtree. Abbreviated Note: Left-root-right.
(3) Post-order traversal (LRD), first traversing the left subtree, then traversing the right subtree, and finally accessing the root node. Abbreviated Left-Right-Root.
Preamble traversal:
If the binary tree is empty, the empty operation returns. Otherwise, first access the root node, then traverse the left subtree in the previous order, and then traverse the right subtree in the previous order.
The order of traversal is: ABDHIEJCFKG
The code copy is as follows:
//Precise traversal
function preOrder(node){
if(!node == null){
putstr(node.show()+ " ");
preOrder(node.left);
preOrder(node.right);
}
}
In-order traversal:
If the tree is empty, the empty operation returns, otherwise it starts from the root node (note that the root node is not accessed first), and the left subtree of the root node is traversed in the middle order, then the root node is accessed, and finally the right subtree is traversed in the middle order.
The order of traversal is: HDIBEJAFKCG
The code copy is as follows:
//Use recursive method to implement middle order traversal
function inOrder(node){
if(!(node == null)){
inOrder(node.left);//Add to the left subtree first
putstr(node.show()+ " ");//Add to the root node again
inOrder(node.right);//Last access to the right subtree
}
}
Post-order traversal:
If the tree is empty, the empty operation returns. Otherwise, the left and right subtrees are traversed from left to right to access the left and right subtrees, and finally access the root node.
The order of traversal is: HIDJEBKFGCA
The code copy is as follows:
//Post-order traversal
function postOrder(node){
if(!node == null){
postOrder(node.left);
postOrder(node.right);
putStr(node.show()+ " ");
}
}
Implement binary search tree
The Binary Lookup Tree (BST) is composed of nodes, so we define a Node node object as follows:
The code copy is as follows:
function Node(data,left,right){
this.data = data;
this.left = left;//Save left node link
this.right = right;
this.show = show;
}
function show(){
return this.data;//Show data saved in the node
}
Find maximum and minimum values
Finding the minimum and maximum values on the BST is very simple, because the smaller values are always on the left child node, and looking for the minimum value on the BST, just traverse the left child tree until the last node is found
Find the minimum value
The code copy is as follows:
function getMin(){
var current = this.root;
while(!(current.left == null)){
current = current.left;
}
return current.data;
}
This method traverses one by one along the left subtree of BST until it traverses to the leftmost node of BST, which is defined as:
The code copy is as follows:
current.left = null;
At this time, the value saved on the current node is the minimum value
Find the maximum value
Finding the maximum value on BST only requires traversing the right subtree until the last node is found, and the value saved on that node is the maximum value.
The code copy is as follows:
function getMax(){
var current = this.root;
while(!(current.right == null)){
current = current.right;
}
return current.data;
}