1. The basic concept of tree
Note: In a tree structure, there can be no intersection between subtrees, otherwise it will not be a tree structure.
Subtrees are disjoint.
Except for the root node, each node has one and only one parent node.
A tree of N nodes has N-1 edges.
- The degree of a node: the number of subtrees in a node is called the degree of the node; as shown in the figure above: the degree of A is 6, and the degree of B is 0
- The degree of the tree: in a tree, the maximum value of the degree of all nodes is called the degree of the tree; as shown above: the degree of the tree is 6
- Leaf node or terminal node: a node with a degree of 0 is called a leaf node; as shown in the figure above: B, C, H, I... and other nodes are leaf nodes
- Parent node or parent node: If a node contains a child node, the node is called the parent node of its child node; as shown above: A is the parent node of B
- Child node or child node: The root node of the subtree contained in a node is called the child node of the node; as shown above: B is the child node of A
- Root node: a node in a tree that has no parent node; as shown above: A
- The level of the node: starting from the root definition, the root is the first level, the child nodes of the root are the second level, and so on
- The height or depth of the tree: the maximum level of nodes in the tree; as shown above: the height of the tree is 4
You only need to understand the following concepts of trees, and you only need to know what they mean when you read the book:
- Non-terminal nodes or branch nodes: nodes whose degree is not 0; as shown above: D, E, F, G... and other nodes are branch nodes
- Brother nodes: nodes with the same parent node are called sibling nodes; as shown above: B and C are sibling nodes
- Cousin node: nodes whose parents are on the same layer are cousins of each other; as shown in the figure above: H and I are sibling nodes of each other
- Ancestor of a node: all nodes on the branch from the root to the node; as shown above: A is the ancestor of all nodes
- Descendants: Any node in the subtree rooted at a node is called the descendant of the node. As shown above: all nodes are descendants of A
- Forest: A collection of m(m>=0) disjoint trees is called a forest.
2. Binary tree
2.1 Concept
A binary tree is a finite set of nodes that:
- or empty
- Or it consists of a root node plus two binary trees called left subtree and right subtree.
As can be seen from the above figure:
- There is no node with degree greater than 2 in a binary tree
- The subtree of a binary tree is divided into left and right, and the order cannot be reversed, so the binary tree is an ordered tree
Note: For any binary tree, it is composed of the following situations:
2.2 Two special binary trees
- Full binary tree: A binary tree, if the number of nodes in each layer reaches the maximum value, the binary tree is a full binary tree. That is, if a binary tree has K levels and the total number of nodes is 2^k -1 , then it is a full binary tree.
- Complete binary tree: A complete binary tree is a highly efficient data structure, and a complete binary tree is derived from a full binary tree. A binary tree of depth K with n nodes is called complete if and only if each node corresponds to a node numbered from 0 to n-1 in a full binary tree of depth K. Binary tree. Note that a full binary tree is a special kind of complete binary tree.
2.3 Properties of Binary Trees
-
If the number of root nodes is specified to be 1, then a non-empty binary tree will have up to 2 ^(i-1) (i>0) nodes on the first level.
-
The maximum number of nodes for a binary tree with a depth of K is 2^k-1 (k>=0), provided that only the root node has a depth of 1.
-
For any binary tree, if the number of leaf nodes is n0 and the number of non-leaf nodes with degree 2 is n2, then n0=n2+1
(Derivation:
1. Assume that any binary tree has N nodes, and because a binary tree is composed of leaf nodes n0, node n1 with degree 1 and node n2 with degree 2, N = n0+n1+n2 (1)
2. For any tree, if there are N nodes, then N-1 edges will be generated
n0: node with degree 0, only 0 edges can be generated downward
n1: A node with degree 1, which can generate n1 edges downward
n2: a node with degree 2, which can generate 2*n1 edges downward
Get: N-1 = 0+n1+2*n2(2)
Expressions (1) and (2) are combined to get n0=n2+1)
-
The depth k of a complete binary tree with n nodes is rounded up
-
For a complete binary tree with n nodes, if all nodes are numbered starting from 0 in order from top to bottom and left to right, then for sequence number i
The nodes are:
If i>0, parental serial number: (i-1)/2; i=0, I is the root node number, no parental node
If 2i+1<n, left child number: 2i+1, otherwise no left child
If 2i+2<n, right child number: 2i+2, otherwise no right child
Exercise questions:
-
A binary tree has a total of 399 nodes, of which 199 are nodes of degree 2, then the number of leaf nodes in the binary tree is ( )
A does not exist such a binary tree
B 200
C 198
D 199Answer: The node with degree 0 n0 = n2+1, n0 = 199+1=200, choose B
-
In a complete binary tree with 2n nodes, the number of leaf nodes is ( )
A n
B n+1
C n-1
D n/2Answer: A node consists of nodes with degree 0, degree 1, and degree 2.
In a complete binary tree, there is an even number of nodes, so there is 1 node with degree 1. 2n= n0+n1+2*n2 = n0+1+n2
And because n0 = n2+1, so n0 = n, choose A
-
A complete binary tree with 767 nodes, the number of leaf nodes is ()
A 383
B 384
C 385
D 386Answer: In a complete binary tree, there are an odd number of nodes, so there are 0 nodes with degree 1. 767=n0+0+n2
And because n0 = n2+1, so n0 = 384, choose B
-
A complete binary tree has 531 nodes, then the height of the tree is ( )
A 11
B 10
C 8
D 12Answer: k = log2(n+1) = log2(532) rounded up, choose B
2.4 Storage of binary tree
The storage structure of binary tree is divided into: sequential storage and linked storage similar to linked list.
The chain storage of the binary tree is referenced through a node, and the common representations include binary and ternary representations.
2.5 Basic operations of binary tree
2.5.1 Traversal of binary tree
The so-called traversal (Traversal) refers to follow a certain search route, and sequentially visit each node in the tree once and only once. The operation performed by accessing a node depends on the specific application problem (eg: printing the node content, adding 1 to the node content). Traversal is one of the most important operations on a binary tree, and it is the basis for other operations on a binary tree.
When traversing a binary tree, if there is no agreement, everyone traverses in their own way, and the result is confusing.
According to certain rules, everyone's traversal results for the same tree must be the same.
-
pre-middle-post-order traversal
If N represents the root node, L represents the left subtree of the root node, and R represents the right subtree of the root node.
Then there are the following traversal methods according to the order of traversing the root node:
NLR: Preorder Traversal - Access Root Node - Left Subtree of Root - Right Subtree of Root.// Pre-order traverse root->left subtree->right subtree public void preOrder(TreeNode root) { if(root == null){ return; } System.out.print(root.val+" "); preOrder(root.left);//recursion preOrder(root.right); } //Sub-problem ideas: (usually use this) public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if(root == null) { //If the root node is empty, return directly return list; } list.add(root.val); //Add left subtree and right subtree List<Integer> leftTree = preorderTraversal(root.left); list.addAll(leftTree); List<Integer> rightTree = preorderTraversal(root.right); list.addAll(rightTree); return list; }
LNR: Inorder Traversal - left subtree of root - > root node - > right subtree of root.
// Traversing left subtree in middle order - > root - > right subtree void inOrder(TreeNode root) { if(root == null) { return; } inOrder(root.left); System.out.print(root.val+" "); inOrder(root.right); }
LRN: Postorder Traversal - Left subtree of root - > Right subtree of root - > Root node.
// Post-order traverse left subtree->right subtree->root void postOrder(TreeNode root) { if(root == null) { return; } postOrder(root.left); postOrder(root.right); System.out.print(root.val+" "); }
Exercise questions:
-
A complete binary tree outputs the sequence in layers (from left to right at the same layer) as ABCDEFGH . The preorder sequence of this complete binary tree is (A)
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA -
The pre-order traversal and in-order traversal of the binary tree are as follows: pre-order traversal: EFHIGJK; in-order traversal: HFIEJKG. Then the root node of the binary tree is (A)
A: E B: F C: G D: HAnswer: The root node of the preorder traversal is the first node E.
-
Assume that the in-order traversal sequence of a binary tree in Lesson 1 is badce, and the post-order traversal sequence is: bdeca, then the pre-order traversal sequence of the binary tree is (D)
A: adbce B: decab C: debac D: abcdeAnswer: The root node of post-order traversal is the last node a. In in-order traversal, the left subtree of a is the left subtree, and the right subtree is the right subtree of a.
-
The post-order traversal sequence of a binary tree is the same as the in-order traversal sequence, both of which are ABCDEF , then the sequence output by level (from left to right at the same level) is (A)
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEFAnswer: The root node of post-order traversal is the last node F, and the left number is the right subtree or left subtree of F.
2.5.2 Basic Operation Exercises of Binary Trees
-
Get the number of nodes in the tree
int count = 0; int size(TreeNode root){ if (root == null){ return 0; } count++; return size(root.left)+size(root.right); } /** * sub-problem ideas */ int size1(TreeNode root){ if (root == null) return 0; //Sum of left subtree and right subtree + root node return size1(root.left)+size1(root.right)+1; }
-
Get the number of leaf nodes - (traversal ideas, sub-problem ideas)
//1. Traversal idea: traverse to the leaf node, let the counter++ int leafCount = 0; public void getLeafNodeCount(TreeNode root){ if(root == null){ return; } //When both the left subtree and the right subtree are null, it is a leaf node if (root.left == null && root.right ==null){ leafCount++; } //Recursive left subtree and right subtree getLeafNodeCount(root.left); getLeafNodeCount(root.right); } //2. Sub-problem idea: the number of leaves in the left leaf + the number of leaves in the right leaf = the leaves of the entire tree int leafCount1 = 0; public int getLeafNodeCount1(TreeNode root) { if (root == null) { return 0; } if (root.left == null &&root.right == null){ //The current root has no subtree, it is a leaf node return 1; } return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right); }
-
Get the number of nodes in the K th layer
- Sub-problem idea: it is the kth layer of the root node, which is the k-1 th layer of the second layer node
public int getKLevelNodeCount(TreeNode root,int k){ if (root == null || k <= 0){ return 0; } if (k == 1){ //When k=1, the first layer return 1; } //When k is not 1: recursion return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1); }
-
Get the height of a binary tree
- Sub-problem idea: the height of the left tree and the height of the right tree take the maximum value and then +1 (root node) = the height of the entire tree
- The time complexity of the following function: O(n) (Look at the number of recursion, each node recurses, the number of times is n)
- Space complexity: O(k) k=log2(n) (space complexity is the height of a number)
int getHeight2(TreeNode root) { if(root == null){ return 0; } int leftHeight = getHeight2(root.left); int rightHeight = getHeight2(root.right); return leftHeight>=rightHeight ? leftHeight+1 : rightHeight+1; } int getHeight(TreeNode root){ if(root == null){ return 0; } //Compare the height of the left tree and the height of the right tree, and take the maximum value int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1; //return getHeight(root.left) > getHeight(root.right)? (getHeight(root.left)+1):(getHeight(root.right)+1); //The number of recursion is too many, and the calculation is repeated many times, err //Exceeding the specified running time: 1. Infinite loop 2. Too many recursions }
-
Check if the element with value value exists
TreeNode find(TreeNode root,char val) { if (root == null) return null; if (root.val == val){ return root; } TreeNode ret = find(root.left,val); if(ret!=null){ return ret; } ret = find(root.right,val); //If the left subtree has no element with value value, look at the right subtree if (ret != null){ return ret; } return null; }
-
Determine if a tree is a complete binary tree
- Idea: Return true if root is empty. If it is not empty, create a queue and put root into the queue.
- When the queue is not empty, the head element of the queue is taken out each time. If the head element is not null, the left subtree and right subtree of the head element are added. If it is null, the loop is terminated.
- After that, when the queue is not empty, check all elements in the queue, if they are all null, it will be true, if there are other elements, it will be false
boolean isCompleteTree(TreeNode root){ if(root == null){ return true; } //queue Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root);//enqueue root //cycle while (!queue.isEmpty()){// queue is not empty TreeNode cur = queue.poll(); //Take the head element of the queue to cur if (cur != null){ //When the extracted queue head is not null, add two elements of its left subtree and right subtree queue.offer(cur.left); queue.offer(cur.right); }else { break; //When null, abort the loop } } //See if the remaining elements of the queue are all null, if there are elements that are not null, then it is not a complete binary tree while(!queue.isEmpty()){ TreeNode top = queue.peek(); if(top != null){ return false; } queue.poll(); } return true; }
r.left);
queue.offer(cur.right);
}else {
break; // when null, abort the loop
}
}
//See if the remaining elements of the queue are all null, if there are elements that are not null, then it is not a complete binary tree
while(!queue.isEmpty()){
TreeNode top = queue.peek();
if(top != null){
return false;
}
queue.poll();
}
return true;
}