<jupyter_start><jupyter_text>N-Ary Trees N-ary trees are tree data structures that allow us to have up to n children nodes for each of the nodes. We need two pieces of information:- the value of the node- the list of its children nodes<jupyter_code>class Tree:
    def __init__(self, value, children = None):
        if children is None:
            children = []
        self.value = value
        self.children = children
    def __repr__(self, level=0):
        """String representation of a n-ary Tree"""
        result = '|--'*level + f"Tree({self.value},...)"
        for child in self.children:     # per ogni figlio
            # aggiungo una riga con il figlio piÃ¹ indentato
            result += '\n' + child.__repr__(level+1)
        return result

# Sample tree
n1 = Tree(1)
n2 = Tree(2)
n3 = Tree(3, [n1, n2])
n4 = Tree(4, [n3]) 
n5 = Tree(5, [n4])
n6 = Tree(6)
tree = Tree(7, [n5, n6])

print(tree)<jupyter_output>Tree(7,...)
|--Tree(5,...)
|--|--Tree(4,...)
|--|--|--Tree(3,...)
|--|--|--|--Tree(1,...)
|--|--|--|--Tree(2,...)
|--Tree(6,...)<jupyter_text>Get information about tree Get height<jupyter_code>def get_height(tree):
    if not tree.children:
        return 1
    return max([get_height(child) for child in tree.children]) + 1

print(f"Sample n-ary tree is {get_height(tree)} levels deep")<jupyter_output>Sample n-ary tree is 5 levels deep<jupyter_text>Get diameterThe diameter of the tree is defined as the **total number of nodes on the longest path between two end nodes**<jupyter_code>def diameter(tree):
    # Base case: tree has not children, so it's diameter is one
    if not tree.children:
        return 1
    else:
        # prima trovo il valore del diametro massimo di ciascuno dei sottoalberi
        diam_max_figli = max([ diametro(figlio) for figlio in radice._figli ])
        # poi calcolo la lunghezza del percorso se passasse per la radice
        if len(radice._figli) == 1:             # se c'Ã¨ un solo figlio
            # altezza dell'unico sottoalbero +1
            diametro_per_radice = 1 + altezza(radice._figli[0])
        else:
            # se ci sono almeno 2 figli prendo le prime due altezze massime
            altezze_ordinate = list(sorted([ altezza(figlio) for figlio in radice._figli ], reverse=True ))
            prima, seconda = altezze_ordinate[:2]
            diametro_per_radice = prima + seconda + 1       # e il percorso piÃ¹ lungo Ã¨ la loro somma +1
        return max(diametro_per_radice, diam_max_figli)     # torno il massimo dei due casi (per la radice o solo nei sottoalberi)<jupyter_output><empty_output><jupyter_text>Trasversal of a n-ary tree Pre-order trasversal<jupyter_code>def preorder(tree, result = None):
    if result is None:
        result = []
    if not root:
        return result
    result.append(tree.value)
    # print(tree.value, end=" ")
    for child in tree.children:
        preorder(child, result)
    return result

print(f"Preorder traversal of sample tree: {preorder(tree)}")<jupyter_output>Preorder traversal of sample tree: [7, 5, 4, 3, 1, 2, 6]<jupyter_text>In-order trasversal<jupyter_code>def inorder(tree, result = None):
    if result is None:
        result = []
    if tree is None:
        return result
    # visit all children except last one
    for child in len(tree.children) - 1:
        preorder(child, result)
    print(tree.data,end=" ")
    result.append(child.value)
    return result

print(f"Preorder traversal of sample tree: {inorder(tree)}")<jupyter_output>Preorder traversal of sample tree: [5, 4, 3, 1, 2, 5, 6, 6]
{'fraction_non_alphanumeric': 0.1179285111173656, 'fraction_numerical': 0.015761328454826907, 'mean_word_length': 2.90979097909791, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '379309', 'license': 'MIT', 'n_tokens_mistral': 1228, 'n_tokens_neox': 1206, 'n_words': 381, 'path': '06_n_ary_trees.ipynb', 'repo_name': 'AlexGherardelli/PyNotes', 'size': '3553'}