Pythonアルゴリズム練習--検索ツリーを双方向チェーンテーブルに変換

本文の現在分かち合うテーマはすべてJulyの分かち合いから来て、それから具体的なアルゴリズムを実現します.探索ツリー回転双方向チェーンテーブルの主な実現ロジックは中序遍歴であり、ノードの左右のサブツリーを調整する.中序遍歴は再帰呼び出しであるため,調整時には調整の位置に注意しなければならず,書き間違えた場合,デッドサイクルをもたらす可能性が高い.回避の主な方法は、左サブツリーを読み終わったときに左ノードを調整し、右サブツリーを巡り終わったときに右ノードを調整することです.具体的なコードはtrans関数を参照してください.アルゴリズムの時間複雑度はo(logn)である.
ツリー構築が完了したら、次のように入力します.
コードは次のとおりです.

# -*- coding: utf-8 -*-
"""
  ：         （      ），                   。  ：          ，             。
1 2 3 4 5 6 7      4 3 1 2 5 6 7            
    ：        ，                        ，                  
"""
class TreeNode:
    """
          ，              
    """

    def __init__(self): 
        """
                ，          
        """
        self.leftNode = None
        self.rightNode = None

    def setData(self, data):
        """
               
        args: data   
        """
        self.data = data

    def setLeftNode(self, leftNode):
        """
                
        args: leftNode    
        """
        self.leftNode = leftNode

    def setRightNode(self, rightNode):
        """
                
        args: rightNode    
        """
        self.rightNode = rightNode

    def getData(self):
        """
              
        return:      
        """
        return self.data

    def getLeftNode(self):
        """
             
        return:     
        """
        return self.leftNode

    def getRightNode(self):
        """
             
        return:     
        """
        return self.rightNode

class BuildTree:
    """
                ，        ，        
    """


    def build(self, dataList):
        """
             
        args:dataList      
        """
        #      
        for i in range(len(dataList)):       
             currData = dataList[i]
             #       
             newTreeNode = TreeNode()
             newTreeNode.setData(currData);
             #       ，        
             if i==0:
                 self.tree = newTreeNode
            #         ，          
             else:
                 flagNode = self.tree
                 while flagNode is not None:
                     if currData <= flagNode.getData():
                         #            ，         ，        
                         if flagNode.getLeftNode() is  None: 
                             flagNode.setLeftNode(newTreeNode)
                             break;
                         else:
                             #        
                             flagNode = flagNode.getLeftNode()
                     else:
                        #          ，         ，        
                        if flagNode.getRightNode() is None:                            
                             flagNode.setRightNode(newTreeNode)
                             break;
                        else:
                            #        
                            flagNode = flagNode.getRightNode()

    def trans(self, tempNode):
        """
                
                ，          ，        
                ，          ，        
        args:tempNode         
        """
        if tempNode is not None:
            #       
            self.trans(tempNode.getLeftNode())
            #       ，           
            if tempNode.getLeftNode() is not None:
                tempNode2 = tempNode.getLeftNode()
                while tempNode2.getRightNode() is not None:
                    tempNode2 = tempNode2.getRightNode()
                tempNode.setLeftNode(tempNode2)
                tempNode2.setRightNode(tempNode)
            #       
            self.trans(tempNode.getRightNode())
            #       ，           
            if tempNode.getRightNode() is not None:
                tempNode2 = tempNode.getRightNode()
                while tempNode2.getLeftNode() is not None:
                    tempNode2 = tempNode2.getLeftNode()
                tempNode.setRightNode(tempNode2)
                tempNode2.setLeftNode(tempNode)

    def callTrans(self):
        """
             trans    
        """
        self.trans(self.tree);

    def test(self):
        """
               ，                
        """
        tempNode = self.tree
        while tempNode.getLeftNode() is not None:
            #      
            tempNode = tempNode.getLeftNode()
            #print tempNode.getData()
        #     
        while tempNode.getRightNode() is not None:
            print tempNode.getData()
            tempNode = tempNode.getRightNode()
        print tempNode.getData()
        #     
        while tempNode is not None:
            print tempNode.getData()
            tempNode = tempNode.getLeftNode()

if __name__ == "__main__":   
    #     
    dataList = [10,6,4,8,2,5,7,9,20,15,28,14,16,24,29]
    test = BuildTree()   
    #     
    test.build(dataList)
    #        
    test.callTrans()
    #    
    test.test()                

出力結果:
2 4 5 6 7 8 9 10 14 15 16 20 24 28 29 29 28 24 20 16 15 14 10 9 8 7 5 4 2
購読番号「白話アルゴリズム」へようこそ