Defeat the binary tree!

The concept and structure of tree

Trees are a kind of Nonlinear data structure , It is from n（n≥0） Finite nodes make up a set with hierarchical relations . It's called a tree because it looks like an upside down tree , That is to say, it is root up , And leaf down .
● There is a special node , be called root node , The root node has no precursor node , But there are 0 One or more successors
● Except for the root node , The rest of the nodes are divided into M(M>0) Disjoint sets T1、T2、……、Tm, And every set of them Ti(1<= i<= m) Another tree with a structure similar to that of a tree subtree . The root node of each subtree has and only has one precursor , There can be 0 One or more successors .

therefore , Trees are defined recursively .

Degree of node ： The number of subtrees a node contains Called the degree of the node ;
Leaf nodes Or terminal node ： Degree is 0 The node of It's called a leaf node ;
Non terminal nodes Or branch node ： The degree is not for 0 The node of ;
parent node Or parent node ： If a node has child nodes , This node is called the parent of its child ; Pictured above ：A yes B Parent node
Child node Or child nodes ： The root node of the subtree that a node contains is called the child node of the node ; Pictured above ：B yes A The child node of
Brother node ： Nodes with the same parent They call each other brother nodes ;
Treelike degree ： In a tree , The degree of the largest node is called the degree of the tree ;
Node level ： Starting from the root , The root for the first 1 layer , The child node of the root is the 2 layer , And so on ;
Treelike Height or depth ： The maximum level of nodes in the tree ;
Cousin node ： The nodes of both parents on the same layer are cousins to each other ;
Node The ancestors ： From the root to all nodes on the branch through which the node passes ;
descendants ： Any node in a subtree with a node as its root is called the descendant of the node .
The forest ： from m（m>0） A collection of trees that do not intersect each other is called a forest ;

Practical applications such as ：Linux directory tree
 
 
 

Binary tree

 

Concept and structure

Binary tree (Binary Tree) yes n(n≥0) A collection of nodes , It may be an empty tree (n= 0); Or a non empty tree ,
For non empty trees T: (1) There is only one node called root ; (2) The other nodes except the root node are divided into two disjoint subsets T1 and T2, Known as T The left and right subtrees of , And T1 and T2 Itself is a binary tree .

Binary trees have the same recursive properties as trees , There are two main differences between binary tree and tree ：

1. Each node of a binary tree has at most two subtrees （ namely There is no large degree and in binary tree 2 The node of ）;
2. The subtree of a binary tree has left and right branches , The order cannot be reversed arbitrarily .（ Ordered trees ）

Binary tree 5 There are three basic forms

 

Special binary tree

1. Full binary tree ：
   Depth is K And Nodes total 2^K-1 individual Two fork tree , That is, the number of nodes in each layer is full （ Have reached the maximum ）, Then this binary tree is full of binary trees .
   The number of nodes in each layer is 2^K-1

2. Perfect binary tree ：
   Depth is K And The number of nodes is n Two fork tree , If and only if each of its nodes has a depth of K From the full binary tree of 1~n When the node position serial numbers of are one-to-one corresponding, it is a complete binary tree .
   A full binary tree is a special kind of complete binary tree .
   ( Tree height is h , front h-1 The layers are full , The first h Layer from left -> Right primary storage )

The total number of nodes is Odd number ： No, Degree is 1 The node of by even numbers ： Degree is 1 Nodes of have and only One

 
 

nature

1. If the specified number of layers of the root node is 1, Then the of a non empty binary tree The first i There is a maximum of 2^(i-1) Nodes .

2. If the specified number of layers of the root node is 1, Then the depth is h Binary tree The maximum number of knots is 2^h-1（ Full binary tree ）

3. Any binary tree , If the degree is 0 The number of leaf nodes is N0, Degree is 2 The number of branch nodes is N2, Then there are N0 ＝ N2＋1
   

4. If the specified number of layers of the root node is 1, have n The depth of a complete binary tree of nodes ,h = log2(n+1)(ps： yes log With 2 Bottom ,n+1 For logarithm )
   

5. Those who have n Of nodes Perfect binary tree , If all nodes are in the array order from top to bottom and from left to right from 0 Numbered starting , Then for the serial number is i There are ：

1. if i > 0,i The parent sequence number of the location node ：(i-1)/2;i=0,i Number the root node , No parent nodes
2. if 2i+1<n, Left child serial number ：2i+1,2i+1 ≥ n otherwise No left children
3. if 2i+2<n, Right child number ：2i+2,2i+2 ≥ n otherwise No right children
 

 
 

Storage structure

1. Sequential structure ： Binary tree sequential storage is a physical Array , Logically, it is a binary tree .

