Information Technology Reference
In-Depth Information
Designing on a Special Algorithm of Triple Tree Based on
the Analysis of Data Structure
Min Wang and Yunfei Li
Computer Science Department, Weinan Teachers University, Weinan, Shanxi, China
wntcwm@126.com
Abstract. This paper introduces in detail the design and analysis of the
algorithm of computing the number of descendant nodes of each node in
the triple tree based on analyzing the special storage structures of triple tree.
The recursive algorithm description in C is introduced subsequently after the
design ideas, the implementation methods, and the concrete steps of the
algorithm were given. Finally, the algorithm is evaluated from the two aspects
of time complexity and space complexity.
Keywords: Triple tree; Descendant; The triple tree preorder traversal;
Recursive algorithm; Time complexity; Space complexity.
1 Introduction
Data structure and Algorithms are important and basic subjects in computer science,
and they are an indivisible whole. The procedure of computer solving problem follow
such steps that inputting the initial data, processing by the computer, and then
outputting the information. For a given problem, it is essential to decide how to
organize the initial data, how to store them in the computer, and how to choose and
design appropriate algorithms for it. To solve a particular problem, it needs to analyze
the problem at first, and then combine organically the data structure and algorithms.
To solve the problem effectively, algorithms must adopt suitable data structures [1].
This paper will design the algorithm of computing the number of descendant nodes
of each node in the triple tree, analyze in detail the approaches and steps for problem
solving by analyzing the basic data structure of the triple tree, give the recursive
algorithm description in C, and analyze and evaluate the algorithm time complexity
and space complexity.
2 Problem Description of the Triple Tree
The problem to be solved is described as follow:
Known that the triple tree T has a special triple list storage structure, and each node
of it includes four fields, that are lchild , mchild , rchild and DescNum . Where, fields
lchild , mchild and rchild are point respectively the left, the middle and the right child
node of this parent node; while the field DescNum is a non-negative integer that
 
Search WWH ::




Custom Search