Basic knowledge and examples of binary tree

Catalog

1 Node structure of binary tree

1.1  Using recursive and non recursive methods to realize the preorder of binary tree 、 Middle preface 、 After the sequence traversal

1.1.1 Recursive order

1.1.2 Recursive version Preface Middle preface In the following order

1.1.3 Non recursive version of Preface Middle preface In the following order

1.2 How to complete the width first traversal of binary tree （ Common topics ： Find the width of a binary tree ）

2 Related concepts of binary tree and its implementation judgment

2.1 How to judge whether a binary tree is a search binary tree ？

2.2 How to judge whether a binary tree is a complete binary tree ？

2.3 How to judge whether a binary tree is full of binary trees ？

2.4 How to judge whether a binary tree is a balanced binary tree ?

3 Given the nodes of two binary trees node1 and node2, Find their lowest common ancestor node

4 Find the successor of a node in the binary tree

5 Serialization and deserialization of binary trees

6 creasing problem

---

1 Node structure of binary tree

class Node<V>{

        V value;

        Node left;

        Node right;

}

Using recursive and non recursive methods to realize the preorder of binary tree 、 Middle preface 、 After the sequence traversal

How to complete the width first traversal of binary tree （ Common topics ： Find the width of a binary tree ）

1.1  Using recursive and non recursive methods to realize the preorder of binary tree 、 Middle preface 、 After the sequence traversal

1.1.1 Recursive order

void f(Node head)
{

    if(head == null)
    {
       return;
     }

    f(head.left);
    f(head.right);

}

analysis ： It will return to the original function many times , Although nothing was done , Every node will be used 3 Time

1.1.2 Recursive version Preface Middle preface In the following order

All are processed by recursive order , Choose a different time to print .

The first order is to print out （ Around the head ）：1,2,4,5,3,6,7 （ Print the first time you enter the function , The other two times will not be printed ）

The middle order is printed out as （ Left head right ）：4,2,5,1,6,3,7（ Print the second time you enter the function , The other two times will not be printed ）

The following sequence is printed out as （ Left and right ）：4,5,2,6,7,3,1（ Print the third time you enter the function , The other two times will not be printed ）

1.1.3 Non recursive version of Preface Middle preface In the following order

  Self stack .

First step ：

① Pop up a node from the stack cur

② Print （ Handle ）cur

③ First press the right child into the stack, and then press the left child into the stack （ If any ）

④ go back to ① repeat

Subsequent steps ：

① Pop up a node from the stack cur

② take cur Put it into the collection stack

③ First press the right child into the stack, and then press the left child into the stack （ If any ）

④ go back to ① repeat

⑤ Until there is no number, the data will be ejected from the collection stack and printed in turn

Intermediate steps ：

① Each subtree is stacked on the left border of the whole tree

② Print in the process of pop-up in turn

③ Stack the right tree of the pop-up node （ When entering the stack, it is also the left border of the whole tree ）

④ go back to ②, If there is no data in the stack, go back to ①

ex. step1:1,2,4 Into the stack -> eject 4->4 There is no right tree back ①-> eject 2->2 There is a right tree , take 5 Into the stack ->····

1.2 How to complete the width first traversal of binary tree （ Common topics ： Find the width of a binary tree ）

Preorder traversal is the depth first traversal of binary trees

  Width first traversal uses queues ,

Width first traversal step ：

① Pop up a node from the queue list cur

② Print （ Handle ）cur

③ First put the left child in the queue, and then put the right child in the queue （ If any ）

④ go back to ① repeat

Find the width of a binary tree （ Hash table method ）

Queue<Node> queue = new LinkedList<>();
queue.add(head);
HashMap<Node,Integer> levelMap = new HashMap<>();    // Store all nodes and their levels 

levelMap.put(head,1);    // The head node of the tree , The node level is 1

int curLevel = 1;
int curLevelNodes = 0;
int max = Integer.MIN_VALUE; // Minimum value of global variable  （ Or take 0 Can also be ）

while(!queue.isEmpty())
{
    Node cur = queue.poll();
    int curNodeLevel = levelMap.get(cur);// Get the current level 
    if(curNodeLevel == curLevel)
    {
        curLevelNodes++; // If the current level is at the level to be calculated , Then pop up the data ++
    }
    else
    {
        max = Math.max(max,curLevelNodes); // If not , Then the current level is the next , Start comparing the maximum width 
        curLevel++;    // The level that needs to be calculated at the beginning is next level 
        curLevelNodes = 1; // Initialize the number of nodes of this level 
    }

    if(cur.left != null)
    {
        levelMap.put(cur.left, curNodeLevel+1);
        queue.add(cur.left);
    }
    if(cur.right != null)
    {
        levelMap.put(cur.right , curNodeLevel+1);
        queue.add(cur.right);
    }
}

2 Related concepts of binary tree and its implementation judgment

2.1 How to judge whether a binary tree is a search binary tree ？

Search binary trees ： For every sub tree , His left tree nodes are smaller , The nodes of his right tree are larger .

  Method ：

In the sequence traversal , What you get is an ascending data , It is a search binary tree

2.2 How to judge whether a binary tree is a complete binary tree ？

Perfect binary tree ： The depth of a tree is one k There are n Of nodes Binary tree , Click from top to bottom for the nodes in the tree 、 Number from left to right , If the number is i（1≤i≤n） Node and Full binary tree Number is i The nodes of the binary tree have the same position , This binary tree is called a complete binary tree . 

