Binary tree -- natural search semantics (1) Basics

1. Tree structure can search and search efficiently .（ System files , It's a tree structure . Find specific files according to folders , Time complexity is actually the depth of the number of files logN）

Tree structure in life ： Library system 、 Management of large enterprises

After storing the data in a tree structure , Search or find again , The efficiency is much higher than that of linear structure .

2. Common tree structure ：

BST Binary search tree -- Element search of binary tree

Balanced binary search trees -- AVL（ Strict balance ）, Red and black trees （ Non strict equilibrium ）

notice logN Associate with tree structure

3. Trees ： The subtrees can't intersect .

Except for the root node , Each node has and only has one parent

One N The tree of nodes has N-1 side

Degree of node ： The number of subtrees contained in the node is called the degree of the node

The degree of a tree ： The degree of the largest node in the tree

leaf node （ Terminal nodes ）： Degree is 0 The node of

Tree hierarchy ： Calculate from the root

Binary tree ： Each node has at most two subtrees , The degree of a node in a binary tree does not exceed 2, The two sub trees are divided into left and right .

Full binary tree ： The degree of all non leaf nodes is 2. 

For a binary tree , The height is k, Then the binary tree has at most 2 Of k Power -1 Nodes （ The most common case is full binary tree ）.

The hierarchy is k, The first k There are at most 2 Of k-1 Sub nodes .

Side length = The number of nodes n-1

Set the degree as 0 The number of nodes is n0, Degree is 1 The number of nodes of is n1, Degree is 2 The number of nodes of is n2,

be n0 = n2 +1

n0 + n1+ n2 = n

---

Perfect binary tree ： The full binary tree is missing the lower right corner

The node numbers of the complete binary tree correspond to the full binary tree one by one . The nodes of each layer try to reach the maximum , If the node of a certain layer does not reach the maximum , The nodes of this layer are arranged on the left .

In a complete binary tree , There is no node with only right subtree and no left subtree （ Nodes should be arranged on the left ）.

Binary tree storage ：

It's like a list , Sequential storage and chained storage （ quote ）

Sequential storage , Store the binary tree in an array （ Only complete binary trees can be stored ）

Ordinary binary trees are stored by reference .

Traversal of binary tree ： Before the order 、 Middle preface 、 In the following order 、 level

When writing three traversal methods , With the help of stack structure , Ensure that it is not heavy or missing .

// The first sequence traversal : Root left and right 
    // Pass in the root node of a binary tree . You can output the node value in the way of preorder traversal 
    public static void preOrder(TreeNode root){
        // The boundary conditions 
        if(root == null){
            return ;
        }
        System.out.println(root.val + " ");
        // Recursively access the left subtree in the way of preorder traversal 
        preOrder(root.left);
        // Access the right tree in the way of preorder traversal 
        preOrder(root.right);
    }

  // In the sequence traversal ： Left middle right 
    // Pass in the root node of a binary tree , The result set can be output in the way of middle order traversal 
    public static void inOrder(TreeNode root){
        if(root == null){
            return ;
        }
        inOrder(root.left);
        System.out.println(root.val + " ");
        inOrder(root.right);
    }

Sequence traversal is a non recursive iterative method , Here is the code implementation ：

public class Num102_LevleOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        // The traversal process is realized with the help of queues 
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            // Continue to traverse when it is not empty 
            // Use one temp Array to hold the elements of the current level 
            List<Integer> curList = new ArrayList<>();
            // Take out all the elements of the current layer and add them into curList in 
            int size = queue.size();
            for (int i = 0; i <size; i++) {
                TreeNode cur = queue.poll();
                curList.add(cur.val);
                if(cur.left!= null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }
            // The current layer element has been traversed 
            ret.add(curList);
        }
        return ret;
    }
}