摘要
针对一维数组中求最长升序序列问题,在研究树形结构和分析任务需求的基础上,提出采用区别于传统树的逆序树结构进行计算,采用深度优先算法策略查找路径。逆序树采用子节点指向父节点的节点逆序指向方式,在建树过程中不用为每个节点考虑子节点的数量,克服了不可预见的存储分配和节点指向问题,能有效地找出全部升序路径,最终找出一维数组中全局最长的升序序列。在此基础上实现的Java程序验证了逆序树结构的有效性。
Aiming at the problem of finding the longest ascending sequence in one .dimensional array, the tree data structure is studied, and the reverse tree which is different from the traditional tree, is proposed. Depth-first strategy in algorithm design is applied. Reverse tree means that son node points to father node. Using it to build tree, the program no longer needs to care about the counts of every node＇s children, the unforeseeable storage allocation and node point. It can easily find out all ascending sequences, and global longest ascending sequences. Java program based on this proves that the reverse tree is effective.
出处
《计算机时代》
2013年第3期37-38,41,共3页
Computer Era
关键词
逆序树
传统树
节点
深度优先
最长升序序列
reverse tree
traditional tree
node
depth first
the longest ascending seq.uence
