The binary tree is established

Firstly, the node structure is given:

static class Node { public int val; public Node left; public Node right; public Node(int val) { this.val = val; }}Copy the code

There are two ways to establish:

  • The binary tree can be built recursively according to the subscript relation between the binary root node and the left and right child nodes.
  • You can also use the input stream preorder to create a binary tree (note that the empty tree must enter -1).

1. According to the subscript relationship

// given a arr to build
static Node createTree(int arr[], int i) {
    if (i >= arr.length || arr[i] == -1)
        return null;
    Node root = new Node(arr[i]);
    root.left = createTree(arr, 2 * i + 1);
    root.right = createTree(arr, 2 * i + 2);
    return root;
}
Copy the code

The general process is as follows:

2. Pre-sequence input (CIN) is established

// cin method static Node buildTree(Scanner cin) { Node root = null; int data = cin.nextInt(); if (data ! = -1) { root = new Node(data); root.left = buildTree(cin); root.right = buildTree(cin); } return root; }Copy the code

The process is as follows:

The former sequence traversal

1. Recursive preordering

static void preOrder(Node T) {
    if (T == null)
        return;
    System.out.print(T.val + " ");
    preOrder(T.left);
    preOrder(T.right);
}
Copy the code

2. Non-recursive preordering

The preceding traversal sequence is: root -> left subtree -> right subtree. Therefore, you can directly access the root node being accessed. After accessing the root node, access the left subtree and then access the right subtree in the same way.

  • If the current nodepNot null, access nodepAnd place the nodepPushes and continues to access the left subtree (until the left subtree is empty);
  • Otherwise, push the top element off the stack and access the right subtree of the top element.
  • Until the stack is empty andpIs empty, the loop ends.

Code:

