Designing on a Special Algorithm of Triple Tree Based on the Analysis of Data Structure - Advanced Research on Computer Education, Simulation and Modeling - page 425

The design ideas of computing the number of descendant nodes of each node in the
triple tree using the preorder traversal procedure aforementioned are as follows:
The procedure starts from the root node, and terminates when the tree is NULL. If
it wasn't terminated, it then needs to determine whether the root node has a left child.
The field DescNum of root node will be increased by one if the answer is yes, and
then a new procedure which computes the number of descendant nodes will start from
the left subtree of the root node. This procedure uses the same method to modify field
DescNum of the root node of the left subtree. Next, the same way used to determine
the middle subtree and the right subtree of the root node of the original triple tree, and
modify the DescNum fields of the root nodes of the two subtrees. Finally, the number
of descendant nodes of the root node eaquals to the sum of the modified DescNum
field of the root node and the other three DescNum fields of the root nodes of the
subtrees of the root node.
The concret steps of the algoritnm are as follows:
(1) If the triple tree is empty, the algorithm will terminate and return;
(2) Otherwise, follow these steps to continue:
① If the left child of the root node exists, the DescNum field of the root node
will be increased by 1. Then, starting from the root node of the left subtree,
the recursive preorder traversal procedure will be executed to compute the
number of descendant of the left child of the root node;
② If the middle child of the root node exists, the DescNum field of the
root node will be increased by 1. Then, starting from the root node of
the middle subtree, the recursive preorder traversal procedure will be
executed to compute the number of descendant of the middle child of the
root node;
③ If the right child of the root node exists, the DescNum field of the root node
will be increased by 1. Then, starting from the root node of the right subtree,
the recursive preorder traversal procedure will be executed to compute the
number of descendant of the right child of the root node;
④ Finally, the DescNum field of the root node adds the three DescNum fields of
its children (left, middle, and right nodes).

4.2 Algorithm Description in C

Suppose that the triple tree adopts the triple linked list storage structure TripleTree
mentioned before, and the root pointer points to it. The recursive design ideas of this
algorithm can be described in C is as follows:

void NumberofChildren(TripleTree *root)
{ if(!*root) return;

//Return when the tree is empty

if((*root)->Lchild)
{ NumberofChildren(&((*root)->Lchild));
(*root)->DescNum++; }//End_if
if((*root)->Mchild)
{ NumberofChildren(&((*root)->Mchild));
(*root)->DescNum++; }//End_if
if((*root)->Rchild)
{ NumberofChildren(&((*root)->Rchild));