ツリーの各種アルゴリズム(一)python

間もなく秋招に入って、ビルの主人は後でいくつかのデータ構造のアルゴリズムのテーマpythonバージョン+機械が主流のアルゴリズムの原理と導きを学ぶことができて、暇があって更にあります.
今日はツリー要素の追加(キュー実装)、前、中、後のループの再帰とスタック実装、最大深さと最大距離の再帰実装についてです.
PS:スレ主は大体1つの例を使ってテストして、しばらく欠点がなくて、もしバグの私信あるいは評論があれば私が修正して、もし同じならば、私があなたを写したと思って、もし著作権の紛争があれば私を私信して、あなた达は大物で私は弟です.大男に頭を下げる(実はこれらのアルゴリズムは完全に私が空想したわけではない.きっと私が以前これらの考えを見たことがあるに違いない.今回の思い出は実現しただけだ).

まずノードclassとツリーclassを定義し、ここでツリーは最初は空のノード

である.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Jul 31 23:06:50 2017

@author: xuhy
"""
class Node():#  class，    None
    def __init__(self,value=None,lchild=None,rchild=None):
        self.value=value
        self.lchild=lchild
        self.rchild=rchild

class BTree():#BTree   class
    def __init__(self,root=Node()):#     root   Node()
        self.root=root

次に階層追加要素が使用され、キュー

が使用されます.

    def add(self,new):#       
        #      ，      ，         ，      
        #       ，            ，         
        if self.root.value==None:
            self.root=Node(new)
        else:
            stack=[]
            stack.append(self.root)
            while stack:
                node=stack.pop(0)#     ，   pop(0)
                if node.lchild==None:
                    node.lchild=Node(new)
                    return
                elif node.rchild==None:
                    node.rchild=Node(new)
                    return
                else:
                    stack.append(node.lchild)
                    stack.append(node.rchild)

は、次に、前、中、後の順の再帰的実装

である.

    #      
    def front_digui(self,root):
        #     or，or           ，or      
        if root==None or root.value==None:
            return
        else:
            print(root.value)
            self.front_digui(root.lchild)
            self.front_digui(root.rchild)

    #    
    def mid_digui(self,root):
        if root==None or root.value==None:
            return
        else:
            self.mid_digui(root.lchild)
            print(root.value)
            self.mid_digui(root.rchild)

    #    
    def back_digui(self,root):
        if root==None or root.value==None:
            return
        else:
            self.back_digui(root.lchild)
            self.back_digui(root.rchild)   
            print(root.value)

それから3種類の遍歴のスタックが実現して、個人は後序が少しすごいと感じます

    #    ，   stack      node
    #      ，            ，  print+  ，
    #          ，  node  ，      
    def front_stack(self,root):
        if root.value==None:
            return
        node=root
        stack=[]
        while node or stack:
            while node:
                stack.append(node)
                print(node.value)
                node=node.lchild
            node=stack.pop()
            node=node.rchild
    #    ，   stack      node
    #     ，       ，    
    #      ，print+  node  ，            
    def mid_stack(self,root):
        if root.value==None:
            return
        node=root
        stack=[]
        while node or stack:
            while node:
                stack.append(node)
                node=node.lchild
            node=stack.pop()
            print(node.value)
            node=node.rchild

    #    ，   stack      node
    #      ，         ，      
    def back_stack(self,root):
        if root.value==None:
            return
        node=root
        stack1=[]
        stack2=[]
        stack1.append(node)
        while stack1:
            node=stack1.pop()
            stack2.append(node)
            if node.lchild:
                stack1.append(node.lchild)
            if node.rchild:
                stack1.append(node.rchild)
        while stack2:
            node=stack2.pop()
            print(node.value)

次は再帰的に二叉樹の最大深さと距離を求め、その中の最大距離は『プログラミングの美』の上のテーマのようで、ここは最大深さとともに出力され、理解に困難があれば、読者はペンと紙を出して絵を描くことができ、理にかなっている.

    #              ，      recur
    #    ，                   +1；
    #      ，                ，          
    #           +       +1+1，      ；
    #           0，   0
    def get_depth_dis(self,root):
        if root.value==None:
            return
        elif root.lchild==None and root.rchild==None:
            return 0,0
        elif root.lchild==None and root.rchild!=None:
            return (self.get_depth_dis(root.rchild)[0]+1,
                    max(self.get_depth_dis(root.rchild)[1],
                        self.get_depth_dis(root.rchild)[0]+1))
        elif root.rchild==None and root.lchild!=None:
            return (self.get_depth_dis(root.lchild)[0]+1,
                    max(self.get_depth_dis(root.lchild)[1],
                        self.get_depth_dis(root.lchild)[0]+1))
        else:
            return (max(self.get_depth_dis(root.lchild)[0]+1,
                        self.get_depth_dis(root.rchild)[0]+1),
                    max(self.get_depth_dis(root.lchild)[1],
                        self.get_depth_dis(root.rchild)[1],
                        self.get_depth_dis(root.lchild)[0]+1+
                        self.get_depth_dis(root.rchild)[0]+1))

今度はまずここに来て、実習のこともしなければならないので、たまに時間を割いて手を練習しなければなりません.次は階層遍歴、中順+その他の順序でツリー、ツリーミラーを再構築する必要があります.のsee you! pps:暇があったらまたGANのいくつかのバージョンをテストしたいです.もしやったら更新します.私の1060が耐えられるかどうか分かりません.天殺の黄牛&サボって、1080 tiを返してください.ああ、夏休みが终わってまた実験室に帰ってレンガを运びました.结局穴の主人はできませんね.うん、私は电気工事です.の