Halo

A magic place for coding

0%

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.

And its implementations:

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.

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.

BinaryTree(const BinaryTree< Entry > &original)

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

recursive_copy(Binary_node< Entry > *sub_root)

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

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

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

~BinaryTree()

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

empty()

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

size()

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

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.

height()

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

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.

width()

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

leaf_count()

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

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.

precondition: None.
postcondition: Clean the BinaryTree itself.

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.

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

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

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.

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

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

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.

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

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

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.

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).

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.

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).

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

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

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.

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

Welcome to my other publishing channels