Data Structure and Algorithm Analysis

Properties of Binary Tree

On a binary tree, there are some important properties:

There are at most 2 ^ (i − 1) nodes on layer i (i ∈ N)

A tree with a hierarchy of k (k ∈ N) can have at most 2 ^ k − 1 nodes

If the number of leaf nodes is n0, and the number of nodes with degree=2 is n2, then n0=n2+1

If each layer of a binary tree is filled, the binary tree is called a full binary tree; If the binary tree is full except the last layer, and the last layer is either full, or the right side lacks a number of consecutive nodes, the binary tree is called a complete binary tree.

Because full binary tree and complete binary tree are special binary trees, they also have some deterministic properties. Let's assume that the number of summary points is k, the height of the tree (that is, the number of layers of the tree) is h, and one of the layers is layer i, then it has the following properties:

Implementation of binary tree

In order to implement a binary tree, we can use a two-way linked list structure for it, but it is no longer the prev and next that point to the node, but the left child and right child that point to the node.

struct BinaryTreeBaseNode {

BinaryTreeBaseNode* left,* right;

};

template

struct BinaryTreeNode : BinaryTreeBaseNode {

Element data;

};

Here we give the height and depth of node in the solution of binary tree root

If you want to solve some data from the node upward, it is not easy to do so, because the child does not have a pointer to the parent, you need to traverse the tree to find the parent of the node.

To facilitate the implementation, we will naturally add a pointer to the parent in the chain domain. In this way, it is very convenient to solve the problem of sibling and uncle, and it is no longer necessary to equate the node depth to the path length from root to node. Note that root has no parent.

Traversal of binary tree

Remember the previously mentioned postmorter traversal and preorder traversal, which are also applicable to binary trees. But don't worry. Now that the number of children is determined, can you put the node processing between two nodes? Of course, no problem. This processing method is inorder traversal, which is also a kind of DFS.

If the current node is marked as N, the left child node is marked as L, and the right child node is marked as R, then the pre order traversal can be expressed as NLR, the middle order traversal can be expressed as LNR, and the post order traversal can be expressed as LRN.

In the subsequent traversal, after the left sub node is processed, the node can be processed only when there is no right sub node or the right sub node is processed. Therefore, it is necessary to determine whether the right child of the current node is empty or whether the node that has just been processed is the right child of the node. It is very simple to judge whether the right sub node is empty, but the problem is how to record the nodes that have just been visited?

A variable is used to point to the node being processed. When it points to the next node to be processed, its value is the previous processing node of the node, that is, the processing precursor.

A heterogeneous preorder traversal

If you flip a word string, there is a simple and feasible method: first flip the word string as a whole, and then flip it word by word. In this way, you will get a reversal of the word string!

This heterogeneous inversion can also be used in the DFS traversal of the binary tree. The node order of the previous traversal is NLR (Node ->Left ->Right), while the node order of the subsequent traversal is LRN. The sequence of the subsequent traversal is reversed to NRL. If we traverse in NRL order, we can finally flip the results to get a sequence of post order traversal, which is essentially a heterogeneous pre order traversal.

Sequence traversal of binary tree

DFS is naturally combined with stack, while BFS is combined with queue. Therefore, for the above three DFS traversals, using recursion is a simple and efficient understanding and coding, while sequence traversal is more suitable for loop.

Morris traversal

In the three DFS traversals described above, both recursion and loop implementations require O (N) time complexity and O (N) space complexity. In 1979, J.H. Morris proposed a traversal method in his paper, which can use the time complexity of O (N) and the space complexity of O (1) to complete the traversal. Its core idea is to reduce the space complexity by using the idle pointer in the binary tree.

Take poster as an example to illustrate the specific idea of its algorithm:

If the left subtree of the current node is empty, the right subtree will be traversed

If the left subtree of the current node is not empty, find the predecessor node of the current node in the middle order traversal in the left subtree of the current node

If the right child node of the predecessor is empty, set the right child node of the predecessor node as the current node, and update the current node to its left child node

If the right child node of the predecessor is the current node, it will be re empty. All nodes on the path from the left child of the current node to the predecessor node are processed in reverse order. Update the current node to the right child of the current node

Repeat steps 1 and 2 until the traversal ends

iterator

Since you can traverse a tree, you still want to pause in the tree, perform some operations on the nodes, and then continue to iterate. When we choose different traversal methods, the predecessor and successor of the iteration are different.

If an iterator is given now, how to find the predecessor and successor iterators of the iterator. The algorithm steps and code for solving the precursor of the middle order traversal are given here. The algorithm for solving the successor of the middle order traversal is similar to the predecessor's algorithm, so only the code is given.

Solve the precursor

If the left subtree of a node exists, the predecessor is the largest node on the left subtree of the node

If the left subtree of the node does not exist, you need to find the parent of the node

If the node is a node on the right subtree of the parent, the parent is its predecessor

If the node is a node on the left subtree of a parent, continue to search upward until the parent is null ptr or a node on the right subtree of its parent

Example: Expression tree

The following figure shows an expression tree. Leaf node is the operand and internal node is the operator. Since all operations are binary, this tree is a binary tree. The operand of each operator is the operation result of its two subtrees.

The expression corresponding to this tree is a+b ∗ c+(d ∗ e+f) ∗ g. If we post the tree, we will get the sequence abc ∗+de ∗ f+g ∗+, which is a suffix expression; If you preorder traversal it, you will get the prefix expression++a ∗ bc ∗+∗ defg; Finally, try inorder traversal. The result should be an infix expression, but its sequence is not bracketed.

From the results of the poster trailer, you can easily build this tree. It is left to the reader for implementation, and will not be explained here.