This is the fifth day of my participation in the August More text Challenge. For details, see:August is more challenging
The tree
A tree is a data structure that consists of a set of n(n≥1) finite nodes with a hierarchical relationship. It's called a tree because it looks like an upside-down tree, meaning it has roots up and leaves downCopy the codestructure
1. Node: it is the foundation of data structure and the basic constituent unit of complex data structure.
2. Tree: a finite set of n (n>=0) nodes. When n=0, it’s called an empty tree. In any non-empty tree:
1) There is only one specific node called Root; 2) When n>1, the remaining nodes can be divided into m(m>0) non-intersecting finite sets T1, T2 and…… Tn, where each set is itself a tree and is called a subtree of the root.
In addition, the definition of tree also needs to emphasize the following two points: 1) when n>0, the root node is unique, there cannot be more than one root node, and the tree in the data structure can only have one root node. 2) When m>0, there is no limit to the number of subtrees, but they must not intersect each other.
3. Degree of node: The number of subtrees a node has is called degree of node.
4. Node relationship: The root node of the node idea tree is the child node of the node. The phase should be called the parent of the child. Children of the same parent node are called brothers.
5. Node hierarchy: Starting from the root, the root is the first layer, the children of the root are the second layer, and so on.
6. Tree depth: The maximum number of nodes in a tree is called the depth or height of the tree
7. Balance factor: the depth of the left subtree down this node – the depth of the right subtree = balance factor
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 roots, respectively.Copy the codeThe characteristics of
- Every node has at most two subtrees, so there is no node greater than two in a binary tree.
- The left subtree and the right subtree are ordered, and the order cannot be reversed arbitrarily.
- Even if a node in the tree has only one subtree, you have to distinguish whether it’s a left subtree or a right subtree.
The nature of the
- There are at most 2^(I -1) nodes on the ith level of a binary tree. (I > = 1)
- In a binary tree, if the depth is k, there are at most 2 to the k minus 1 nodes. (k > = 1)
- N0 =n2+1 N0 indicates the number of nodes with degree 0, and n2 indicates the number of nodes with degree 2.
- In a complete binary tree, a complete binary tree with n nodes has a depth of [log2n]+1, where [log2n] is rounded down.
- If a complete binary tree with N nodes is numbered from 1 to N from top to bottom and from left to right, any node numbered I in the complete binary tree has the following characteristics:
1) If I =1, the node is the root of the binary tree and has no parents; otherwise, the node numbered [I /2] is its parent; 2) If 2i>n, the node has no left child; otherwise, the node numbered 2i is its left child; 3) If 2i+1>n, the node has no right child; otherwise, the node numbered 2I +1 is its right child.Copy the codeInclined tree
A binary tree in which all nodes have only left subtrees is called a left-slant tree. A binary tree in which all nodes have only a right subtree is called a right slant tree. These two are collectively called oblique trees.
Storage structure
Sequential storage structure
We use a one-dimensional array to store the nodes in the binary tree, and the location of the nodes is the index of the array.
When the binary tree is a complete binary tree, the nodes just fill the array
When the binary tree is not a complete binary tree, the light colored node means that the node does not exist
The array representation is as follows: ∧ indicates that there is no storage node at this location in the array. There is already a waste of space in the sequential storage structure.
Binary list
Adopt chain storage. The node data structure is defined as a data and two pointer fields
Binary tree traversal
Refers to starting from the root of the binary tree, in some order to access all nodes in the binary tree, so that each node is accessed once, and only once
Binary tree is a recursively defined structure, so the recursively traversed binary tree code is very simple.
The access order of binary tree can be divided into four kinds: pre-order traversal, middle-order traversal, post-order traversal, and sequential traversal
Sequence of sequence and sequence of sequence traversal, determine a binary tree.
After sequence traversal sequence and sequence traversal sequence, determine a binary tree.
Given the preordered traversal sequence and the postordered traversal sequence, a binary tree cannot be uniquely identified.
So let’s initialize the tree, so we need to iterate
public class TreeNode<T> {
private T data; // Node data
private int level; / / hierarchy
private TreeNode<T> left; / / the left subtree
private TreeNode<T> right; / / right subtree
public TreeNode(T data, int level) {
this.data = data;
this.level = level; }}public class NewTree<T> {
private TreeNode<T> rootNode; / / the root node
private int depth = 1; / / depth of the tree
private Map<String, Integer> map; // This is used for counting
public static void main(String[] args) {
NewTree<Integer> tree = new NewTree<Integer>();
tree.rootNode = new TreeNode<Integer>(7.1);
tree.add(tree.rootNode, 4);
tree.add(tree.rootNode, 9);
tree.add(tree.rootNode, 2);
tree.add(tree.rootNode, 6);
tree.add(tree.rootNode, 8);
tree.add(tree.rootNode, 10);
tree.add(tree.rootNode, 1);
tree.add(tree.rootNode, 3);
tree.add(tree.rootNode, 5);
System.out.println("Initializing the list successfully!");
}
public void add(TreeNode<Integer> treeNode, int x) {
int data = treeNode.getData();
int level = treeNode.getLevel() + 1;
if (x >= data) {
if(treeNode.getRight() ! =null) {
this.add(treeNode.getRight(), x);
} else {
treeNode.setRight(new TreeNode<Integer>(x, level));
this.depth = level > this.depth ? level : this.depth; }}if (x < data) {
if(treeNode.getLeft() ! =null) {
this.add(treeNode.getLeft(), x);
} else {
treeNode.setLeft(new TreeNode<Integer>(x, level));
this.depth = level > this.depth ? level : this.depth; }}}}Copy the codeThe former sequence traversal
Starting from the root node of the binary tree, the node data is output when it first reaches the node, which is accessed in the direction of first left and then right.
Note: Starting from the root node, node 7 is reached for the first time, so output 7; Continue to access the left, the first time to access node 4, so output 4;
7 4 2 1 3 6 5 9 8 10
// Print result: 7 4 2 1 3 6 5 9 8 10
public void prologue(TreeNode<Integer> node) { / / before order
Integer x = node.getData();
if (map.get(x) == null) {
map.put(x, 1);
System.out.print(x + "");
}
if(node.getLeft() ! =null) {
this.prologue(node.getLeft());
}
if(node.getRight() ! =null) {
this.prologue(node.getRight()); }}Copy the codeIn the sequence traversal
Starting from the root node of the binary tree, when the second time to reach the node, the node data output, according to the first left and right direction access.
Note: Starting from the root node, when node 7 is reached for the first time, 7 is not output, and then the left access is continued. When node 4 is accessed for the first time, 4 is not output. Go on to 2,1; When the left subtree is empty, it returns to 1. At this time, it accesses 1 for the second time, so it outputs 1.
1 2 3 4 5 6 7 8 9 10
// Print result: 1 2 3 4 5 6 7 8 9 10
public void middleOrder(TreeNode<Integer> node) { / / in the sequence
Integer x = node.getData();
Integer size = map.get(x);
if (size == null) {
map.put(x, 1);
if(node.getLeft() ! =null) {
this.middleOrder(node.getLeft());
}
map.put(x, 2);
System.out.print(x + "");
if(node.getRight() ! =null) {
this.middleOrder(node.getRight()); }}}Copy the codeAfter the sequence traversal
Starting from the root node of the binary tree, when the third time to reach the node, the node data output, according to the first left and right direction access.
Note: Starting from the root node, when node 7 is reached for the first time, 7 is not output, and then the left access is continued. When node 4 is accessed for the first time, 4 is not output. Go on to 2,1; At 1, the left subtree of 1 is empty, then it returns to 1. At this time, it accesses 1 for the second time, and does not output 1. If the right subtree of 1 is empty, it returns to 1. At this time, it reaches 1 for the third time, so it outputs 1.
1 3 2 5 6 4 8 10 9 7
// Final result: 1 3 2 5 6 4 8 10 9 7
public void postSequence(TreeNode<Integer> node) { / / after order
Integer x = node.getData();
Integer size = map.get(x);
if (size == null) {
map.put(x, 1);
if(node.getLeft() ! =null) {
this.postSequence(node.getLeft());
}
map.put(x, 2);
if(node.getRight() ! =null) {
this.postSequence(node.getRight());
}
map.put(x, 3);
System.out.print(x + ""); }}Copy the codeLevel traversal
Traverse the binary tree from left to right according to the tree hierarchy from top to bottom
As shown in the figure above, visit as follows: 7 4 9 2 6 8 10 1 3 5
// Final result: 7 4 9 2 6 8 10 1 3 5
public void level(NewTree<Integer> tree) { / / hierarchy
tree.order(tree.rootNode);
for (int i = 1; i <= tree.depth ; i++) {
List<Integer> list = tree.levelMap.get(i);
list.stream().forEach(x -> System.out.print(x + "")); }}public void order(TreeNode<Integer> node) {
Integer x = node.getData();
int level = node.getLevel();
List<Integer> list = this.levelMap.get(level);
if (list == null) {
list = new ArrayList<Integer>();
}
list.add(x);
this.levelMap.put(level, list);
if(node.getLeft() ! =null) {
this.order(node.getLeft());
}
if(node.getRight() ! =null) {
this.order(node.getRight()); }}Copy the codeBinary tree classification
Full binary Tree, full binary Tree, binary search Tree, balanced binary Tree, red-black Tree, B+Tree, B-tree...Copy the codeFull binary tree
In a binary tree. If all branch nodes have left and right subtrees, and all leaves are on the same level, such a binary tree is called a full binary tree.
The characteristics of
1. Leaves can only appear at the bottom layer. It is impossible to achieve balance in other layers.
2. The degree of non-leaf nodes must be 2.
3. In the binary tree with the same depth, the full binary tree has the most nodes and leaves.
Perfect binary tree
A binary tree with n nodes is numbered by layer. If the node numbered I (1<= I <=n) is in exactly the same position as the node numbered I in a full binary tree with the same depth, then the binary tree is called a complete binary tree.
The characteristics of
1. Leaf nodes can only appear at the lowest level and the second level.
2. The lowest leaves are clustered on the left side of the tree.
3. If there is a leaf node in the penultimate layer, it must be in a continuous position on the right.
4. If the node degree is 1, then the node has only left child, that is, no right subtree.
5, the same number of nodes of binary tree, complete binary tree depth is the least.
Note: Full binomial trees must be complete binomial trees, but the reverse may not be true.
Binary search tree
And: binary search tree, binary sort tree; Or an empty tree
The characteristics of
1. The value of the left node in all subtrees is smaller than the root node, and the value of the right node is larger than the root node
2. The left and right subtrees of any node are also binary search trees
3, through the order traversal, will get an ordered sequence
The optimal time complexity for its operation is O(log2n), which is equivalent to binary search for the sequence. The worst time complexity is O(n), which corresponds to a linear search.
Balanced binary tree
Also known as AVL trees (as distinct from AVL algorithms);
1, is the binary search tree optimal case;
2, it is a good solution to binary search tree degradation into a linked list, the insertion, search, delete time complexity of the best case and the worst case are maintained at O(logN).
3, but the frequent rotation will make the insertion and deletion sacrifice O(logN) time, but compared to the binary search tree, the time is much more stable.
The characteristics of
1. It is a binary search tree
2. The absolute value of the height difference between the left and right subtrees is no more than 1, and both of the left and right subtrees are a balanced binary tree
3. When deleting, adding, or modifying a value on a node, it balances the binary tree by turning left or right.
4. The worst time complexity is O(log2n).
Adjustment measures: single/double rotation
Insertion of nodes in a balanced search tree may break the balance of the whole tree. In order to ensure that the balance is not destroyed, some nodes should be rotated according to the balance factor, so as to reduce the height of the tree, so as to ensure the balance of the tree.
The balance factor calculation is described in: Tree - structureCopy the codeThe single spiral
1, left left situation
The balance factor of the root node is 2, and the left child node of the root node is 0 or 1. Then, nodes close to the root node with a balance factor of 1 should be set as root nodes for right-handed balance adjustment
1, right right situation
The balance factor of the root node is -2, and the right child node of the root node is 0 or -1. Then, nodes close to the root node whose balance factor is -1 need to be set as root nodes to adjust balance by left-handed rotation
Twin twist
1. Around situation (LR)
The balance factor of the root node is 2, and that of the left child node is -1.
Then it is necessary to adjust the balance of the left child node whose balance factor is -1 by left-handed rotation, and then to adjust the balance of the root node by right-rotation
2. Right and left
The balance factor of the root node is -2, and that of the right child node is 1.
Then, the right child node whose balance factor is 1 needs to be right-rotated to adjust the balance, and then the root node needs to be left-rotated
Red and black tree
A special binary search tree
The characteristics of
1. Each node is either red or black;
2, the root node is always black;
3. All leaf nodes are black (note that leaf nodes are actually NIL nodes in the figure above);
4. Two children of every red node must be black;
5. The path from any node to each leaf node in its subtree contains the same number of black nodes; Rotate to ensure that no path is twice as long as the others. Thus, a red-black tree is a binary tree that is relatively close to equilibrium.