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

(*root)->DescNum++; }//End_if
(*root)->DescNum+=(*root)->Lchild->DescNum;
(*root)->DescNum+=(*root)->Mchild->DescNum;
(*root)->DescNum+=(*root)->Rchild->DescNum;
}//End
4.3 Algorithm Evaluation
The returned result of each recursive calling does not be saved, so it must be
computed once more whenever needed, this leads to the time complexity of recursive
functions actually depend on the times of recursive calling [4-6].
This paper adopted the recursive function NumberofChildren() to describe the
algorithm, the first calling begin with the root of the triple tree. Since this function
includes three recursive calling statements, the times of recursive calling is actually
the sum of the number of nodes in the forest and the number of null pointers. An n
nodes triple linked list has 3 n pointers, where there are n 0 =2n+1 null pointers, and
then the total number of recursive calling is 3 n +1 times [6]. Regarding the number
( n ) of nodes in the forest as the scale of the problem, and with the gradually increase
of problem scale, the algorithm time complexity is nearly T(n) = O ( 3n+1) .
In addition to the storage space used by the function itself and the tree nodes,
function NumberofChildren() introduced no assistant space, so the algorithm space
complexity is constant order, that is S(n)=O(1) .
5 Conclusion
The procedure of analyzing and designing the algorithm of computing the number of
descendant nodes of each node in the triple tree based on the data structure was
introduced in detail in this paper. After the recursive algorithm description in C had
been given, the algorithm was evaluated from the two aspects of time complexity and
space complexity. Therefore, this work plays a guiding role in teaching the relevant
chapters in “Data Structure” curriculum.
Acknowledgments. This work is supported by Research Fund of Weinan Teachers
University (No. 11YKS014) and Graduate Special Fund of Weinan Teachers
University (No. 09YKZ012).
References
1. Wang, W.: Data Structure Learning guidance. Electronic Science and Technology
University Press, Xi'an (2004)
2. Yan, W., Wu, W.: Data Structures(C language edition). Tsinghua University Press, Beijing
(2002)
3. Geng, G.: Data Structure—C Language description. Electronic Science and Technology
University Press, Xi'an (2005)