204 / InitiateStack s ; / s / i = n; t = p = new node; / */ p->data = postorder[i]; while i > q = new node; if parent[i - ] == postorder[i] S,T S

Size: px

Start display at page:

Download "204 */ InitiateStack s ; /* s */ i = n; t = p = new node; /* */ p->data = postorder[i]; while i > q = new node; if parent[i - ] == postorder[i] S,T S"

选氓扉洪
7 years ago
Views:

1 28 4 Vol.28 No JOURNAL OF NANTONG VOCATIONAL UNIVERSITY Dec. 204!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! doi:0.3969/j.issn 唐自立 ( 苏州大学计算机科学与技术学院, 江苏苏州 25006) : 提出一种新的由一棵严格二叉树的后序序列和结点的双亲情况构造该严格二叉树的非递归算法通过实例说明该算法的执行过程, 假设 n 是严格二叉树的结点的个数, 该算法的时间复杂度和最差情况空间复杂度都是 O(n) : 非递归算法 ; 严格二叉树 ; 后序序列 ; 结点的双亲 ; 严格二叉树构造 : TP30.6 : A : (204) A Non-recursive Algorithm for Constructing a Strictly Binary Tree from Its Post-order Traversal and the Parent of Each Node TANG Zi-li School of Computer Science and Technology, Soochow University, Suzhou 25006, China Abstract: A new non-recursive algorithm is presented for constructing a strictly binary tree from its post-order traversal and the parent of each node. The execution of the algorithm is illustrated by an example. Let n be the number of nodes of a strictly binary tree. The time complexity and the worst case space complexity of the algorithm are both O n. Key words: non-recursive algorithm; strictly binary tree; postorder traversal; parent of node; strictly binary tree construction [2] [] [2] [3-8] : : ( ); (0KJA52004); (BK202645); (BY2024) :

2 204 */ InitiateStack s ; /* s */ i = n; t = p = new node; /* */ p->data = postorder[i]; while i > q = new node; if parent[i - ] == postorder[i] S,T S Push s p ;,U T p->rightchild = q;, else U NULL; p->leftchild = q; p = q; p->data = postorder[--i]; p->leftchild = p->rightchild = NULL; DestroyStack s ; U 2 # n 7 U postorder[..7] parent[..7] v t a s v v b t c postorder[..7] parent[6] A =postorder A d preorder[..7] parent[5] C =postorder[6] ConstructSBT7 &t postorder[ ] parent[ ] n C C /* t postorder[..n] parent[..n] p ->leftchild = p ->rightchild = Pop s p ; BFGDECA ADDCCA# postorder [7] A [7] A A postorder[6] C C 94

3 4 parent[4] C postorder[5] E E postorder[2] F NULL C h preorder C [..7] parent[] postorder[4] D A postorder[2] F F f postorder[..7] NULL A parent [3] D =postorder parent [2] D pos- postorder[5] E e torder[3] G G postorder [..7] NULL D [4] D D postorder[] D B i preorder[..7] B postorder [3] G g preorder[..7] NULL j D A s k a b c d 95

4 204 e f g h 96

5 第4期唐自立由后序序列和结点的双亲情况构造严格二叉树的非递归算法 i j k 图 3 实例执行过程算法分析假设 n n 是一棵严格二叉树的结点的个数那么 n 一定是正奇数[ 8 ] 在时间开销上由于执行算法时要循环 n - 次而每循环一次都要花费 O 时间则执行算法总共要花费 O n 时间因此算法的时间复杂度是 O n 在空间开销上当所构造的严格二叉树有以 97

6 ,28(6): tree from its traversals n- / 2 O n 992,42(2):7-9. O n 4 989,29(3): O n [2] BIT,989,29(2): Systems,996,7(2): : [] Knuth D E. The art of computer programming,vol.,fundamental algorithms [M]. 3rd ed. Reading,MA:Addison-Wesley, 997. [2] 唐自立. 基于遍历序列的唯一确定树或二叉树的方法 [J]. 小型微型计算机系统,200,22(8): [3] Andersson A,Carlsson S. Construction of a tree from its traversals in optimal time and space[j]. Information Processing Letters, 990,34():2-25. [4] Burgdorff H A,Jajodia S,Springsteel F N,et al. Alternative methods for the reconstruction of trees from their traversals [J]. BIT,987,27(2): [5] Chen G H,Yu M S,Liu L T. Two algorithms for constructing a binary tree from its traversals [J]. Information Processing Letters, [6] Gabrani N,Shankar P. A note on the reconstruction of a binary [J]. Information Processing Letters, [7] Kamakoti V,Rangan C P. An optimal algorithm for reconstructing a binary tree[j]. Information Processing Letters,992,42(2): 3-5. [8] M 覿 kinen E. Constructing a binary tree from its traversals[j]. BIT, [9] M 覿 kinen E. Constructing a binary tree efficiently from its traversals [J]. International Journal of Computer Mathematics,2000,75 (2): [0] Olariu S,Overstreet M,Wen Z F. Reconstructing a binary tree from its traversals in doubly logarithmic CREW time[j]. Journal of Parallel and Distributed Computing,995,27(): [] Slough W,Efe K. Efficient algorithms for tree reconstruction[j]. [2] Stojmenovic I. Constant time BSR solutions to parenthesis matching, tree decoding, and tree reconstruction from its traversals [J]. IEEE Transactions on Parallel and Distributed [3] Wen Z F. New algorithms for the LCA problem and the binary tree reconstruction problem [J]. Information Processing Letters, 994,5():-6. [4] Xiang L M,Lawi A,Ushijima K. On constructing a binary tree from its traversals [J]. Research Reports on Information Science and Electrical Engineering of Kyushu University,2000,5(): 3-8. [5] 唐自立. 基于遍历序列的构造二叉树的算法 [C]// 全国计算机技术应用与高等学校计算机教育论文集 ( 第卷 ), 成都 : 西南交通大学出版社,2009: [6] 唐自立. 基于遍历序列的构造严格二叉树的算法 [J]. 苏州大学学报 : 自然科学版,200,26(3): [7] 唐自立. 基于遍历序列的构造树的算法 [J]. 苏州大学学报 : 自然科学版,20,27(3): [8] 唐自立. 由先序序列和结点的左孩子情况构造严格二叉树的高效算法 [J]. 南通大学学报 : 自然科学版,203,2():

1

1 2 EI ( 2005) 3 EI ( 2005) 4 2006 3 1 2 3 EI ( 2005) http://www.ei.org.cn/twice/coverage.jsp ISSN 0567-7718 Acta Mechanica Sinica/Lixue Xuebao 1006-7191 Acta Metallurgica Sinica (English Letters) 0253-4827