pythonは二叉木とその七種類の遍歴を実現する

紹介:
ツリーはデータ構造において非常に重要なものであり、主な用途は検索効率を向上させることであり、二叉ソートツリー、FP-ツリーなどの繰り返し検索の場合に効果的である.さらに、ハフマンツリーなどの符号化効率を向上させるために使用することができる.
コード:
pythonで木の構造といくつかの遍歴アルゴリズムを実現するのは難しくないが,コードを整理してまとめた.実装機能:

木の構造

再帰的に先順遍歴、中順遍歴、後順遍歴

を実現する.

スタックは、先順遍歴、中順遍歴、後順遍歴

を実現する.

キュー実装階層

#coding=utf-8

class Node(object):
    """   """
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree(object):
    """  """
    def __init__(self):
        self.root = Node()


    def add(self, elem):
        """      """
        node = Node(elem)
        if self.root.elem == -1:            #      ，       
            self.root = node
        else:                     
            myQueue = []
            treeNode = self.root
            myQueue.append(treeNode)
            while myQueue:                      #            
                treeNode = myQueue.pop(0)
                if treeNode.lchild == None:
                    treeNode.lchild = node
                    return
                elif treeNode.rchild == None:
                    treeNode.rchild = node
                    return
                else:
                    myQueue.append(treeNode.lchild)
                    myQueue.append(treeNode.rchild)


    def front_digui(self, root):
        """            """
        if root == None:
            return
        print root.elem,
        self.front_digui(root.lchild)
        self.front_digui(root.rchild)


    def middle_digui(self, root):
        """            """
        if root == None:
            return
        self.middle_digui(root.lchild)
        print root.elem,
        self.middle_digui(root.rchild)


    def later_digui(self, root):
        """            """
        if root == None:
            return
        self.later_digui(root.lchild)
        self.later_digui(root.rchild)
        print root.elem,


    def front_stack(self, root):
        """            """
        if root == None:
            return
        myStack = []
        node = root
        while node or myStack:
            while node:                     #      ，        
                print node.elem,
                myStack.append(node)
                node = node.lchild
            node = myStack.pop()            #while        node  ，            
            node = node.rchild                  #         


    def middle_stack(self, root):
        """            """
        if root == None:
            return
        myStack = []
        node = root
        while node or myStack:
            while node:                     #      ，        
                myStack.append(node)
                node = node.lchild
            node = myStack.pop()            #while        node  ，            
            print node.elem,
            node = node.rchild                  #         


    def later_stack(self, root):
        """            """
        if root == None:
            return
        myStack1 = []
        myStack2 = []
        node = root
        myStack1.append(node)
        while myStack1:                   #  while               ，  myStack2  
            node = myStack1.pop()
            if node.lchild:
                myStack1.append(node.lchild)
            if node.rchild:
                myStack1.append(node.rchild)
            myStack2.append(node)
        while myStack2:                         # myStack2      ，        
            print myStack2.pop().elem,


    def level_queue(self, root):
        """            """
        if root == None:
            return
        myQueue = []
        node = root
        myQueue.append(node)
        while myQueue:
            node = myQueue.pop(0)
            print node.elem,
            if node.lchild != None:
                myQueue.append(node.lchild)
            if node.rchild != None:
                myQueue.append(node.rchild)


if __name__ == '__main__':
    """   """
    elems = range(10)           #           
    tree = Tree()          #       
    for elem in elems:                  
        tree.add(elem)           #        

    print '        :'
    tree.level_queue(tree.root)

    print '

        :'
    tree.front_digui(tree.root)
    print '
        :' 
    tree.middle_digui(tree.root)
    print '
        :'
    tree.later_digui(tree.root)

    print '

        :'
    tree.front_stack(tree.root)
    print '
        :'
    tree.middle_stack(tree.root)
    print '
        :'
    tree.later_stack(tree.root)

まとめ:
木の遍歴は主に2種類あり、1つは深さ優先遍歴であり、前序、中序、後序のようなものである.もう1つは、階層遍歴のような広さ優先遍歴です.ツリー構造では両者の違いはまだ明らかではないが,ツリーから有向図に拡張し,無方向図に至るまで深さ優先探索と広さ優先探索の効率と役割は大きく異なる.深さ優先は一般に再帰,広さ優先はキューである.一般的に再帰的に実現できるアルゴリズムの大部分もスタックで実現できる.
ツリーを再帰的に作る方法があるような印象ですが、どうやって作るかずっと考えられませんでした.後でよく考えてみると,再帰思想は深さ優先アルゴリズムに似ているが,木の構造は広さ優先であるべきである.再帰を使う場合は必ず終了条件があります.例えば、木の深さを規定するなどです.そうでないと構築された木は左単子樹か右単子樹に偏っている.ですから、一般的な木の構造はやはりキューを使うべきです.
以上の話は厳密ではありません.間違いがあれば、指摘を歓迎します.
転載は出典を明記してください.ありがとうございます.(原文リンク:http://blog.csdn.net/bone_ace/article/details/46718683)