Method ： Width traversal

① Any node has right or left , return false （ That is, it is not a complete binary tree ）

② In dissatisfaction ① Under the circumstances , If you meet the first child or so, it's not all , Subsequent leaf nodes （ That is, there is no subtree ）

③ return ① Continue to judge

2.3 How to judge whether a binary tree is full of binary trees ？

A full binary tree means that there are no child nodes in the last layer , A binary tree in which all nodes on each layer have two children .

A simple way to understand ： Use a function to find the maximum depth of a binary tree D, Use a function to find the number of nodes of the binary tree N. Satisfy , It's full of binary trees

2.4 How to judge whether a binary tree is a balanced binary tree ?

Balanced binary trees ： Balance tree (Balance Tree,BT) refer to , The height difference of any node's subtree is less than or equal to 1. And both the left tree and the right tree are balanced trees .

public static boolean isBalanced(Node head){
    return process(head).isBalanced;
}

public static class ReturnType{
    public boolean isBalanced;
    public int height;

    public ReturnType(boolean isB, int hei){
            isBalanced = isB;
            height = hei;
    }
}

public static ReturnType process(Node x){
    if( x == null) 
    {// base
     return new ReturnType(true, 0);
    }

    ReturnType leftData = process(x.left);
    ReturnType rightData = process(x.right);

    int height = Math.max(leftData.height, rightData.height)+1;
    
    boolean isBalanced = leftData.isBalanced&&rightData.isBalanced
                        &&Math.abs(leftData.height-rightData.height<2)

    return new ReturnType(isBalanced, height);
}

3 Given the nodes of two binary trees node1 and node2, Find their lowest common ancestor node

Their thinking ：

① First, establish the parent node of each node through the hash table

② Create hash table set1 Storage node1 Sequence of nodes

③ Give Way node2 Back up , And judge whether the new value is set1 in

4 Find the successor of a node in the binary tree

There is now a new binary tree node type as follows ：

public class Node{

        public int value;

        public Node left;

        public Node right;

        public Node parent;

        public Node(int val){

                value = val;

        }

}

This structure has one more point to the parent node than the normal binary tree node structure parent The pointer

So let's say I have one Node A binary tree of nodes of type , For each node in the tree parent Pointers all point correctly to their parent node , Head of the node parent Point to null.

I'm just going to give you a node in the binary tree node, Please implement return node The function of the subsequent nodes of .

A sequence traversed in the middle order of a binary tree ,node The next node of node Successor node .

Problem solving analysis ：

①x When there is a right tree , here x The successor node of is the leftmost node on the right tree

②x When there is no right tree ,x Keep looking up , Judge whether it is currently the left node of the father , Until the time is y yes x Successor node

③ When x When it is the rightmost node , At this time, there is no successor node , Its successor node is null

 

public static Node getSuccessorNode(Node node){
    if (node == null){
        return node
    }
    if (node.right != null){
        return getLeftMost(node.right);// situation ①
    } else{ // situation ②
        Node parent = node.parent;
        while(parent != null && parent.left != node){// The current node is the right child of its parent node 
            node = parent;
            parent = node.parent;
        }
        return parent;
    }

}

public static Node getLeftMost(Node node){
    if(node == null){
        return node;
    }
    while(node.left != null){
        node = node.left;
    }
    return node;
}

5 Serialization and deserialization of binary trees

Is how a tree in memory becomes a string （ serialize ）, How to change from string form to tree in memory （ Deserialization ）

How to judge whether a binary tree is a subtree of another binary tree

With “#” Representational space ,“_” For the end

public static String serialByPre(Node head){
    if(head == null){
        return "#_";
    }
    String res = head.value + "_";
    res += serialByPre(head.left);
    res += serialByPre(head.right);
    return res;
}

public static Node reconByPreString(String preStr){
    String[] values = preStr.split("_");
    Queue<String> queue = new LinkedList<String>();
    for(int i = 0 ; i != value.length; i++){
        queue.add(value[i]);
    }
    return reconByPreOrder(queue);
}

public static Node reconPreOrder(Queue<String> queue){
    String value = queue.poll();
    if(value.equals("#"){
        return null;
    }
    Node head = new Node(Integer.valueOf(value));
    head.left = reconPreOrder(queue);
    head.right = reconPreOrder(queue);
    return head;
}

6 creasing problem

Please put a piece of paper on the table , Then fold it in half from the bottom of the note to the top , Press out the creases and unfold .

Now the crease is concave , That is, the direction of the crease bulge points to the back of the paper .

If you fold the note in half from the bottom to the top twice in a row , Press out the creases and unfold , At this time, there are three creases on the right , From top to bottom are the lower creases 、 Lower crease and upper crease

Given an input parameter N, It means that the paper is folded in half from the bottom to the top N Time .

Please print the direction of all creases from top to bottom .

for example ：N=1 when , Print down , N=2 when , Print ： down down up

Problem solving analysis ： That is, a left subtree is concave , The right subtree is a convex full binary tree

 

pubulic static void printAllFolds(int N){
    printProcess(1,N,true);
}

// A recursive process , Came to a node 
//i Is the number of layers of the node ,N The total number of floors , down == true  concave , down == false  Convex 
public static void printProcess(int i, int N, boolean down){
    if(i > N){
        return;
    }
    printProcess(i + 1, N, true);
    System.out.println(down ? " concave " : " Convex ");
    printProcess(i + 1, N, false);
}