白駿5639

2905 ワード

これは白俊5639号バイナリナビゲーションツリーの巡回問題です.


バイナリ・ナビゲーション・ツリーの場合、ルート・ノードより小さい場合は左、より大きい場合は右.
したがって、入力が先頭順であれば、上記のバイナリナビゲーションツリーの基本概念を用いて挿入すると、上図の画像と同じ入力が作成されます.
  • 入力値をバイナリプローブツリーに順次挿入します.
  • 後列巡視を行う.
  • コードでは前列、中列、後列のループも実現していますので、参考にしてください.
    import sys
    sys.setrecursionlimit(10000)
    
    class Node():
        root = None
        left = None
        right = None
        def __init__(self,root):
            self.root = root
            
    class binarySerchTree:
        
        def __init__(self):
            self.node=None
            self.preOrderList= []
            self.postOrderList = []
            self.inOrderList = []
            
        def insert(self, data):
            if ( self.node == None):
                self.node = Node(data)
            else:
                self.__addNode(self.node, data)
                
        def __addNode(self, node , data):
            if ( data <= node.root ):
                if ( node.left == None):
                    node.left = Node(data)
                else:
                    self.__addNode(node.left, data)
            else:
                if ( node.right == None):
                    node.right = Node(data)
                else:
                    self.__addNode(node.right, data)
                    
                    
        def inOrder(self):
            if ( self.node == None):
                return False
            self.__inOrder(self.node)
            return self.inOrderList
        
        def __inOrder(self, node):
            if ( node == None):
                return False
            self.__inOrder(node.left)
            self.inOrderList.append(node.root)
            self.__inOrder(node.right)
                    
        def postOrder(self):
            if ( self.node == None):
                return False
            self.__postOrder(self.node)
            return self.postOrderList
        
        def __postOrder(self, node):
            if ( node == None):
                return False
            self.__postOrder(node.left)
            self.__postOrder(node.right)
            self.postOrderList.append(node.root)
            
                
        def preOrder(self):
            if ( self.node == None):
                return False
            self.__preOrder(self.node)
            tmp = self.preOrderList
            self.preOrderList = []
            return tmp
        
        def __preOrder(self, node):
            if ( node == None):
                return False
            self.preOrderList.append(node.root)
            self.__preOrder(node.left)
            self.__preOrder(node.right)
            
    tree = binarySerchTree()
    while(True):
        try:
            tree.insert(int(input()))
        except:
            break
    answer = tree.postOrder()
    for i in answer:
        print(i)

    実行時エラー:pythonの再帰関数の深さが超えたため発生
    メモリオーバーフロー:pythonの再帰関数の深さが100万に制限されている場合に発生します.
    後で1を修正するだけで解決でき、pythonは再帰関数の深さをcの配列のようにメモリとして推定します.