Data Structure: Getting Started with Binary Tree Basics_Sum of Left and Right Subtree Weights_Golden Years 5789651’s Blog

class=”markdown_views prism-atom-one-dark”>

Define

A binary tree consists of a root node and two disjoint binary trees called the left and right subtrees of the root node.

Binary tree types

full binary tree

For a binary tree, if each non-leaf node has left and right subtrees, and all leaf nodes in the binary tree are in the same layer, such a binary tree is called a full binary tree.

Complete binary tree

Except for the leaf nodes, each node has left and right sub-leaves and the leaf nodes are at the bottom of the binary tree.

For a complete binary tree, if the number of a certain node is i, the left child node is 2i+1, and the right child node is 2i+2.

Binary search tree

Also known as Binary Search Tree or Binary Sorting Tree. A binary search tree has the following properties:

• If the left subtree is not empty, the values ​​of all nodes on the left subtree are less than the value of its root node
• If the right subtree is not empty, the values ​​of all nodes on the right subtree are greater than or equal to the value of its root node
• The left and right subtrees are also binary sorted trees
• No nodes with equal keys

The time complexity of binary search is O(log N), and the worst case time complexity is O(N)

Balanced binary tree

Also known as AVL tree. It is a binary sorting tree, and has the following properties: it is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, and both left and right subtrees are a balanced binary tree.

Red-black tree

A red-black tree is a tree in which each node is colored. The node color is either red or black. A red-black tree is a search tree. Red-black trees have an important property that the longest path from the root node to the leaf node is no more than twice the length of the shortest path. For red-black tree insertion, deletion and search, the complexity is O(log N).

Huffman tree

Given n weights as the leaf nodes of n, construct a binary tree. If the length of the weighted path reaches the minimum, such a binary tree is called an optimal binary tree, also known as a Huffman tree.

Conclusion

• The i-th layer of the binary tree has at most 2^(i-1) nodes, and the binary tree with a depth of k has at most 2^(k-1) nodes
• Unlike a tree, the number of nodes in a tree is at least 1, while the number of nodes in a binary tree can be 0
• There is no limit to the maximum degree of a node in a tree, but the maximum degree of a binary tree node is 2
• The nodes of the tree are not divided into left and right, while the nodes of the binary tree are divided into left and right

traversal

The traversal of a binary tree can be divided into depth-first traversal and breadth-first traversal. Depth-first traversal can be divided into pre-order traversal, in-order traversal, and post-order traversal. Breadth-first traversal is hierarchical traversal.

Node class TreeNode:

public class TreeNode {
     
     public int value; // node val
     public TreeNode leftChild;// left subtree left
     public TreeNode rightChild;// right subtree right

     public TreeNode(int value) {
     
         super();
         this.value = value;
     }
    
     public int getValue() {
     
 return value;
 }

 public void setValue(int value) {
     
 this.value = value;
 }

 public TreeNode getLeftChild() {
     
 return leftChild;
 }

 public void setLeftChild(TreeNode leftChild) {
     
 this.leftChild = leftChild;
 }

 public TreeNode getRightChild() {
     
 return rightChild;
 }

 public void setRightChild(TreeNode rightChild) {
     
 this.rightChild = rightChild;
 }
 	
 }
 

Generate a complete binary tree:

private int[] treeNodeValue= {
     10,6,14,4,8,12,16};
 private ArrayListTreeNode>   list = new ArrayList();

 public static TreeNode createTree() {
     
 		 
 for (int i = 0; i   treeNodeValue.length; i++) {
     
 TreeNode treeNode = new TreeNode(treeNodeValue[i])  ;
 list.add(treeNode);
 }
 //According to the nature of a complete binary tree, the left subtree of i node is 2*i+1, and the number of words in the right node is 2*i+2
 for (int i = 0; i   list.size() / 2; i  ++) {
     
 TreeNode treeNode = list.get(i);
 //Judge whether the left subtree is out of bounds
 if (i * 2 + 1  list  .size()) {
     
 TreeNode leftTreeNode = list.get(i * 2 +  span> 1);
 treeNode.setLeftChild(leftTreeNode);
 }
 //Judge whether the right subtree is out of bounds
 if (i * 2 + 2  list  .size()) {
     
 TreeNode rightTreeNode = list.get(i * 2 +  span> 2);
 treeNode.setRightChild(rightTreeNode);
 }
 }
 		 
 return list.get(0);
 }
 

Depth-first traversal (DFS)

Traverse the depth of the binary tree as much as possible.

Preorder traversal

Visit the root node first, then visit the left and right children

• Recursive method

class Solution {
     
     public ListInteger!stack.isEmpty(  )) {
     
             while (root != null) {
     
                 stack.push(root);
                 root = root.left;
             }
             root = stack.pop();
             if (root.right == null || root.right   == prev) {
     
                 res.add(root.val);
                 prev = root;
                 root = null;
             } else {
     
                 stack.push(root);
                 root = root.right;
             }
         }
         return res;
     }
 }
 

Postorder traversal results: 4->8->6->12->16->14->10

Breadth-first traversal (BFS)

In fact, it is a layer-by-layer traversal, outputting each node of the binary tree according to the level

Hierarchy Traversal

According to the number of layers, traverse from bottom to top

class Solution {
     
     public ListList<  Integer levelOrder(TreeNode root) {
     
         ListListInteger  > ret = new  span> ArrayListListInteger(  );
         if (root == null) {
     
             return ret;
         }

         QueueTreeNode queue = new LinkedListTreeNode();
         queue.offer(root);
         while (!queue.isEmpty()) {
     
             ListInteger level = new ArrayListInteger();
             int currentLevelSize = queue.size();
             for (int i = 1; i <= currentLevelSize; ++i) {
     
                 TreeNode node = queue.poll();
                 level.add(node.val);
                 if (node.left != null) {
     
                     queue.offer(node.left);
                 }
                 if (node.right != null) {
     
                     queue.offer(node.right);
                 }
             }
             ret.add(level);
         }
        
         return ret;
     }
 }
 

Hierarchical traversal result: 10->6->14->4->8->12->16

n punctuation”>TreeNode queue = new LinkedListTreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {

ListInteger level = new ArrayListInteger();
int currentLevelSize = queue.size();
for (int i = 1; i <= currentLevelSize; ++i) {

TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {

queue.offer(node.left);
}
if (node.right != null) {

queue.offer(node.right);
}
}
ret.add(level);
}

return ret;
}
}

Hierarchical traversal result: 10->6->14->4->8->12->16