Sequential structure storage is to make Use arrays to store , Memory is continuously distributed ,（ Generally, arrays are only suitable for representing complete binary trees , Because it is not a complete binary tree, there will be a waste of space .） In reality, only the heap will use arrays to store , About Pile up As shown in the first half

2. The chain structure ： The chain storage structure of binary tree refers to the use of linked list to represent a binary tree , Chain is used to indicate the logical relationship of elements .

Chained storage is to connect the nodes scattered at various addresses in series through pointers The usual method is that each node in the linked list consists of three fields , Data fields and Left and right pointer fields , The left and right pointers are used to give the storage address of the chain node where the left child and the right child of the node are located .

Chain structure can be divided into binary chain and trigeminal chain , Most of them are binary chains , For example, red and black trees will use trigeminal chains .

 
 

Traversal of binary tree

（ These two kinds of traversal are the most basic traversal ways in graph theory ）

Depth-first traversal ： Go deep first , Meet the leaf node and go back .
● The former sequence traversal （ Recursive method , Iterative method ） Root left and right
● In the sequence traversal （ Recursive method , Iterative method ） Left root right
● After the sequence traversal （ Recursive method , Iterative method ） Left and right

Breadth first traversal ： Layer by layer to traverse .
● Level traversal （ Iterative method ）

The definition of binary tree

// C （ Binary chain ）
struct TreeNode {
    
     int val;
     struct TreeNode *left;   //  Structure pointer 
     struct TreeNode *right;
};
—————————————————————————————————————————————————————————————————————————
// cpp
struct TreeNode {
    
      int val;
      TreeNode *left;
      TreeNode *right;
      //  Three overloaded constructions 
      TreeNode() : val(0), left(nullptr), right(nullptr) {
    }
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {
    }
 };

 

The former sequence traversal

144. Preorder traversal of two tree
It's also called sequence traversal , Access order: root node -> The first sequence traversal The left subtree -> The first sequence traversal Right subtree

    //  Preorder traversal recursive implementation 
	void preOrder(TreeNode* root, vector<int>& res){
    
        if(nullptr == root) return ;   // Recursive export 
        res.push_back(root->val);   //  Save root value 
        preOrder(root->left, res);   //  Traverse left subtree 
        preOrder(root->right, res);  //  Traversal right subtree 
    }  
      
    vector<int> Traversal(TreeNode* root) {
    
        vector<int> res;
        preOrder(root, res);
        // inOrder(root, res);
        // postOrder(root, res);
        return res;
    }

Preorder traversal is root left and right , Each time, the intermediate node is processed first , Then put the root node on the stack first , Then add the right child Stack , Add the left child . In this way, when the stack is released, the root is in the left and right order .

  //  iteration 
    // Then put the root node on the stack first , Then add the right child to the stack , Add the left child 
    vector<int> preorderTraversal(TreeNode* root) {
    
        stack<TreeNode*> s;
        vector<int> res;
        if(nullptr == root) return res;
        s.push(root);
        while(!s.empty()){
    
            TreeNode* node = s.top();    //  The root node 
            s.pop();  
            res.push_back(node->val);  
            if(node->right != nullptr)
                s.push(node->right);   //  Right child in the stack 
            if(node->left != nullptr)
                s.push(node->left);    //  Left child in the stack 
        }
        return res;
    }

 

In the sequence traversal

94. Middle order traversal of binary trees
Access order: In the sequence traversal The left subtree -> root node -> In the sequence traversal Right subtree

//  Middle order traversal recursive implementation 
    void inOrder(TreeNode* root, vector<int>& res){
    
        if(nullptr == root) 
            return ;   // Recursive export  
        inOrder(root->left, res);   //  Traverse left subtree 
        res.push_back(root->val);   //  Save root value 
        inOrder(root->right, res);  //  Traversal right subtree 
    }

The node at the top of the binary tree is accessed first , Then, layer by layer, access down , Until you reach the bottom of the tree to the left , And then we start processing nodes （ That is, put the node value in res Array ）