static void iterativePre(Node root) { Stack<Node> s = new Stack<>(); Node p = root; while (! s.empty() || p ! = null) { if (p ! // We can also write a while loop until the left subtree is empty. System.out.print(p.val + " "); p = p.left; } else { p = s.pop(); p = p.right; }}}Copy the code

We can also write a while loop with the above all access to the left subtree empty:

static void iterativePre2(Node root) { Stack<Node> s = new Stack<>(); Node p = root; while (! s.empty() || p ! = null) { while (p ! = null) {// while loop until left subtree is empty. System.out.print(p.val + " "); p = p.left; } p = s.pop(); p = p.right; }}Copy the code

Here’s another way to write it:

  • The root node is pushed, and then it’s pushed one element at a time, accessing that element first, and then if its right subtree exists, and if its left subtree exists, it’s pushed;
  • The reason for entering the right subtree first is that the preceding traversal is middle > left > right, and the stack can be reversed, so right first and then left;

This method is shown later in the double stack method of traversal, which is just this slight modification.

static void iterativePre3(Node root) { if (root == null) return; Node p = root; Stack<Node> stack = new Stack<>(); stack.add(p); while (! stack.isEmpty()) { p = stack.pop(); System.out.print(p.val + " "); if (p.right ! = null)// stack. Push (p.right); if (p.left ! = null) stack.push(p.left); }}Copy the code

In the sequence traversal

1. Recursive middle order

static void inOrder(Node T) {
    if (T == null)
        return;
    inOrder(T.left);
    System.out.print(T.val + " ");
    inOrder(T.right);
}
Copy the code

2. Non-recursive middle order

Middle order traversal: left subtree -> root -> right subtree, as follows:

  • The current node is not empty! = null, the current node is pushed to the left (unlike the previous traversal, no printing is required);
  • The current node is empty== null, take one off the stack and print it (print it here) with the current node to the right;

Until the stack is empty and P is empty, the loop ends.

/** * 1), the current node is not empty (! =null), the current node is pushed to the left (unlike previous traversal, no printing is required); * 2), the current node is empty (==null), take one from the stack and print (print here), the current node to the right; */ static void iterativeIn(Node root) { if (root == null) return; Stack<Node> s = new Stack<>(); Node p = root; while (! s.empty() || p ! = null) { if (p ! = null) { s.push(p); p = p.left; } else { p = s.pop(); System.out.print(p.val + " "); // Print p = p. light; }}}Copy the code

Similarly, the child who keeps visiting the left can also be changed to whlie:

static void iterativeIn2(Node root) {
    if (root == null)
        return;
    Stack<Node> s = new Stack<>();
    Node p = root;
    while (!s.empty() || p != null) {
        while (p != null) { //这里改成while
            s.push(p);
            p = p.left;
        }
        p = s.pop();
        System.out.print(p.val + " "); //在这里打印
        p = p.right;
    }
}
Copy the code

After the sequence traversal

1. Recursive post-order

static void postOrder(Node T) {
    if (T == null)
        return;
    postOrder(T.left);
    postOrder(T.right);
    System.out.print(T.val + " ");
}
Copy the code

2. Non-recursive post-ordering

1) Double stack method

This is actually a slight improvement on the nonrecursive pre3.

  • First, pre-traversal the push (iterativePre3) in the order ofRight to left first;
  • In this case, we can do the reverse, first left then right, so that the traversal order can be “center right left”, and the subsequent traversal order is “left right center”, which is exactly the opposite of the previous one, so we can use another stack inversion to save;

Code:

/** * non-recursive follow-up 1(double stack method to solve non-recursive follow-up) * subsequent traversal is to be implemented &emsp; &emsp; &emsp; Left -> right -> * This method and the second method of pre-order traversal &emsp; It's just one more stack * because emsp; Preorder traversal is middle -> left -> right &emsp; &emsp; The order of pressing is right -> left *, which is easy to implement. Middle -> right -> left traversal &emsp; &emsp; The pushing order is &emsp; Left -> right * and the next iteration is to implement left -> right -> middle, * we put the top &emsp; &emsp; Right & left emsp; Push into another stack. Emsp; / static void iterativePos(Node root) {Stack<Node> s = new Stack<>(), s2 = new Stack<>(); / static void iterativePos(Node root) {Stack<Node> s = new Stack<>(), s2 = new Stack<>(); Node p; s.push(root); while (! s.empty()) { p = s.pop(); s2.push(p); if (p.left ! = null) s.push(p.left); // if (p. Right!) {// if (p. Right! = null) s.push(p.right); } while (! s2.empty()) System.out.print(s2.pop().val + " "); }Copy the code

2), set upprenode

The process is as follows:

  • For any nodep, first push it to the stack;
  • Access conditions: ① IfpIf there are no left and right children, you can access it directly. (2) orpThere is a left child or a right child, but the left child and the right child have been accessed, can also directly access the node;
  • If not, the right child and the left child are pushed one by one. This ensures that every time the top of the stack is fetched, the left child is accessed before the right child, and the root node is accessed after the left and right children;

Code:

*/ static void iterativePos2(Node root) {Node cur, pre = null; Stack<Node> s = new Stack<>(); s.push(root); while (! s.empty()) { cur = s.peek(); / / the situation of the two can access the if ((cur) left = = null && cur. Right = = null) | | ((pre! = null) && (pre == cur.left || pre == cur.right))) { System.out.print(cur.val + " "); s.pop(); pre = cur; } else { if (cur.right ! = null) s.push(cur.right); if (cur.left ! = null) s.push(cur.left); }}}Copy the code

Level traversal

Very simple. Queue BFS can be used. After accessing P each time, if the left and right children exist, they will join the queue until the queue is empty.

static void levelOrder(Node root) { if (root == null) return; Queue<Node> queue = new LinkedList<>(); queue.add(root); while (! queue.isEmpty()) { Node now = queue.poll(); System.out.print(now.val + " "); if (now.left ! = null) queue.add(now.left); if (now.right ! = null) queue.add(now.right); }}Copy the code

Look for any nodes in the tree that have a value of x

There are two recursive conditions, one is empty means not found, if found directly return, otherwise recursively search left and right subtrees.

Static Node search(Node T, int x) {if (T == null) return null; static Node search(Node T, int x) {if (T == null) return null; if (T.val == x) return T; else { if (search(T.left, x) == null) return search(T.right, x); else return search(T.left, x); }}Copy the code

Count the number of nodes in the tree

The number of nodes in the tree is equal to the root node (1) + the number of left subtrees + the number of right subtrees.

sourceStatic int count(Node T) {static int count(Node T) {if (T == null)
        return 0;
    else
        return count(T.left) + count(T.right) + 1;
}
Copy the code

Compute the height of the tree

Again, recursively, the higher of the left and right subtrees plus the root is the height of the tree.

sourceStatic int depth(Node T) {static int depth(Node T) {if (T == null)
        return 0;
    return Math.max(depth(T.left), depth(T.right)) + 1;
}
Copy the code

Determine if two trees are equal

Again, recursively, the two trees are equal, so the root nodes are equal, and the left and right subtrees are equal.

sourceStatic Boolean is_SameTree(Node T1, Node T2) {static Boolean is_SameTree(Node T1, Node T2) {if (T1 == null && T2 == null)
        return true;
    else {
        returnT1 ! = null && T2 ! = null && T1.val == T2.val && is_SameTree(T1.left, T2.left) && is_SameTree(T1.right, T2.right); }}Copy the code

Welcome to pay attention to the public number: the growth of the old boy road, selected dry goods regularly every week!