پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 158 |
| تعداد شماره‌ها | 6,230 |
| تعداد مقالات | 67,757 |
| تعداد مشاهده مقاله | 115,115,148 |
| تعداد دریافت فایل اصل مقاله | 89,881,969 |
An improved algorithm to reconstruct a binary tree from its inorder and postorder traversals | ||
| Journal of Algorithms and Computation | ||
| مقاله 9، دوره 49، شماره 1، شهریور 2017، صفحه 93-113 اصل مقاله (442.04 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2017.7987 | ||
| نویسندگان | ||
| Niloofar Aghaieabiane1؛ Henk Koppelaar2؛ Peyman Nasehpour* 3 | ||
| 1Department of Engineering, School of Computer Science, New Jersey Institute of Technology, Newark, New Jersey, the USA. | ||
| 2Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands. | ||
| 3Golpayegan University of Technology, Department of Engineering Science, Golpayegan, Iran. | ||
| چکیده | ||
| It is well-known that, given inorder traversal along with one of the preorder or postorder traversals of a binary tree, the tree can be determined uniquely. Several algorithms have been proposed to reconstruct a binary tree from its inorder and preorder traversals. There is one study to reconstruct a binary tree from its inorder and postorder traversals, and this algorithm takes running time of $ \BigO{\emph{n}^2} $. In this paper, we present $ \proc{InPos} $ an improved algorithm to reconstruct a binary tree from its inorder and postorder traversals. The running time and space complexity of the algorithm are an order of $ \BigTheta{\emph{n}} $ and $ \BigTheta{\emph{n}} $ respectively, which we prove to be optimal. The $ \proc{InPos} $ algorithm not only reconstructs the binary tree, but also it determines different types of the nodes in a binary tree; nodes with two children, nodes with one child, and nodes with no child. At the end, the $ \proc{InPos} $ returns a matrix-based structure to represent the binary tree, and enabling access to any structural information of the reconstructed tree in linear time with any given tree traversals. | ||
| کلیدواژه‌ها | ||
| Binary tree؛ Preorder traversal؛ Inorder traversal؛ Postorder traversal؛ time complexity؛ Space complexity | ||
|
آمار تعداد مشاهده مقاله: 505 تعداد دریافت فایل اصل مقاله: 419 |
||