28 4 Vol.28 No.4 4 204 2 JOURNAL OF NANTONG VOCATIONAL UNIVERSITY Dec. 204!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! doi:0.3969/j.issn.008-5327.204.04.024 唐自立 ( 苏州大学计算机科学与技术学院, 江苏苏州 25006) : 提出一种新的由一棵严格二叉树的后序序列和结点的双亲情况构造该严格二叉树的非递 归算法通过实例说明该算法的执行过程, 假设 n 是严格二叉树的结点的个数, 该算法的时间复杂度 和最差情况空间复杂度都是 O(n) : 非递归算法 ; 严格二叉树 ; 后序序列 ; 结点的双亲 ; 严格二叉树构造 : TP30.6 : A : 008-5327(204)04-0093-06 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] : 204-09-8 : (6075040); (0KJA52004); (BK202645); (BY2024) : 965-93
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
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
204 e f g h 96
第4期 唐自立 由后序序列和结点的双亲情况构造严格二叉树的非递归算法 i j k 图 3 实例执行过程 算法分析 假设 n n 是一棵严格二叉树的结点的 个数 那么 n 一定是正奇数[ 8 ] 在时间开销上 由于执行算法 时要循环 n - 次 而每循环一次都要花费 O 时间 则执 行算法 总共要花费 O n 时间因此 算法 的 时间复杂度是 O n 在空间开销上 当所构造的严格二叉树有以 97
204 988,28(6):297-299. tree from its traversals n- / 2 O n 992,42(2):7-9. O n 4 989,29(3):572-575. O n [2] BIT,989,29(2):36-363. Systems,996,7(2):28-224. : [] Knuth D E. The art of computer programming,vol.,fundamental algorithms [M]. 3rd ed. Reading,MA:Addison-Wesley, 997. [2] 唐自立. 基于遍历序列的唯一确定树或二叉树的方法 [J]. 小型 微型计算机系统,200,22(8):985-988. [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):34-40. [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):43-47. [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():00-05. [] 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:394-397. [6] 唐自立. 基于遍历序列的构造严格二叉树的算法 [J]. 苏州大学学报 : 自然科学版,200,26(3):40-43. [7] 唐自立. 基于遍历序列的构造树的算法 [J]. 苏州大学学报 : 自 然科学版,20,27(3):26-29. [8] 唐自立. 由先序序列和结点的左孩子情况构造严格二叉树的高效算法 [J]. 南通大学学报 : 自然科学版,203,2():9-3. 98