## Introduction

*Linked Lists* have great advantages of flexibility over the contiguous representation of data structure, but they have one weakness: They are sequential lists; that is, they are arranged so that it is necessary to move through them only one position at a time. In this post, we can overcome this problem by using **trees** as data structure, with methods of pointers.

### Definition

A **binary tree** is either empty, or it consists of a node called the **root** together with two binary trees called the **left subtree** and the **right subtree** of the root.

Noted that **binary trees** are not the same class as the **2-trees**. Each node in a **2-tree** has either 0 or 2 children, never 1, as can happen with a **binary tree**.

For **n** nodes, here I give a formular to calculate the number of different binary trees:

$$ \cfrac {C_{2n}^{n}}{n+1} $$

### Tree Traversal

#### What is the order?

**Traversal**, moving through all the nodes of the binary tree, visiting each node in turn, is one of the most important operations on a binary tree.

For lists or other data structures we’ve mentioned previously, the **traversal** operation follows the same order. However, for trees, there are several orders in which we could traverse all the nodes.

At a given node, then, there are three tasks we shall wish to do in some order: We shall visit the node **itself**, we shall traverse its **left subtree***; and we shall traverse its **right subtree**. The key distinction in traversal orders is to decide which node we should visit first, among **the node itself**, **its left subtree**, and **its right subtree**.

#### Standard Traversal Orders

For a traversal task, we denote that a node **V**, its left subtree **L**, and its right subtree **R**. So there are **3** orders we may have:

preorder | inorder | postorder |
---|---|---|

VLR |
LVR |
LRV |

#### Expression Trees

An **expression tree** is built up from the simple operands and operators of an (arithmetical or logical) expression by placing the simple operands as the leaves of a binary tree and the operators as the interior nodes.

For each **binary operator**, the left subtree contains all the simple operands and operators in the left operand of the given operator, and the right subtree contains everything in the right operand.

For a **unary operator**, one of the two subtrees will be empty.

#### Polish Form

The names of the traversal methods are related to the **Polish forms** of the expression. Traversal of an expression tree in **preorder** yields the **prefix form**, in which every operator is written before its operands; **inorder** traversal gives the **infix form**(the customary way that we use in daily life); and **postorder** traversal gives the **postfix form**, in which all operators appear after their operands. Although we may consider the **infix form** convenient to use, the computer prefer a **postfix form** expression, **Reverse Polish** expression to calculate. I will show you how to convert a **infix form** to a **postfix form** and calculate it in another post, but not here.

Expression | a+b | log x | n ! | a-(b×c) | (a<b) or (c<d) |
---|---|---|---|---|---|

preorder | + a b | log x | ! n | - a × b c | or < a b < c d |

inorder | a + b | log x | n ! | a - b × c | a < b or c < d |

postorder | a b + | x log | n ! | a b c × - | a b < c d < or |

### Implementation

First we consider the representation of the nodes that make up a tree. We define a structure **Binary_node**, which has both a left and a right subtree.

1 | template <class Entry> |

And its implementations:

1 | template <class Entry> |

Now we can start to construct a tree. For convenience, here we give most methods that a tree need, but not necessary to implement them right now. This provides us a bluprint to construct any binary tree.

1 | template <class Entry> |

It seems a bit more complex but just relax. I’ll explain it in details. At first, functions like **height**, **size**, and **clear** are basic functions that tell us some features of a tree. They all can be implemented easily by using recursions. So they have their corresponding auxiliary functions in the **protected field**.

Now we move to see the traversal functions. As I’ve introducted that there are 3 standard traversal orders, there are certainly **three traversal functions**. And of course, they have their corresponding auxiliary functions as well.

Noted that the **insert** function here is used to test our basic tree class, it will be overrided when BST or other trees are implemented.

#### BinaryTree ()

*precondition*: None.*postcondition*: The *BinaryTree* has been created and is initialized to be empty.

1 | template <class Entry> |

#### BinaryTree (**const** BinaryTree< Entry > &original)

*precondition*: None.*postcondition*: The *BinaryTree* has been created and is initialized with *BinaryTree* original.

1 | template <class Entry> |

#### recursive_copy (Binary_node< Entry > *sub_root)

*precondition*: None.*postcondition*: Return a node that is initialized with sub_root.

1 | template <class Entry> |

#### BinaryTree& operator=(**const** BinaryTree< Entry > &original)

*precondition*: None.*postcondition*: The *BinaryTree* is reset to copy original.

1 | template <class Entry> |

#### ~BinaryTree ()

*precondition*: None.*postcondition*: The *BinaryTree* itself is released.

