调整Construct()函数 [英] Adjust construct() function

问题描述

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
 
def construct(start, end, preorder, pIndex, dict):
 
    # base case
    if start > end:
        return None, pIndex
 
    root = Node(preorder[pIndex])
    pIndex = pIndex + 1
 
    index = dict[root.data]
 
    root.left, pIndex = construct(start, index - 1, preorder, pIndex, dict)
 
    root.right, pIndex = construct(index + 1, end, preorder, pIndex, dict)
 
    return root, pIndex     

def constructTree(inorder, preorder):
 
    dict = {}
    for i, e in enumerate(inorder):
        dict[e] = i
 
    pIndex = 0
 
    return construct(0, len(inorder) - 1, preorder, pIndex, dict)[0]
 
 
if __name__ == '__main__':
 
 
    inorder = [4, 2, 1, 7, 5, 8, 3, 6]
    preorder = [1, 2, 4, 3, 5, 7, 8, 6]
 
    root = constructTree(inorder, preorder)
 
    print("The inorder traversal is ", end='')
    inorderTraversal(root)
 
    preorderTraversal(root)

此代码构造一个具有预遍历和有序遍历的树.如何修改该代码以使其适用于有序订单和后订单订单?我想我只需要以类似的方式修改 construct()并创建 constructPreOrderInOrderTree()和 constructPreOrderPostOrderTree().

This code constructs a tree with the preorder and inorder traversal. How can I modify that code to make it work for inorder-postorder and preorder-postorder? I guess I just have to modify construct() and create constructPreOrderInOrderTree() and constructPreOrderPostOrderTree() in a similar manner.

编辑

假设我有 inorder = [3、7、1、10、9、5、8、6、4、2] 和 postorder = [3、7、10、9，1、8、4、6、2、5] . construct()可以按顺序进行此操作，但不适用于该示例.因此，我需要该功能的一个版本，该版本可以同时用于订单后订单和订单后订单.

Suppose I have inorder=[3, 7, 1, 10, 9, 5, 8, 6, 4, 2] and postorder = [3, 7, 10, 9, 1, 8, 4, 6, 2, 5]. construct() would do that for inorder-preorder, but it is not adapted for that example. So I need a version of that function which would work with both inorder-postorder and preorder-postorder.

推荐答案

即使不阅读Geeks-for-Geeks页面，我也决定实现自己的构造函数算法(preorder-postorder，preorder-inorder，inorder-postorder).

Without even reading Geeks-for-Geeks pages I decided to implement my own algorithms for construction functions (preorder-postorder, preorder-inorder, inorder-postorder).

我所有的算法都是 O(N ^ 2)复杂度.

All my algorithms are O(N^2) complexity.

除了构造函数( construct_preorder_postorder()， construct_preorder_inorder()， construct_inorder_postorder())之外，我还实现了遍历功能( traverse_preorder()， traverse_inorder()， traverse_postorder())，控制台树打印功能( print_tree())和节点相等性比较函数( __ eq __()).

Besides construction functions (construct_preorder_postorder(), construct_preorder_inorder(), construct_inorder_postorder()) I also implemented traversing functions (traverse_preorder(), traverse_inorder(), traverse_postorder()), console tree printing function (print_tree()) and Node equality comparison function (__eq__()).

输出:

     /--6
  /--3
  |  |  /--8
  |  \--5
  |     \--7
--1
  \--2
     \--4

这篇关于调整Construct()函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！