Use the iteration method to write the middle order traversal , You need to borrow The pointer To help access nodes , Stack Is used to process elements on nodes .

   //  iteration 
   vector<int> inorderTraversal(TreeNode* root) {
    
        stack<TreeNode*> s;
        vector<int> res;
        TreeNode* cur = root;
        while(cur != nullptr || !s.empty()){
    
            if(cur != nullptr){
       //  Access to the bottom 
                s.push(cur);
                cur = cur->left;
            }else{
    
                cur = s.top();
                s.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }

        return res;
    }

 

After the sequence traversal

145. Postorder traversal of binary trees
Access order: After the sequence traversal The left subtree -> After the sequence traversal Right subtree -> root node

//  After order traversal recursive implementation 
    void postOrder(TreeNode* root, vector<int>& res){
    
        if(nullptr == root)
            return ;
        postOrder(root->left, res);
        postOrder(root->right, res);
        res.push_back(root->val);
    }

Post order traversal only requires a slight modification of the pre order traversal code

  //  iteration 
   vector<int> postorderTraversal(TreeNode* root) {
    
        vector<int> res;
        stack<TreeNode*> s;
        if(nullptr == root) return res;
        s.push(root);
        while(!s.empty()){
    
            TreeNode* node = s.top();
            s.pop();
            res.push_back(node->val);
            //  Relative to preorder traversal , This changes the order of stack entry 
            if(node->left != nullptr) s.push(node->left);
            if(node->right != nullptr) s.push(node->right);
            
        }
        reverse(res.begin(), res.end()); //  After reversing the result, the order of the subsequent order is 
        return res;
    }

---

C Language recursive implementation of three traversal code
 

Sequence traversal

Sequence traversal requires the help of queues
First queue the root node and then : If the queue is not empty , Cycle through the following operations :
1. Take... From the queue 1 Nodes
2. Remove the node from the queue （ Pointer save ）
3. Traverse the node
4. If the node has a left child , Put the child in the left queue ; If there is a right child , Put the right child in the queue

    vector<vector<int>> levelOrder(TreeNode* root) {
    
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(nullptr == root) return res;
        q.push(root);
        //  When the first i After traversing all nodes of the layer , If the queue is not empty , Then... Is just placed in the queue i+1 The nodes of the layer 
        while(!q.empty()){
    
            size_t size = q.size();
            vector<int> level;
            level.reserve(size);
            for(int i = 0; i < size; ++i){
    
                TreeNode* node = q.front();
                q.pop();   // Remove the node from the queue （ Pointer save ）
                level.push_back(node->val);
                // If the node has a left child , Put the child in the left queue ;  If there is a right child , Put the right child in the queue 
                if(node->left != nullptr) q.push(node->left);
                if(node->right != nullptr) q.push(node->right);
            }
            res.push_back(level);
        }
        return res;
    }

Learn sequence traversal Leetcode Hit ten directly ！

 
 

Binary search tree

Also called binary sorting tree , The binary search tree is an ordered tree . Binary sort tree or an empty tree , Or a binary tree that has the following properties
● If it's Zuozi tree is not empty , be The values of all nodes on the left subtree are Less than Its root node Value ;
● If it's Right subtree is not empty , be The values of all nodes on the right subtree are Greater than Its root node Value ;
● Its left 、 The right subtree is also a binary sort tree

AVL Trees

Balanced binary trees (Balance d Binary Tree or Height-Balanced·Tree), Because the mathematicians of the former Soviet Union Adelson-Velskii and Landis Put forward , So it's also called AVL Trees
Balanced binary tree or empty tree , Or a binary sort tree with the following characteristics ：
( 1 ) Left subtree and right subtree The difference in depth ( Balance factor ) The absolute value of is not more than 1;
( 2 ) The left and right subtrees are also balanced binary trees .

If the equilibrium factor of the node on the binary tree (Balance Factor, BF) It is defined as the sum of the depths of the left subtree and the right subtree of the node
Bad , Then the equilibrium factors of all nodes on a balanced binary tree can only be found -1、0 and 1.

If a binary search tree is highly balanced , It is AVL Trees . If it has n Nodes , Its height can be maintained at O(log2n) , Search time complexity O(log2n) .

 

red Black tree

AVL-tree outside , Another historical and widely used balanced binary search tree is RB- tree
( Red and black trees ). So-called RB-tree, Not only is - A binary search tree , And the following rules must be met :

1. Each node is either red or black
2. root The node is black color .
3. If The node is red , Its child nodes must be black .
4. Any node to NULL ( End of tree ) Of Any path , The number of black nodes must be the same .

C++ in map、set、multimap,multiset The underlying implementation of is a balanced binary search tree （ Red and black trees ）

Red and black trees and AVL Trees are efficient balanced binary trees , The time complexity of adding, deleting, modifying and checking is O(log2N),
AVL Trees are highly balanced , Frequent insertion and deletion , Will cause frequent rebalance, Resulting in a decrease in efficiency ;
Red and black trees do not pursue absolute balance , It only needs to ensure that the longest path does not exceed... Of the shortest path 2 times , Relatively speaking , Reduces the number of inserts and rotations , Therefore, in the structure of frequent additions and deletions, the neutral energy ratio AVL Better trees , And the implementation of red black tree is relatively simple , So there are more red and black trees in practical application .