1 | template <class Entry> |

#### empty ()

*precondition*: None.*postcondition*: The function returns **true** or **false** according to whether the *BinaryTree* is empty or not.

1 | template <class Entry> |

#### size ()

*precondition*: None.*postcondition*: Return the number of entries in the *BinaryTree*.

1 | // 计算节点个数 |

#### recursive_size (Binary_node< Entry > *sub_root)

*precondition*: sub_root is either NULL or points to a subtree of the *BinaryTree*.*postcondition*: Return the number of entries in the subtree rooted at sub_root.

1 | template <class Entry> |

#### height ()

*precondition*: None.*postcondition*: Return the height of the *BinaryTree*.

1 | // 计算树高 |

#### recursive_height (Binary_node< Entry > *sub_root)

*precondition*: sub_root is either NULL or points to a subtree of the *BinaryTree*.*postcondition*: Return the height of the subtree.

1 | template <class Entry> |

#### width ()

*precondition*: None.*postcondition*: Return the width of the *BinaryTree*.

1 | template <class Entry> |

#### leaf_count ()

*precondition*: None.*postcondition*: Return the number of leaves in the *BinaryTree*.

1 | // 计算叶子节点个数 |

#### recursive_leaf_count (Binary_node< Entry > *sub_root)

*precondition*: sub_root is either NULL or points to a subtree of the *BinaryTree*.*postcondition*: Return the number of leaves in the subtree rooted at sub_root.

1 | template <class Entry> |

#### clear ()

*precondition*: None.*postcondition*: Clean the *BinaryTree* itself.

1 | template <class Entry> |

#### recursive_clear (Binary_node< Entry > *&sub_root)

*precondition*: sub_root is either NULL or points to a subtree of the *BinaryTree*.*postcondition*: The subtree has been cleaned.

1 | template <class Entry> |

#### preorder (void (*visit)(Entry &))

*precondition*: None.*postcondition*: Traverse the *BinaryTree* in preorder.

1 | template <class Entry> |

#### recursive_preorder (Binary_node< Entry > *sub_root, void (*visit)(Entry &))

*precondition*: sub_root is either NULL or points to a subtree of the *BinaryTree*.*postcondition*: The subtree has been been traversed in preorder sequence.

1 | template <class Entry> |

#### inorder (void (*visit)(Entry &))

*precondition*: None.*postcondition*: Traverse the *BinaryTree* in inorder.

1 | template <class Entry> |

#### recursive_inorder (Binary_node< Entry > *sub_root, void (*visit)(Entry &))

*precondition*: sub_root is either NULL or points to a subtree of the *BinaryTree*.*postcondition*: The subtree has been been traversed in inorder sequence.

1 | template <class Entry> |

#### postorder (void (*visit)(Entry &))

*precondition*: None.*postcondition*: Traverse the *BinaryTree* in postorder.

1 | template <class Entry> |

#### recursive_postorder (Binary_node< Entry > *sub_root, void (*visit)(Entry &))

*precondition*: sub_root is either NULL or points to a subtree of the *BinaryTree*.*postcondition*: The subtree has been been traversed in postorder sequence.

1 | template <class Entry> |

#### insert (**const** Entry &)

*precondition*: None.*postcondition*: If the *root* is empty, the new entry should be inserted into the *root*, otherwise it should be inserted into the shorter of the two subtrees of the *root*(or into the left subtree if both subtrees have the same height).

1 | // 插入 |

#### recursive_insert (Binary_node< Entry > *&sub_root, **const** Entry &x)

*precondition*: sub_root is either NULL or points to a subtree of the *BinaryTree*.*postcondition*: If subroot is n NULL, x is inserted to this subtree; else, move to left or right subtree.

1 | template <class Entry> |

#### double_traverse (void (*visit)(Entry &))

*precondition*: None.*postcondition*: At each node of the *BinaryTree*, **double-order traversal** function first visits the node, then traverses its left subtree (in double order), then visits the node again, then traverses its right subtree (in double order).

1 | // 双重遍历 |

#### recursive_double_traverse (Binary_node *sub_root, void (*visit)(Entry &))

*precondition*: None.*postcondition*: The subtree rooted at sub_root is doubly traversed.

1 | template <class Entry> |

#### level_traverse (void (*visit)(Entry &))

*precondition*: None.*postcondition*: The *BinaryTree* is traversed level by level, starting from the top. The operation *visit is applied to all entries.

1 | template <class Entry> |

That’s the general introduction of **BinaryTree**. In next post, I’ll introduce another useful tree structure to you. Thank you!