We know that data structure can be divided into linear structure and nonlinear structure according to the way of data storage, and trees belong to nonlinear structure.
A tree is a hierarchical set composed of n(n>0) finite nodes. When n=0, it’s called an empty tree.
This data structure is called a tree because it looks like an “upside-down tree,” with roots up and leaves down.
It has the following characteristics:
- A tree without a parent is called a root
- Each node can have one or more children
- Each non-root node has only one parent
Basic terms for trees
-
Degree of node: the number of subtrees of nodes
-
Tree degree: The maximum degree of all nodes in the tree
-
Path and path length: the path from node N1 to nk is a sequence of nodes n1, n2… , nk
Where ni is the parent of Ni +1. The number of edges a path contains is called the length of the path
-
Hierarchy of nodes: specify that the hierarchy of the root node is 1, and the hierarchy of any other node is the hierarchy of its parent node plus one
-
Tree depth: The maximum level of all nodes in a tree is the depth of the tree
Binary tree
Binary trees are just a special case of trees. The difference is:
- A binary tree can have at most two nodes per node
- The nodes in a binary tree are left and right. The order cannot be reversed
Binary trees have the following properties:
- There are at most 2I-1 nodes at level I of the binary tree
- A binary tree of depth k, with at most 2K-1 nodes (k>=1)
- n0 = n2N + 10Is the number of nodes with degree 0, n2 Number of knots of degree 2
Inclined tree
A binary tree where all nodes have only left subtrees is called a left slant 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 tree
Full binary tree
In a binary tree. A binary tree is called a full binary tree if all nodes have left and right subtrees and all leaves are on the same level.
Complete binary tree
A binary tree with N nodes is numbered by layers. If the node numbered I (1<= I <=n) is exactly in the same position as the node numbered I in the full binary tree with the same depth, the binary tree is called a complete binary tree.
Properties of complete binary trees:
- The depth of a complete binary tree with n nodes [log2N] + 1, where log2n is rounded down.
The storage structure of binary trees
The nodes of a binary tree can be stored using a one-dimensional array or a linked list.
Sequential storage
The sequential storage of binary tree is to store the nodes of the binary tree using a one-dimensional array, and the location of the nodes is the subscript index of the array.
Therefore, we know that the sequential storage structure of binary tree has the advantage of high search efficiency, and high efficiency of adding and deleting nodes.
The disadvantage is that when the binary tree structure is not a complete binary tree, it is easy to waste space.
For example, in the case of a slanted tree, most of the locations in the array have no storage nodes, wasting space.
The corresponding one-dimensional array is stored as follows:
Chain store
The chain storage of binary tree is the storage of nodes by linked list.
The structure of a node has one data field and two pointer fields.
Traversal of binary trees
Binary tree traversal means that all nodes in the binary tree are visited in a certain order starting from the root node, so that each node is visited once and only once.
The order of binary tree access can be divided into four types:
- The former sequence traversal
- In the sequence traversal
- After the sequence traversal
- Sequence traversal
The former sequence traversal
A front-order traversal first visits the root, then the left subtree, and finally the right subtree. When traversing the left and right subtrees, we still visit the root first, then the left subtree, and finally the right subtree.
In the sequence traversal
A middle-order traversal first traverses the left subtree, then the root, and finally the right subtree. When traversing the left and right subtrees, we still traverse the left subtree first, then the root, and finally the right subtree.
After the sequence traversal
Back-order traversal first traverses the left subtree, then the right subtree, and finally the root. When traversing the left and right subtrees, the left subtree is traversed first, then the right subtree, and finally the root.
Level traversal
Hierarchical traversal is traversing a binary tree from top to bottom according to the tree levels.
Binary tree code implementation
Sequential storage
package com.xgc.tree.binarytree.sequentialstoreage;
public class BinaryTree {
Object[] arr;
public void buildTree(Object[] arr) {
this.arr = arr;
}
/** * traverses * in order@paramThe root of the root tree */
public void preOrderTree(a) {
preOrderTree(0);
}
private void preOrderTree(int index) {
if (arr==null || arr.length == 0) return;
System.out.print(arr[index] + "");
if((index*2+1)<arr.length){
preOrderTree(index*2+1);
}
if((index*2+2)<arr.length){
preOrderTree(index*2+2); }}Middle-order and post-order traversals are similar to pre-order traversals
// The hierarchy traversal is easier, traversal the number of groups can be done
}
Copy the codeChain store
package com.xgc.tree.binarytree.linkedstoreage;
/** * the node of the binary tree *@author xgc
*
*/
public class TreeNode {
Object data;
/ / the left node
TreeNode left;
/ / right node
TreeNode right;
public TreeNode(Object data) {
this.data = data;
}
public TreeNode(TreeNode left , Object data, TreeNode right) {
this.left = left;
this.data = data;
this.right = right; }}Copy the codepackage com.xgc.tree.binarytree.linkedstoreage; @author XGC ** / public class TreeNode {Object data; // TreeNode left; // TreeNode right; public TreeNode(Object data) { this.data = data; } public TreeNode(TreeNode left , Object data, TreeNode right) { this.left = left; this.data = data; this.right = right; }}Copy the codeTesting:
package com.xgc.tree.binarytree.linkedstoreage;
public class BinaryTreeTest {
public static void main(String[] args) {
Object[] arr = {1.2.3.4.5.6.7.8.9};
BinaryTree tree = new BinaryTree();
TreeNode root = tree.buildTree(arr);
System.out.print("Sequential traversal");
tree.preOrderTree(root);
System.out.println();
System.out.print("Middle order traversal");
tree.inOrderTree(root);
System.out.println();
System.out.print("Post-order traversal");
tree.postOrderTree(root);
System.out.println();
System.out.print("Hierarchical traversal"); tree.levelOrderTree(root); System.out.println(); }}Copy the codeThe result is as follows:
1 2 4 8 9 5 3 6 7 2 4 8 9 5 1 3 6 7 2 4 8 9 5 3 6 7 1 level 1 2 3 3 4 5 6 7 8 9Copy the codeBinary search tree
Binary search tree: a binary tree that can be null. If it is not empty, it has the following properties:
-
The value of all nodes of a non-empty left subtree is less than the value of the root
-
The value of all nodes in a non-null right subtree is greater than the value of the root
-
Both the left and right subtrees are binary search trees
Binary search trees do not have duplicate elements, so they are not inserted when they do.
Binary search tree operation functions are:
- Insert new node
- Delete nodes
- Find maximum and minimum values
- Finds the node of the specified value
In the above operation, the operation of deleting nodes is more complex, so the implementation of the operation of deleting nodes is introduced, and the other is not introduced, it is ok to see the code.
Discussion on deletion operation classification of binary search tree:
-
The node to be deleted has no children, i.e. leaves.
So here we’re going to delete the parent node and we’re going to set the left or right of the parent node to NULL
“Left” and “right” depend on whether the node being deleted is the left or right of the parent node
If current is the current node to be deleted, we simply set parent. Left to null
-
The deleted node has a child node
Assign the child node to the left or right of the parent node to be deleted
-
The node to be deleted has two child nodes
This is a complicated case, so we introduce the concept of a successor node.
Successor node: If the output of a binary tree is traversed in middle order, the next node of any node is the successor node of that node.
-
The successor node is the right node of the node to be deleted
Replace the node to be deleted with the successor node. Pay attention to the left and right of the deleted node
-
-
The successor node is the left child of the right child of the node to be deleted
This is a complicated situation, as you can see from the GIFs
Binary search tree code implementation
package com.xgc.tree.binarysearchtree;
import java.util.LinkedList;
import java.util.Queue;
/** * binary search tree *@author xgc
*
*/
public class BinarySearchTree {
/** * binary search tree node *@author xgc
*
*/
private class Node {
int data; / / data domain
Node right; / / right subtree
Node left; / / the left subtree
public Node(int data) {
this.data = data;
}
public Node(a) {}}// The root of the tree
private Node root;
/** * Find the corresponding node * in the binary search tree based on the specified value@param data
* @return* /
public Node find(int data) {
Node current = root;
while(current.data ! = data) {if (data > current.data) {
current = current.right;
}
if (data < current.data) {
current = current.left;
}
if (current == null) {
return null; }}return current;
}
/** * binary search tree insertion *@param data
*/
public void insert(int data) {
// The node to insert
Node p = new Node(data);
if (root == null) {
root = p;
} else {
Node parent = new Node();
Node current = root;
while(true) {
parent = current;
if (data>current.data) {
current = current.right;
if (current==null) {
parent.right = p;
return; }}else if(data == current.data) {
return;
} else {
current = current.left;
if (current==null) {
parent.left = p;
return;
}
}
}
}
}
/** * Delete the specified data *@param data
* @returnCheck whether the deletion succeeded */
public boolean delete(int data) {
Node current = root;
Node parent = new Node();
boolean isRightChild = true;
// Find the node to delete
while(current.data ! = data) { parent = current;if (data > current.data) {
current = current.right;
isRightChild = true;
} else {
current = current.left;
isRightChild = false; }}// The node to be deleted is a leaf
if (current.right == null && current.left == null) {
if (current == root) {
root = null;
} else {
if (isRightChild) {
parent.right = null;
} else {
parent.left = null; }}return true;
}
// The node to be deleted has only one child
else if(current.left == null) {
if (current == root) {
root = current.right;
}else if(isRightChild) {
parent.right = current.right;
}else {
parent.left = current.right;
}
return true;
}
else if(current.right == null) {
if (current == root) {
root = current.left;
}else if(isRightChild) {
parent.right = current.left;
}else {
parent.left = current.left;
}
return true;
}
// The node to be deleted has two children
else {
Node successor = getSuccessor(current);
if (current == root) {
root = successor;
} else if (isRightChild) {
parent.right = successor;
} else {
parent.left =successor;
}
successor.left = current.left;
return true; }}/** * get the descendant of the given node * not only get the descendant of the node, but also adjust the right subtree structure of the deleted node *@param current
* @returnThe next node */
private Node getSuccessor(Node node) {
Node successorParent = node;
Node successor = node;
Node current = node.right;
while(current! =null) {
successorParent = successor;
successor = current;
current = current.left;
}
// The successor node is already found
// If the successor is the left child of the right node of the node to be deleted, adjust the right subtree of the node to be deleted
if(successor ! = node.right) { successorParent.left = successor.right; successor.right = node.right; }return successor;
}
public void levelOrderTree(a) {
if (root == null) return;
Queue<Node> nodes = new LinkedList<>();
nodes.add(root);
while(! nodes.isEmpty()) { Node node = nodes.poll(); System.out.print(node.data +"");
if(node.left ! =null) {
nodes.add(node.left);
}
if(node.right ! =null) { nodes.add(node.right); }}}public void show(Node node) { System.out.println(node.data); }}Copy the codetest
package com.xgc.tree.binarysearchtree;
public class BinarySearchTreeTest {
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(5);
tree.insert(6);
tree.insert(7);
tree.insert(3);
tree.insert(4);
tree.insert(7);
tree.levelOrderTree();
tree.delete(3);
System.out.println();
tree.levelOrderTree();
System.out.println();
tree.show(tree.find(7)); }}Copy the codeThe execution result is as follows:
5 3 6 4 7
5 4 6 7
7
Copy the code