最低限のコード（正しく機能しない場合が多数）

min_tree_sandbox.py

class Tree(object):
    def __init__(self, label, left=None, right=None):
        self.label = label
        self.left = left
        self.right = right
        
    def __str__(self):
        return str(self.label)
     
def get_dfs_label(t):
    left_label = get_dfs_label(t.left) if t.left is not None else ""
    right_label = get_dfs_label(t.right) if t.right is not None else ""
    return "{}{}{}".format(t, left_label, right_label)

def print_tree(t):
    if t is None:
        return
    print(t.label, end=" ")
    print_tree(t.left)
    print_tree(t.right)
    
from copy import deepcopy as copy
def get_all_complete_subtrees(t, ans):
    ans.append(copy(t))
    if t.left is not None:
        get_all_complete_subtrees(t.left, ans)
    if t.right is not None:
        get_all_complete_subtrees(t.right, ans)
    return
  
from collections import Counter
def get_tree_signature(t):
    scT = []
    feature_list = []
    get_all_complete_subtrees(t, scT)
    for subt in scT:
        feature_list.append(get_dfs_label(subt))
    counter = Counter(feature_list)
    total = sum(counter.values(), 0.0)
    for key in counter:
        counter[key] /= total
    return counter

t1 = Tree("I", Tree("F"), Tree("B", Tree("C", Tree("D", Tree("B", Tree("G")), Tree("B", Tree("G"))), Tree("D", Tree("B", Tree("G"))))))
t2 = Tree("L", Tree("F"), Tree("B", Tree("C", Tree("D", Tree("B", Tree("G")), Tree("B", Tree("G"))), Tree("D", Tree("B", Tree("G"))))))
sigT1 = get_tree_signature(t1)
sigT2 = get_tree_signature(t2)

print(sigT1)

"""
result:

Counter({'IFBCDBGBGDBG': 0.08333333333333333,
         'F': 0.08333333333333333,
         'BCDBGBGDBG': 0.08333333333333333,
         'CDBGBGDBG': 0.08333333333333333,
         'DBGBG': 0.08333333333333333,
         'BG': 0.25,
         'G': 0.25,
         'DBG': 0.08333333333333333})"""