Tree implementation in Python

Question

How to implement tree in Python?

I am Python beginner.

Give me a general idea!

Answer 1

Build a Node class, having some content object and a list of children, which are again instances of Node.

Answer 2

An example of a binary tree. It uses dataclass from Python 3.7 and typing

"""
in-order, pre-order and post-order traversal of binary tree

              A
             / \
            B   C
           / \   \
          D   E   F
         / \
        G   H

    in-order
    G->D->H->B->E->A->F->C
    pre-order
    A->B->D->G->H->E->C->F
    post-order
    G->H->D->E->B->F->C->A
"""


from __future__ import annotations
from typing import Optional
from dataclasses import dataclass


@dataclass
class Node:
    data: str
    left: Optional[Node] = None
    right: Optional[Node] = None


@dataclass
class Tree:
    root: Node

    def in_order(self, node: Optional[Node]) -> None:
        if node:
            self.in_order(node.left)
            print(node.data, end="->")
            self.in_order(node.right)

    def pre_order(self, node: Optional[Node]) -> None:
        if node:
            print(node.data, end="->")
            self.pre_order(node.left)
            self.pre_order(node.right)

    def post_order(self, node: Optional[Node]) -> None:
        if node:
            self.post_order(node.left)
            self.post_order(node.right)
            print(node.data, end="->")


if __name__ == "__main__":
    h = Node("H")
    g = Node("G")
    f = Node("F")
    e = Node("E")
    d = Node("D", g, h)
    c = Node("C", f)
    b = Node("B", d, e)
    a = Node("A", b, c)

    tree = Tree(a)
    print("\nin-order")
    tree.in_order(a)
    print("\npre-order")
    tree.pre_order(a)
    print("\npost-order")
    tree.post_order(a)

Answer 3

class Tree(object):
    def __init__(self, name, left_subtree = None, right_subtree = None):
        self._name = name
        self._left_subtree = left_subtree
        self._right_subtree = right_subtree

def inorder(tree):
    if tree is not None:
        inorder(tree._left_subtree)
        print tree._name
        inorder(tree._right_subtree)

if __name__ == '__main__':
    a = Tree('a')
    b = Tree('b')
    c = Tree('c', a, b)
    inorder(c)

Answer 4

class Tree:
def __init__(self,immediateroot=None,index=None):
    self.Nodes=[]
    self.imroot=immediateroot
    self.parent=self.findrecursiveroot()
    self.ArrayOfValues={}
    self.depth=0
    self.index=index
def SetValue(self,**kwargs):
    self.ArrayOfValues=kwargs
def flush2(self):
    salf.parent=self.findrecursiveroot()
def addnode(self):
    self.Nodes+=[Tree(immediateroot=self,index=len(self.Nodes))]
    #self.flush1()
    return self.Nodes[len(self.Nodes)-1]
def recursivesequence(self,tree):
    return self.inrecursivesequence(tree)
def inrecursivesequence(self,tree):
    if tree.imroot==tree.parent:
        return [tree.index]
    return self.inrecursivesequence(tree.imroot)+[tree.index]
def findcorrespondence(self,Category,Value):
    if self.ArrayOfValues[Category]==Value:
            return self
    for node in self.Nodes:
        if node.ArrayOfValues[Category]==Value:
            return node.index
    print('Not Found')
    return None
def access(self,index):
    try:
        return self.Nodes[index]
    except:
        print('Index Out Of Range')
        return None
def Recursiveaccess(self,sequence):
    newtree=self.parent
    return self.inRecursiveaccess(newtree,sequence)
def inRecursiveaccess(self,tree,sequence):
    if len(sequence)==1:
        return tree.Nodes[sequence[0]]
    return self.inRecursiveaccess(tree.Nodes[sequence[0]],sequence[1:])
def findrecursiveroot(self):
    self.depth=0
    return self.intfindrecursiveroot(self)
def intfindrecursiveroot(self,tree):
    if tree.imroot==None:return tree
    self.depth+=1
    return self.intfindrecursiveroot(tree.imroot)
def findleafs(self):
    return self.intfindleafs(self)
def intfindleafs(self,tree):
    if len(tree.Nodes)==0:
        return [tree]
    L=[]
    for node in tree.Nodes:
        L+=self.intfindleafs(node)
    return L
def updateleaf(self,Convert,leaf,newtree):
    Leafs=self.findleafs()
    for leaflet in Leafs:
        if leaflet==leaf:
            self.recursiveupdateparent(leaflet,newtree)
def recursiveupdateparent(self,leaflet,newtree):
    immediateroot,t=leaflet.imroot,leaflet.imroot
    newtree.imroot=immediateroot
    newtree.parent=leaflet.parent
    newtree.index=leaflet.index
    immediateroot.Nodes[leaflet.index]=newtree
    if immediateroot.imroot==None:
        pass
    else:
        return self.recursiveupdateparent(t,immediateroot)
def extractnode(self,index):
    tempstorage=self.parent.Nodes[index]
    tempstorage.parent=tempstorage
    tempstorage.imroot=None
    tempstorage.recursiveupdatenodes()
    return tempstorage
def recursiveupdatenodes(self):
    for i in range(len(self.Nodes)):
        self.Nodes[i].parent=self.parent
        self.Nodes[i].recursiveupdatenodes()
def __str__(self):
    s='''There are '''+str(len(self.Nodes))+''' nodes. \n'''
    s+='''Its set of values is : \n'''
    s+=str(self.ArrayOfValues)
    s+='''\n'''
    for i in range(len(self.Nodes)):
        if i==0:
            alpha='''st'''
        elif i==1:
            alpha='''nd'''
        elif i==2:
            alpha='''rd'''
        else:
            alpha='''th'''
        s+=str(i+1)+alpha+''' node has '''+str(len(self.Nodes[i].Nodes))+''' nodes \n'''
    return s
def __eq__(self,other):
    return id(self)==id(other)

This is a tree implementation I made ...Not very fast but would do the trick for beginners... Experienced developers out there, plz lemme know of any improvements that I can make coz I'm answering for the first time here... Thank you

Answer 5

The shortest implementation of iterable Tree could look like this. You can change order by changing yield order in iter method.

#               A
#              / \
#             B   C
#            / \   \
#           D   E   F
#          / \
#         G   H

from dataclasses import dataclass

@dataclass
class Node:
    data: str
    left: Node = None
    right: Node = None
    
    
    def __iter__(self):
        if self.left:
            yield from self.left
        
        yield self.data

        if self.right:
            yield from self.right

# usage

t = Node(
    'A', 
    Node(
        'B', 
        Node(
            'D', 
            Node('G'),
            Node('H'),
        ),
        Node('E'),
    ),  
    Node(
        'C', 
        right=Node('F'),
    ),
)
print(' -> '.join(t))
# G -> D -> H -> B -> E -> A -> F -> C