Binary trees are important
Tree is the most important in data structure, especially with all kinds of binary tree as the difficult to learn. In terms of interviews alone, there are more than 300 questions related to binary trees in LeetCode. At the same time, the binary tree also plays a connecting role in the whole algorithm plate: not only the extension of arrays and lists, but also as the basis of graphs.
For example, let’s say our classic algorithms quicksort and merge sort, what do you know about these two algorithms? If you tell me that quicksort is a preordered traversal of a binary tree, and merge sort is a preordered traversal of a binary tree, then I know you’re an algorithmic master.
Some of the concepts
node
Node is the foundation of data structure and the basic constituent unit of complex data structure
The tree
A Tree is a finite set of n (n>=0) nodes. When n=0, it’s called an empty tree. In any non-empty tree:
- There is one and only one specific node called Root;
- When n>1, the remaining nodes can be divided into m(m>0) non-intersecting finite sets T1, T2,…… Tn, where each set is itself a tree and is called a subtree of the root.
In addition, the definition of a tree needs to emphasize the following two points:
- When n>0, the root node is unique, there can be no more than one root node, and the tree in the data structure can only have one root node.
- If m is greater than 0, there’s no limit to the number of subtrees, but they must never intersect.
An ordinary tree
The degree of node
The number of subtrees a node has is called its degree.
Node level
The definition starts with the root, the first layer, the children of the root, the second layer, and so on
Binary tree
define
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 roots, respectively.
Binary tree features
- 1) Every node has at most two subtrees, so there is no node whose degree is greater than 2 in a binary tree.
- 2) The left subtree and the right subtree are in order, and the order cannot be reversed arbitrarily.
- 3) Even if a node in the tree has only one subtree, it should be distinguished whether it is a left subtree or a right subtree.
Inclined 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.
Binary search tree
A binary search tree is also called a binary sorting tree, so it is also a binary tree. Then a binary tree satisfying the following properties is a binary search tree:
- 1. If the left subtree is not empty, the values of left and right nodes in the left subtree are less than the value of the root node
- 2. If the right subtree is not empty, then all the nodes in the right subtree have values greater than the root node
- 3. Its left and right subtrees should also be binary search trees
Balanced binary tree
Balanced binarytrees are also called AVL trees. It has the following properties: it is an empty tree or the absolute value of the height difference between its left and right subtrees is not more than 1, and both the left and right subtrees are a balanced binary tree.
Full 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. Full binary tree features are:
- 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
From the root down, all but the lowest level is full (with two children), and all the leaves in the lowest level are filled to the left. To construct a complete binary tree is to place nodes from top to bottom and left to right.
The difference between full and complete binary trees
- The left side is a full binomial tree but not a complete binomial tree. To complete it, you can add two child nodes under the leftmost node of the second layer, or delete the two nodes at the current bottom layer.
- The right side is a complete binomial tree but not full binomial tree, because the last node in the bottom layer has no brothers, that is, the parent node has only one child node, if not, then add a right child node [full binomial tree nodes either have no children, to have must be two].
Binary tree storage structure (serialization)
Sequential storage
The sequential storage structure of a binary tree is to use a one-dimensional array to store the nodes in the binary tree, and the storage location of the nodes is the subindex of the array.
When the binary tree is a complete binary tree, the nodes just fill the array. So when the binary tree is not a complete binary tree, how about sequential storage? The light colors below are empty
Binary list
Since sequential storage cannot meet the storage requirements of binary trees, chained storage is considered. According to the definition of binary tree, each node of binary tree has at most two children. Therefore, the node data structure can be defined as a data and two pointer fields. The representation mode is shown in the figure:
Binary tree traversal
Binomial tree traversal refers to starting from the root node of the binomial tree and visiting all the nodes in the binomial tree in some order, so that each node is accessed once and only once. The access order of binary tree can be divided into four kinds:
- The former sequence traversal
- In the sequence traversal
- After the sequence traversal
- Sequence traversal
Preorder traversal: root-left-right
In order traversal: left-root-right
Post-order traversal: left-right-root
Sequence traversal: start from the root node, and then visit the left and right children, and then start from the left and right children, and then their children, until the node access is completed
code
Iterate through the template recursively
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int v){ value =v; }}// Iterate over the template
public static void f(Node head){
if (head == null) {return;
}
/ / 1
f(head.left);
/ / 2
f(head.right);
/ / 3
}
Copy the codeRecursive preorder traversal
// * * * * * * *
public static void pre(Node head){
if (head == null) {return;
}
System.out.println(head.value);
pre(head.left);
pre(head.right);
}
Copy the codeRecursion in order traversal
// * * * * * * *
public static void pre(Node head){
if (head == null) {return;
}
System.out.println(head.value);
pre(head.left);
pre(head.right);
}
Copy the codeRecursion followed by sequential traversal
// Traverse the left -- right -- root
public static void pos(Node head){
if (head == null) {return;
}
pos(head.left);
pos(head.right);
System.out.println(head.value);
}
Copy the codeNonrecursive preorder traversal
// * * * * * * *
public static void unRecursivePre(Node head){
if(head! =null){
Stack<Node> stack = new Stack<>();
stack.add(head);
while(! stack.isEmpty()){ head = stack.pop(); System.out.println(head.value);if(head.left! =null){
stack.add(head.left);
}
if(head.right! =null){ stack.add(head.right); }}}}Copy the codeNon-recursion in order traversal
// Preorder traversal left -- root -- right
public static void unRecursiveIn(Node head){
if(head! =null){
Stack<Node> stack = new Stack<>();
stack.add(head);
while(! stack.isEmpty() || head! =null) {if(head! =null){
stack.push(head);
head = head.left;
}else{ head = stack.pop(); System.out.println(head.value); head = head.right; }}}}Copy the codeNon-recursive sequential traversal
// Left -- right -- root
public static void unRecursivePos(Node head){
if(head! =null){
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
s1.push(head);
while(! s1.isEmpty()){ head =s1.pop(); s2.push(head);if(head.left! =null){
s1.push(head.left);
}
if(head.right! =null){ s1.push(head.right); }}while(! s2.isEmpty()){ System.out.println(s2.pop()); }}}Copy the codeLayer traversal
public static void level(Node head){
if (head == null) {return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while(! queue.isEmpty()){ Node cur = queue.poll(); System.out.println(cur.value);if(cur.left! =null){
queue.add(cur.left);
}
if(cur.right! =null){ queue.add(cur.right); }}}Copy the codeSerialization (template method)
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int v){
value =v;
}
}
public static Queue<String> fSerial(Node head){
Queue<String> ans = new LinkedList<>();
fpres(head,ans);
return ans;
}
public static void fpres(Node head,Queue<String> ans){
if (head == null){
ans.add(null);
}else {
/ / 1
ans.add(String.valueOf(head.value));
/ / 2
fpres(head.left,ans);
/ / 3fpres(head.right,ans); }}Copy the codeCalculate the maximum width of the binary tree
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int v) {
value = v;
}
}
public static int maxWidthUseMap(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
// Where is the key
HashMap<Node, Integer> levelMap = new HashMap<>();
levelMap.put(head, 1);
int curLevel = 1;// The layer that is currently being counted
int curLevelNodes = 0; // The width of the current layer.
int max = 0;
while(! queue.isEmpty()) { Node cur = queue.poll(); int curNodeLevel = levelMap.get(cur);if(cur.left ! =null) {
levelMap.put(cur.left, curNodeLevel + 1);
queue.add(cur.left);
}
if(cur.right ! =null) {
levelMap.put(cur.right, curNodeLevel + 1);
queue.add(cur.right);
}
if (curLevelNodes == curLevel) {
curLevelNodes++;
} else {
max = Math.max(max, curLevelNodes);
curLevel++;
curLevelNodes = 1;
}
}
max = Math.max(max, curLevelNodes);
return max;
}
public static int maxWidthNoMap(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
Node curEnd = head;// Who is the rightmost node in the current layer
Node nextEend = null;// Next layer, the rightmost node is who
int max = 0;
int curLevelNodes = 0;// Number of current nodes
while(! queue.isEmpty()) { Node cur = queue.poll();if(cur.right ! =null) {
queue.add(cur.right);
nextEend = cur.left;
}
if(cur.left ! =null) {
queue.add(cur.left);
nextEend = cur.left;
}
curLevelNodes++;
if (cur == curEnd){
max = Math.max(max,curLevelNodes);
curLevelNodes =0; // The current node clears 0curEnd = nextEend; }}return max;
}
Copy the codeBinary tree template code to solve origami problems
The problem
Please put a piece of paper on the table vertically, then fold it in half from the bottom of the paper to the top once, press out the crease and unfold. At this time the crease is concave, that is, the crease raised direction pointing to the back of the strip.
If you fold it twice from the bottom to the top of the strip, press out the crease and then unfold, there are three creases, from top to bottom are the lower crease, the lower crease and the upper crease.
Given an input parameter N, the strip is folded in half continuously from bottom to top N times. Print the directions of all creases from top to bottom.
For example, if N=1, “down” is displayed. If N is 2, down Down Up is displayed
Rule, after more than one, each crease appears in the position of the last crease above a concave crease, a convex crease below. So we don’t need to build the tree, we can solve it recursively (i.e., refer to the binary tree recursive traversal template).
The corresponding tree structure output by layer is: 1 concave 2 concave 2 convex 3 concave 3 convex 3 concave 3 convexCopy the code public static void printAllFolds(int N) {
// Start from the beginning node, I initial value is 1, cut the first head node crease is concave crease
printProcess(1, N, true);
}
// The recursion process reaches a certain node,
// I is the number of layers of the node, N total layers, down == true concave down == false convex
public static void printProcess(int i, int N, boolean down) {
if (i > N) {
return;
}
printProcess(i + 1, N, true);
System.out.println(down ? "Concave" : "Convex");
printProcess(i + 1, N, false);
}
public static void main(String[] args) {
int N = 3;
printAllFolds(N);
}
Copy the codeRecursive set of binary trees
Routine summary
- 1) Assume that the X node is the head, assume that you can ask for any information from the left tree of X and the right tree of X
- 2) Under the assumptions of the previous step, discuss the tree with X as the head node, and the possibility of getting the answer (most important)
- 3) After listing all the possibilities, determine what kind of information you want from the left tree and the right tree
- 4) Take the information of the left tree and the information of the right tree as the complete set, which is the information S that any subtree needs to return
- 5) Every recursive function returns S, every subtree
- 6) Write code, consider how to integrate the information of the left tree and the information of the right tree into the information of the whole tree in the code
Determine whether the binary tree is a search binary tree (using routines)
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data; }}// The available information of the node
public static class Info {
boolean isBST;
public int min;
public int max;
public Info(boolean is, int mi, int ma){ isBST = is; min = mi; max = ma; }}// Start assembling nodes
public static Info process(Node head) {
if (head == null) {
return null;
}
Info leftInfo = process(head.left);
Info rightInfo = process(head.right);
int min = head.value;
int max = head.value;
if(leftInfo ! =null) {
min = Math.min(min, leftInfo.min);
max = Math.max(max, leftInfo.max);
}
if(rightInfo ! =null) {
min = Math.min(min, rightInfo.min);
max = Math.max(max, rightInfo.max);
}
// Set possibilities
boolean isBST = false;
if (
(leftInfo == null ? true : (leftInfo.isBST && leftInfo.max < head.value))
&&
(rightInfo == null ? true : (rightInfo.isBST && rightInfo.min > head.value))
) {
isBST = true;
}
return new Info(isBST, min, max);
}
public static boolean isBST(Node head) {
if (head == null) {
return true;
}
return process(head).isBST;
}
Copy the codeDetermine whether a tree is a balanced binary tree (using the routine solution)
public static boolean isBalanced(Node head) {
return process(head).isBalaced;
}
// Left and right requirements are the same, Info information returned structure
public static class Info {
public boolean isBalaced;
public int height;
public Info(boolean b, int h) {
isBalaced = b;
height = h;
}
}
public static Info process(Node X) {
if (X == null) {
return new Info(true.0);
}
Info leftInfo = process(X.left);
Info rightInfo = process(X.right);
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
boolean isBalanced = true;
// Set the case where it is not
if(! leftInfo.isBalaced || ! rightInfo.isBalaced ||Math.abs(leftInfo.height - rightInfo.height) > 1) {
isBalanced = false;
}
return new Info(isBalanced, height);
}
Copy the codeBinary trees are related to quicksort and merge sort
As I said, quicksort is just a preordered walk through a binary tree, and merge sort is just a preordered walk through a binary tree. Why is quicksort and merge sort relevant to binary trees? Let’s briefly analyze their algorithmic ideas and code framework:
Fast row
If nums[lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] [lo..hi] The array is sorted by recursively searching for a new cut-off point between nums[lo..p-1] and nums[p+1..hi].
The code framework for quicksort is as follows:
Void sort(int[] nums, int lo, int hi) {/****** sort the position ******/ // p int p = partition(nums, lo, hi); /************************/ sort(nums, lo, p - 1); sort(nums, p + 1, hi); }Copy the codeFirst we construct the demarcation point, and then we go to the left and right subarrays to construct the demarcation point.
Merge sort
Merge sort of logic, if want to nums lo.. hi sorted, we start to nums lo.. mid sorting, again to nums] [mid + 1.. hi sorting, finally combine the two and orderly subarray, the array is sorted.
The code framework for merge sort is as follows:
void sort(int[] nums, int lo, int hi) { int mid = (lo + hi) / 2; sort(nums, lo, mid); sort(nums, mid + 1, hi); / * * * * * * after sequence traversal location * * * * * * / / / merging two sorted subarray merge (nums, lo, mid, hi); / * * * * * * * * * * * * * * * * * * * * * * * * /}Copy the codeFirst sort the left and right subarrays, and then merge (similar to the logic of merging ordered lists), do you see this is a binary tree after order traversal framework?
Greedy algorithm
Greedy algorithm, also known as greedy method, is to find the optimal solution of problem of commonly used method, this method solving process can be divided into several steps, but each step application greedy principle, selecting the best/optimal condition choose the most favorable choice (local), and pile up the hope that the final result is the best/optimal solution. The main understanding is as follows:
- 1) The most naturally intelligent algorithm
- 2) Always make the best choice at the moment, using a locally most utilitarian criterion
- 3) The difficulty is to prove that the locally most utilitarian standard can obtain the globally optimal solution
- 4) The learning of greedy algorithm is mainly to increase experience and experience
Greedy algorithms and heaps
The heap is a very flexible data structure that can be used on its own to solve many interesting problems. Also, because the definition of a heap is optimal, it has a natural connection to greedy algorithms.
The data structure of heap is a complete binary tree.
The basic steps of the greedy method:
- Step 1: Start with some initial solution;
- Step 2: Adopt the iterative process. When it is possible to make further progress toward the goal, a part of the solution is obtained according to the local optimal strategy and the size of the problem is reduced.
- Step 3: Put all the solutions together.
Application Scenario (Cutting gold Bars)
It takes the same amount of copper to cut a gold bar in half. For example, a gold bar of length 20, no matter how you cut it, costs 20 coppers. A group of people want to divide the whole piece of gold bar, how to divide the most copper?
For example, given an array {10,20,30}, representing three people, the bar is 60 in length, and the bars are divided into 10,20,30 parts.
If you split the 60 bars into 10 and 50 first, it costs 60; If you divide the 50 bars into 20 and 30, it costs 50; The total cost is 110 coppers. But if you split the 60 bars into 30 and 30, it costs 60; Divide the length of 30 bars into 10 and 20, and it costs 30; The total cost is 90 coppers. Enter an array and return the minimum cost of partitioning.
public static int lessMoney(int[] arr) {
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
pQ.add(arr[i]);
}
int sum = 0;
int cur = 0;
while (pQ.size() > 1) {
cur = pQ.poll() + pQ.poll();
sum += cur;
pQ.add(cur);
}
return sum;
}
Copy the codePs: Part of the picture from the network, invaded delete!