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

represents the number of descendants of this parent node. The initial value of field
DescNum in each node is 0. It needs to compute the number of descendant nodes of
each node in the triple tree, and store the numbers into the field DescNum in each
node.

3 Data Structure Definition

According to the meaning of problems, the node structure of the triple linked list is
shown as Fig.1.

DescNum Lchild Mchild Rchild

Fig. 1. The node structure of the triple linked list

The node type can be defined in C as follows:
typedef struct TriNode{
unsigned DescNum;
struct TriNode *Lchild,*Mchild,*Rchild;
} TriNode, *TripleTree;
Since the triple tree adopted the specified storage structure mentioned above, the
algorithm below will be designed based on it.

4 Algorithm Design and Implementation

To imagine the triple tree is an inverted tree, and the root node locates in the first
layer, then the descendants of a certain node are all the nodes of the subtree of this
node.

4.1 Algorithm Design Ideas

The algorithm of computing the number of descendant nodes of each node in the
triple tree can be implemented through the procedure of triple tree preorder traversal.
The triple tree preorder traversal can be described as follows:
(1) If the triple tree is empty, the algorithm will terminate and return;
(2) Otherwise, follow these steps to visit the tree nodes:
① Visit the root node of the triple tree;
②

Preorder traverse the left subtree of the root node while the left child of the
root node exists;
③ Preorder traverse the middle subtree of the root node while the middle child
of the root node exists;
④ Finally, Preorder traverse the right subtree of the root node while the right
child of the root node exists.