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:

1. or empty
2. 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:

1. There is no node with degree greater than 2 in a binary tree
2. 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

1. 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.
2. 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

1. 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.

2. 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.

3. 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)

4. The depth k of a complete binary tree with n nodes is rounded up

5. 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:

1. 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 199

   Answer: The node with degree 0 n0 = n2+1, n0 = 199+1=200, choose B

2. In a complete binary tree with 2n nodes, the number of leaf nodes is ( )
   A n
   B n+1
   C n-1
   D n/2

   Answer: 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

3. A complete binary tree with 767 nodes, the number of leaf nodes is ()

   A 383
   B 384
   C 385
   D 386

   Answer: 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

4. A complete binary tree has 531 nodes, then the height of the tree is ( )
   A 11
   B 10
   C 8
   D 12

   Answer: 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.

1. 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:

1. 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

2. 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: H

   Answer: The root node of the preorder traversal is the first node E.

3. 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: abcde

   Answer: 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.

4. 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: ABCDEF

   Answer: 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

1. 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;
   }
   

2. 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);
   }
   

3. 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);
   }
   

4. 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
}

1. 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;
   }
   

2. 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;
}