Binary tree

Definition of node

class TreeNode<T> {
  public val: T;
  public right: TreeNode<T> | null = null;
  public left: TreeNode<T> | null = null;
  public parent: TreeNode<T> | null = null;
  constructor(val: T) {
    this.val = val;
  }

  isLeave() {
    return this.left === null && this.right === null; }}Copy the code

traverse

One of the most important operations for binary trees is traversal. Traversal is divided into pre-order, mid-order, post-order and hierarchical traversal, also known as depth-first search and breadth-first search.

Depth-first search includes pre-order, middle-order and post-order traversal.

Depth first

Recursion is probably the first thing that comes to mind for depth-first search, and it’s also the easiest way to do it.

function traversal(root: TreeNode<T> | null) :void {
    if (root) {
        / / order before visit (root);
        traversal(root.left);
        / / in order to visit (root);
        tranersal(root.right);
        / / order after visit (root);}}Copy the code

The dotted line is the path of depth-first search, which shows that the node of degree 0 will be visited once, the node of degree 1 will be visited twice, and the node of degree 2 will be visited three times.

The so-called pre-order, mid-order, post-order traversal refers to the number of times the node is encountered to perform the access, that is, to visit the left subtree first to visit the left subtree then to visit the right subtree, to visit the left subtree first to visit the right subtree, to visit the left subtree and right subtree first to visit the self.

Iteration implement

Almost all recursion can be changed to iteration. Recursion preserves the previous state, so we need a stack to help us save previously accessed nodes.

The former sequence traversal

One way to do this:

1. rootInto the stack
2. Loop until the stack is empty:
   1. Pop outtopAnd then visit
   2. top.rightInto the stack
   3. top.leftInto the stack

function preorderTraversal(root: TreeNode<T>) :void {
    const stack: TreeNode<T>[] = [];
    stack.push(root);
    while (stack.length) {
        const node = stack.pop();
        // visit(node);node.right && stack.push(node.right); node.left && stack.push(node.left); }}Copy the code

In the sequence traversal

This way to access the code into the above loop also becomes a pre-order traversal, I think this way is easier to think of and understand.

function inorderTraversal( root: TreeNode<T>) :void {
    const stack: TreeNode<T>[] = [];
    let node: TreeNode<T> | null = root;
    while (node || stack.length) {
        while (node) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        // visit(node);node = node.right; }}Copy the code

Post-order traversal is more difficult to think of as non-recursion, here is an idea:

We push it along the dotted line, where the root node is pushed first, and then the right child and the left child are pushed in a loop.

If such a binary tree to the last node in order to exit the stack is the order of the order traversal, but this is all the right subtree only have the root node, so in the loop need to determine the following each time is the loop need to continue the stack or exit access.

The criteria in the loop should be: the top of the stack node is a leaf node/the last node visited is a child of the top of the stack (if there is more than a root node in the right subtree).

The overall steps are:

1. rootInto the stack
2. Loop until the stack is empty:
   • If the top node is a leaf node/the last accessed node is a child of the top node
     • Pops the top node on the stack and accesses
   • Otherwise,
     • Put the top node on the stackright,leftInto the stack

function postorderTraversal(root: TreeNode<T>) :void {
    const stack: TreeNode<T>[] = [];
    stack.push(root);
    let prev: TreeNode<T> | null = null // The previous popup/accessed element
    while (stack.length) {
        const top = stack[stack.length - 1]; // stack.peek()
        if (top.isLeave() || (top.left === prev || top.right === prev)) {
            // visit(top);
            prev = stack.pop()
        } else{ top.right && stack.push(top.right); top.left && stack.push(top.left); }}}Copy the code

breadth-first

BFS uses queues to store and access nodes at the same level, and queues nodes at the next level.

function levelOrderTraversal(root: TreeNode<T>) {
    const queue: TreeNode<T> = [];
    queue.push(root); // enqueue
    while (queue.length) {
        const node = queue.shift(); // dequeue
        // visit(node);
        node.left && queue.push(node.left); // enqueue 
        node.right && queue.push(node.right); // enqueue}}Copy the code

Precursor node

The so-called precursor node is the previous node of a node in the middle order traversal.

It’s good for binary search trees to find the maximum of the left subtree, but it’s a little bit more difficult for normal binary trees.

• For a node with a left subtree, the preceding node in the middle traversal is the most of its left subtreeright, such as nodes 8, 4, 13 in the figure.
• For a node that does not have a left subtree
  • If there is a parent node and you can go all the way up to find the left fork, there is a precursor node, for example: 6, 10, 11
  • Otherwise, there is no precursor node, for example: 1

function predecessor(root: TreeNode<T>) :TreeNode<T> | null {
    Root.left. Right. Right.
    if (root.left) {
        let node = root.left;
        while (node.right) {
            node = node.right;
        }
        return node;
    }
    // If there is no left child node but there is a parent node, find the left fork
    while (root.parent && root === root.parent.left) {
        root = root.parent;
    }
    return root.parent;
}
Copy the code

The subsequent nodes

A successor node is similar to a precursor node in that it is the next node of a node traversed in middle order.

function successor(root: TreeNode<T>) :TreeNode<T> | null {
    if (root.right) {
        let node = root.right;
        while (node.left) {
            node = node.left;
        }
        return node;
    }
    // If there is no right child node but there is a parent node, find a fork to the right
    while (root.parent && root === root.parent.right) {
        root = root.parent;
    }
    return root.parent;
}
Copy the code

Binary search tree

Binary search tree definition:

• If the left subtree of any node is not empty, the values of all nodes in the left subtree are less than the values of its root node
• If the right subtree of any node is not empty, the values of all nodes in the right subtree are greater than the values of its root node
• The left and right subtrees of any node are binary search trees respectively

The more important operations for binary search trees are add and remove.

This is a recursive implementation, which can be implemented using iteration, especially if the parent attribute is defined in the node.

add

The operation is simple. If the value is greater than, the value is added to the right subtree, and if the value is less than, the value is added to the left subtree.

function insert(val: T) :void {
    this.root = this.add(this.root, val);
}

// Add val to a tree to return the root node of the tree
function add(root: TreeNode<T> | null, val: T) :TreeNode<T> {
    if (root === null) {
        root = new TreeNode(val);
    } else if (this.compare(val, root.val) < 0) {
        root.left = this.add(root.left, val);
        root.left.parent = root;
    } else if (this.compare(val, root.val) > 0) {
        root.right = this.add(root.right, val);
        root.right.parent = root;
    }
    return root;
}
Copy the code

delete

Deleting is a little more complicated than adding. It needs to be divided into 0, 1 and 2.

function remove(val: T) :void {
    this.root = this.delete(this.root, val);
}

// Delete a node in a tree, return the root node of the deleted tree
function delete(root: TreeNode<T> | null, val: T) :TreeNode<T> | null {
    if (root) {
        if (this.compare(val, root.val) < 0) {
            root.left = this.delete(root.left, val);
        } else if (this.compare(val, root.val) > 0) {
            root.right = this.delete(root.right, val);
        } else {
            if (root.isLeave()) { // If the degree is 0, delete yourself directly
                root = null;
            } else if (root.right && root.left) { // The degree is 2, find the precursor or successor node, delete the successor node here
                root.val = (<TreeNode<T>>this.successor(root)).val;
                root.right = this.delete(root.right, root.val);
            } else {  // Degree is 1, directly replace with child node
                if (root.left) {
                    root.left.parent = root.parent;
                    root = root.left;
                }
                if(root.right) { root.right.parent = root.parent; root = root.right; }}}}return root;
}
Copy the code