1.1 Basic Concepts
Binary tree: A binary tree is a tree with a degree of 2 or less (at most two children per node)
1. A binary tree that is called full (2^n-1) if the number of nodes at each level reaches its maximum value.
Complete binary tree: leaf nodes can only appear in the lowest and lower layers, and the nodes of the lowest layer are concentrated in several positions on the left of the layer. That is, if the tree is not satisfied, the left and right are required to be full
1.2 Creation of binary search tree
1.2.1 Properties of binary trees
Node class
class Node {
/ / store the key
private Key key;
/ / store the value
private Value value;
// Left child node
private Node left;
// Right child node
private Node right;
public Node(Key key, Value value, Node left, Node right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right; }}Copy the codeProperties of a binary tree
public class BinaryTree<Key extends Comparable<Key>, Value> {
// Number of elements
private int size;
/ / the root node
private Node root;
}
Copy the code1.2.2 insert
Public void PUT (K key,V value) Inserts a key-value pair into the tree. Private Node PUT (Node,K key,V value) Inserts a key-value pair into the specified Node in the tree
// Insert a key-value pair into the tree
public void put(Key key, Value value) {
root = put(root, key, value);
}
// Add a key pair to the specified tree x and return the new tree
private Node put(Node node, Key key, Value value) {
// If there is no node in the current tree, the new node is returned
if (node == null) {
// Number of nodes +1
size++;
return new Node(key, value, null.null);
}
int cmp = key.compareTo(node.key);
if (cmp > 0) {
// If the key of the new node is greater than the key of the current node, continue to find the right child of the current node
node.right = put(node.right, key, value);
} else if (cmp < 0) {
// If the key of the new node is smaller than the key of the current node, continue to find the left child of the current node
node.left = put(node.left, key, value);
} else {
// If the key of the new node is equal to the key of the current node, the tree already has such a node
node.value = value;
}
return node;
}
Copy the code1.2.3 access
Public Value get(Key Key) // Find the corresponding Value in the tree according to the Key
Private Value get(Node Node, Key Key // Find the Value of the Key in the specified tree X
// Find the corresponding value from the tree according to the key
public Value get(Key key) {
return get(root, key);
}
// Select key from the specified tree x
private Value get(Node node, Key key) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp > 0) {
// If the key of the new node is greater than the key of the current node, continue to find the right child of the current node
return get(node.right, key);
} else if (cmp < 0) {
// If the key of the new node is smaller than the key of the current node, continue to find the left child of the current node
return get(node.left, key);
} else {
// If the key of the new node is equal to the key of the current node, it is returned directly
returnnode.value; }}Copy the code1. Remove
Public void delete(K key) Deletes key-value pairs based on the key. Private Node delete(Node x,K key) Deletes key-value pairs based on the key at a specified Node in the tree
// Delete the corresponding key-value pairs in the tree according to the key
public void delete(Key key) {
root = delete(root, key);
}
// Delete the key pair on the specified tree x and return the new tree
private Node delete(Node node, Key key) {
if (node == null) {
return null;
}
// Find the deleted node
int cmp = key.compareTo(node.key);
if (cmp > 0) {
// The new node's key is greater than the current node's key
node.right = delete(node.right, key);
} else if (cmp < 0) {
// The new node's key is greater than the current node's key
node.left = delete(node.left, key);
} else {
If the right subtree of the current node does not exist, return the left child of the current node directly
if (node.right == null) {
return node.left;
}
If the left subtree of the current node does not exist, return the right child of the current node directly
if (node.left == null) {
return node.right;
}
//3. Both the left and right subtrees of the current node exist
Find the smallest node in the right subtree
Node minNode = node.right;
while(minNode.left ! =null) {
minNode = minNode.left;
}
Delete the smallest node in the right subtree
Node delNode = node.right;
while(delNode.left ! =null) {
if (delNode.left.left == null) {
delNode.left = null;
break;
}
delNode = delNode.left;
}
Let the left subtree of the deleted node be called the left subtree of the minNode.
// Let the right subtree of the deleted node be called the right subtree of the minNode
minNode.left = node.left;
minNode.right = node.right;
//3.4. Make the parent of the node to be deleted point to minNode
node = minNode;
//4
size--;
}
return node;
}
Copy the code1.2.5 get the size
Public int size() Gets the number of elements in the tree
public int size(a) {
return size;
}
Copy the code1.2.6 Find the smallest key in the binary tree
// Find the smallest key in the tree
public Key min(a) {
return min(root).key;
}
// Find the node with the smallest key in the specified tree x
private Node min(Node x) {
if(x.left ! =null) {
return min(x.left);
} else {
returnx; }}Copy the code1.2.7Find the largest key in the binary tree
// Find the largest key in the entire tree
public Key max(a) {
return max(root).key;
}
// find the node with the largest key in the specified tree x
private Node max(Node x) {
if(x.right ! =null) {
return max(x.right);
} else {
returnx; }}Copy the code1.3 Basic traversal of binary tree
1.3.1 Preorder traversal
Binary tree traversal: traverses the root node first, then the left subtree, and finally the right subtree
// preorder traversal
public Queue<Key> pre(a) {
Queue<Key> keys = new LinkedList<>();
pre(root, keys);
return keys;
}
private void pre(Node node, Queue<Key> keys) {
if (node == null) {
return;
}
keys.add(node.key);
if(node.left ! =null) {
pre(node.left, keys);
}
if(node.right ! =null) { pre(node.right, keys); }}Copy the code1.3.2 Order traversal
Sequential traversal in binary trees: traverses the left subtree first, then the root node, and finally the right subtree
// middle order traversal
public Queue<Key> mid(a) {
Queue<Key> keys = new LinkedList<>();
mid(root, keys);
return keys;
}
private void mid(Node node, Queue<Key> keys) {
if (node == null) {
return;
}
if(node.left ! =null) {
mid(node.left, keys);
}
keys.add(node.key);
if(node.right ! =null) { mid(node.right, keys); }}Copy the code1.3.3 Post-order traversal
Back-order binary tree traversal: traverses the left subtree first, then the right subtree, and finally the root node
// after the sequence traversal
public Queue<Key> after(a) {
Queue<Key> keys = new LinkedList<>();
after(root, keys);
return keys;
}
private void after(Node node, Queue<Key> keys) {
if (node == null) {
return;
}
if(node.left ! =null) {
after(node.left, keys);
}
if(node.right ! =null) {
after(node.right, keys);
}
keys.add(node.key);
}
Copy the code1.4 Sequence traversal of binary tree
// sequence traversal
//1. Create a queue to store nodes of each layer;
//2. Use a loop to pop a node from the queue:
// 2.1 Get the key of the current node;
If the left child of the current node is not empty, the left child is queued
If the right child of the current node is not null, the right child is queued
public Queue<Key> layer(a) {
Queue<Key> keys = new LinkedList<>();
Queue<Node> nodes = new LinkedList();
nodes.offer(root);
while(! nodes.isEmpty()) { Node node = nodes.poll(); keys.add(node.key);if(node.right ! =null) {
nodes.offer(node.right);
}
if(node.left ! =null) { nodes.offer(node.left); }}return keys;
}
Copy the code1.5 The maximum depth of binary trees
// Maximum depth
public int maxDepth(a) {
return maxDepth(root);
}
//1. If the root is empty, the maximum depth is 0;
//2. Calculate the maximum depth of the left subtree;
//3. Calculate the maximum depth of the right subtree;
//4. Maximum depth of the current tree = the greater of the maximum depth of the left subtree and the maximum depth of the right subtree +1
private int maxDepth(Node node) {
if (node == null) {
return 0;
}
int leftDepth = 0;
if(node.left ! =null) {
leftDepth = maxDepth(node.left);
}
int rightDepth = 0;
if(node.right ! =null) {
rightDepth = maxDepth(node.right);
}
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
Copy the code