EPITA Algorithms s3 - General Tree

Changmok LEE·2023년 10월 4일

General Tree

Class of Tree

class Tree:

    def __init__(self, key=None, children=None):
        self.key = key
        if children is not None:
            self.children = children
        else:
            self.children = []

    @property
    def nbchildren(self):
        return len(self.children)

class of TreeAsBin

class TreeAsBin:

    def __init__(self, key=None, child=None, sibling=None):
        self.key = key
        self.child = child
        self.sibling = sibling

1. Measures

Exercise 1.1(Size)

Give the definition of the size of a tree : 11
Write a function that returns the size of a tree, for both implementations:

(a) by tuples (each node contains a tuples of children)

# EXERCISE 1-1(a)

def size(T:tree.Tree):
    
    s = 1
    for c in T.children:
        s += size(c)

    return s

(b) left child - right sibling (as a binary tree)

# EXERCISE 1-1(b)

def size(B:treeasbin.TreeAsBin):

    s = 1
    c = B.child
    while c != None:
        s += size(c)
        c = c.sibling

    return s

other way of size() function

def size(B:treeasbin.TreeAsBin):
    if B is None:
        return 0

    return 1 + size(B.child) + size(B.sibling)

Exercise 1.2(Height)

Give the definition of the height of a tree : 3
Write a function that returns the height of a tree, for both implementations:

(a) by tuples (each node contains a tuples of children)

the best height of the T

def height(T):
    ht = 0 # the best height of the T
    for c in T.children:
        ht = max(ht, height(c) + 1)

    return ht

height of the highest child

def height(T):

	if T.nbchildren == 0: # len(T.children) == 0
		return 0
	
    hc = 0 # height of the highest child
    for c in T.children:
        hc = max(hc, height(c))

    return hc + 1

The nbchildren property is defined in the Tree or class.
Properties are similar to methods, but they can be accessed without using parentheses.
In other words, they behave like regular attributes but internally execute a method.

(b) left child - right sibling (as a binary tree)

def height(B):

	ht = 0
	c = B.child
    
    while c != None:
    	ht = max(ht , height(c) + 1)
		c = c.sibling
        
    return ht

gitlab ver

def height(B):
    ht = -1
    c = B.child
    while c != None:    # while c:
        h = max(h, height(c))
        c = c.sibling
    return ht + 1

2. Traversals

Exercise 2.1(DFS: Depth first Search)

Give the principle of a depth first search for a general tree
List elements in prefix and suffix orders for the depth first search of the tree. What other action can be done when visiting a node :

prefix : 15, 3, -6, 10, 8, 11, 0, 4, 2, 5, 9
suffix : -6, 10, 3, 0, 4, 11, 2, 5, 8, 9, 15
Write the depth first search for both implementation:

(a) by tuples

most of the time, use the simple version

def DFS(T):
    # preorder = prefix (print(T.key)) 
    for c in T.children:
		DFS(c)
    # postorder = suffix

"full" version (with intermediate added) => use them only when really necessary

def DFS(T): (X)
    # preorder = prefix (print(T.key)) 
    if T.nbchildren > 0: # T.children == []:    # T.nbchildren == 0:
    	for i in range(T.nbchildren - 1):
			DFS(T.children[i])
        	#intermediate( != inorder)
        DFS(T.children[-1])
    # postorder = suffix

def dfs_full(T:tree.Tree):
    print(T.key)    # prefix
    if T.children == []:    # T.nbchildren == 0:
        # leaf ?(#intermediate)?
        pass
    else:
        for i in range(T.nbchildren - 1):
            dfs_full(T.children[i])
            # intermediate
        dfs_full(T.children[T.nbchildren-1])    # T.children[-1]
    # suffix

(b) left child - right sibling

most of the time, use the simple version

def dfs_TAB(B:treeasbin.TreeAsBin):
    print(B.key) # prefix
    child = B.child
    while child != None:
        dfs_TAB(child)
        child = child.sibling
    # suffix

"full" version (with intermediate added) => use them only when really necessary

def dfs_TAB_full(B:treeasbin.TreeAsBin):
    print(B.key) # prefix
    if B.child == None: # if not B.child:
        # leaf
        pass
    else:
        child = B.child
        while child.sibling != None:
            dfs_TAB_full(child)
            # intermediate
            child = child.sibling
        dfs_TAB_full(child)
    # suffix

Exercise 2.2(BFS: Breadth first Search)

Give the principle of a breadth first Search for a tree
How can we detect level changes during the traversal

first version with Tree: a "end level mark(Flag)" (None) is added in the queue

def bfs_print_levels(T:tree.Tree):
    q = queue.Queue()
    q.enqueue(T)
    q.enqueue(None)
   
    while not q.isempty():
        T = q.dequeue()
        if T == None:
            print()
            if not q.isempty():
                q.enqueue(None)
        else:
            print(T.key, end=' ')
            for C in T.children:
                q.enqueue(C)

second version with Tree: two queues

def bfs_print_levels_2(T:tree.Tree):
    q = queue.Queue()
    q.enqueue(T)
    q_next = queue.Queue()

    while not q.isempty():
        while not q.isempty():
            T = q.dequeue()
            print(T.key, end=' ')
            for C in T.children:
                q_next.enqueue(C)
        # changing level
        print()
        (q, q_next) = (q_next, q)

second version with TreeAsBin: two queues

def bfsasbin_print_levels(B:treeasbin.TreeAsBin):
    q_out = queue.Queue()
    q_in = queue.Queue()
    q_out.enqueue(B)
    while not q_out.isempty():  # "do ... while <cond>" would be better
        while not q_out.isempty():
            B = q_out.dequeue()
            print(B.key, end=' ')
            C = B.child
            while C: # C != None
                q_in.enqueue(C)
                C = C.sibling
        # changing level
        print()
        (q_out, q_in) = (q_in, q_out)

Write a function that displays everykeys, with each level on its own line, for both implementation:

(a) by tuples

def BFS(T):
    """
    T: Tree
    display T's keys
    """
    q = queue.Queue()
    q.enqueue(T)
    while not q.isempty():
        T = q.dequeue()
        print(T.key, end=' ')
        for child in T.children:
            q.enqueue(child)

(b) left child - right sibling

def BFS_tab(B):
    """
    B: TreeAsBin
    display B's keys
    """
    q = queue.Queue()
    q.enqueue(B)
    while not q.isempty():
        B = q.dequeue()
        print(B.key, end=' ')
        child = B.child
        while child != None:
            q.enqueue(child)
            child = child.sibling

3. Aplications

Exercise 3.1(Linear Representation)

Let A be the general tree A = <o, A1, A2 ... An>. The following linear representation of A = (o, A1, A2 ... An) is called list.

(a) Give the linear represnetation of the tree.

(15 (3 (-6) (10)) (8 (11 (0) (4)) (2) (5)) (9))
(b) Draw the corresponding to (12(2(25)(6)(-7))(0(18(1)(8))(9))(4(3)(11))).

              12
          /   |   \
        /     |    \
      2       0     4
   / / \    / \    / \
 25 6 -7   18  9  3  11
          / \  
         1  8

Write thefunction to_linear that builds the linear representation (as a string) from a tree, for both implementation:
(a) by tuples

def to_linear(T):
    """Build the _linear representation_ of a tree.

    Args:
        T (Tree)

    Returns:
        str: the linear representation of T

    """        
    s = '(' + str(T.key)
    for child in T.children:
        s += to_linear(child)
    s += ')'
    return s

(b) left child - right sibling

def to_linear(B):
    """Build the _linear representation_ of a tree.

    Args:
        B (TreeAsBin)

    Returns:
        str: the linear representation of B

    """            
    s = '(' + str(B.key)
    C = B.child
    while C != None:
        s += to_linear(C)
        C = C.sibling
    s += ')'
    return s

Exercise 3.2(Dot format)

A tree can be represented as a list of links (like a graph) : the dot format.

With T1 the tree:

>>> print(tree.dot(T1))
	graph {
    	15 -- 3
        15 -- 8
        15 -- 9
        3 -- -6
        3 -- 10
        8 -- 11
        8 -- 2
        8 -- 5
        11 -- 0
        11 -- 4   
    }

What if some nodes have identical keys?

             4
           /    \
         /       \
        8         12
     / / \      / | \ \
    0  4  5   -4  0  5  8

>>> print(tree.dot(T1))
	graph {
    	4 -- 8
        4 -- 12
        8 -- 0
        8 -- 4
        8 -- 5
        12 -- -4
        12 -- 0
        12 -- 5
        12 -- 8   
    }

Write the function that bulds the .dot representation(a string) of a tree for both implementation:

(a) by tuples

note ver

def __dot(T):

    s = " "
    q = Queue()
    q.enqueue(T)
    while not q.isempty():
        T = q.dequeue()
        K = str(T.key)
        for child in T.children:
            s += "   " + k + " -- " + str(child.key) + "\n"
            q.enqueue(child)
    return s
   
def dot(T):
	if T.nbchildren == 0:
    	return "graph {\n" + str(T.key) + "\n}"
    else:
    	return "graph {\n" + __dot(T) + "}"

gitlab ver

def dot(T):
    """Simple dot format of tree.

    Args:
        T (Tree).

    Returns:
        str: String storing dot format of tree.

    """
    s = "graph {\n"
    q = Queue()
    q.enqueue(T)
    while not q.isempty():
        T = q.dequeue()
        for child in T.children:
            s += "   " + str(id(T)) + " -- " + str(id(child)) + "\n"
            q.enqueue(child)
    s += "}"
    return s

(b) left child - right sibling

note ver

def __dot(B):

    s = " "
    q = Queue()
    q.enqueue(B)
    while not q.isempty():
        B = q.dequeue()
        K = str(B.key)
        child = B.child
        while child:
            s += "   " + k + " -- " + str(child.key) + "\n"
            q.enqueue(child)
            child = child.sibling
    return s
    
def dot(B):
	if B.child == None:
    	return "graph {\n" + str(B.key) + "\n}"
    else:
    	return "graph {\n" + __dot(B) + "}"

gitlab ver

def dot(B):
    """Simple dot format of tree.

    Args:
        B (TreeAsBin).

    Returns:
        str: String storing dot format of tree.

    """

    s = "graph {\n"
    q = Queue()
    q.enqueue(B)
    while not q.isempty():
        B = q.dequeue()
        child = B.child
        while child:
            s += "   " + str(id(B)) + " -- " + str(id(child)) + "\n"
            q.enqueue(child)
            child = child.sibling
    s += "}"
    return s

Exercise 3.3(Find the sum)

Write the function find_sum(B, sum) that tests if there exists a branch in the tree B(TreeAsBin) such that the sum of its values(integers) is equal to sum.

Aplication examples with T4 the tree in figure 2:

>>>fin_sum(T4, 20)
True
>>>fin_sum(T4, 10)
False
>>>fin_sum(T4, 7)
True
>>>fin_sum(T4, 17)
False

# with return in loop :o
   
def find_sum(B:treeasbin.TreeAsBin, Sum, s=0):
    """
    B: TreeAsBin
    optional parameter s is the sum of values in current path from root to parent of B root
    """
    if B.child == None:
        return s + B.key == Sum
    else:
        C = B.child
        while C:
            if find_sum(C, Sum, s + B.key):
                return True
            C = C.sibling
        return False

# without return in loop, without optional parameter
   
def find_sum2(B, Sum):
    """
    B: TreeAsBin
    """
    Sum -= B.key    # better: done only once!
    if B.child == None:
        return Sum == 0
    else:
        C = B.child
        while C != None and not find_sum2(C, Sum):
            C = C.sibling
        return C != None

Exercise 3.4(External Average Depth)

Give the definition of external average depth of a tree :

The sum of the depths of all external nodes in the tree divided by the number of external nodes
Write a function that returns the external average depth of a tree, for both implementations:

(a) by tuples

def external(T, depth = 0):
	if T.children == []:
    	return depth, 1
    else: 
    	tot_depth = 0
        tot_leaves = 0
        for child in T.children:
        	child_depth, child_leaves = external(child, depth + 1)
            tot_depth += child_depth
            tot_leaves += child_leaves
        return tot_depth, tot_leaves

total_depth, total_nodes = external(tree)
avg = total_depth / total_nodes

# a nice version: without depth, going-up
pass
def __ead_up(T:tree.Tree):
    """
    returns (sum of leaf depths, nb leaves)
    """
    if T.children == []:
        return (0, 1)
    else:
        (sum_depths, nb_leaves) = (0, 0)
        for child in T.children:
             (s, n) = __count(child)
             sum_depths += s + n  # each link count +1 for each leaf
             nb_leaves += n
        return (sum_depths, nb_leaves)

def external_average_depth_up(T:tree.Tree):
    (sum_depths, nb_leaves) = __ead_up(T)
    return sum_depths / nb_leaves

(b) left child - right sibling

# with TreeAsBin
def __count_tab(B, depth=0):
    """
    B: TreeAsBin
    depth: actual depth
    returns (sum of leaf depths, nb leaves)
    """    
    if B.child == None:
        return (depth, 1)
    else:
        Bchild = B.child
        (sum_depths, nb_leaves) = (0, 0)
        while Bchild != None:
            (s, n) = __count_tab(Bchild, depth+1)
            sum_depths += s
            nb_leaves += n
            Bchild = Bchild.sibling
    return (sum_depths, nb_leaves)
        

def external_average_depth_TAB(B):
    (sum_depths, nb_leaves) = __count_tab(B)
    return sum_depths / nb_leaves

Exercise 3.5(Tuples <-> left child - right sibling)

Write a function that builds, from a general tree with first child - right sibling implementation

def treeasbin_to_tree(B):
	T = tree.Tree(B.key, [])    # T = tree.Tree(B.key)
    child = B.child
    while child != None:
        T.children.append(treeasbin_to_tree(child))
        child = child.sibling
    return T

def treeasbin_to_tree(B):
	children = []
    child= B.child
    while child:
    	children.append(treeasbin_to_tree(child))
        child = child.sibling
	return tree.Tree(B.key, children)

Write the translation function for the other way.

# with "insertions" at the end
def tree_to_treeasbin_(T):
    B = treeasbin.TreeAsBin(T.key, None, None)  # B = treeasbin.TreeAsBin(T.key)
    if T.nbchildren != 0:
        B.child = tree_to_treeasbin(T.children[0])
        last = B.child
        for i in range(1, T.nbchildren):    
            last.sibling = tree_to_treeasbin(T.children[i])
            last = last.sibling
    return B

# "insertions at the head"
def tree_to_treeasbin(T):
    B = treeasbin.TreeAsBin(T.key)
    firstchild = None
    for i in range(T.nbchildren-1, -1, -1):
        C = tree_to_treeasbin(T.children[i])
        C.sibling = firstchild
        firstchild = C
    
    B.child = firstchild
    return B

Exercise 3.6(Symmetry)

Write the recursive function symmetry(T, B) that tests whether T, a general tree in "classical" implementation(by tuples), and B, a general tree in first child - right sibling implementation, are symmetrical.

# without return in the loop 
def symmetric(T:tree.Tree, B:treeasbin.TreeAsBin):
    if T.key != B.key:
        return False
    else:
        C = B.child
        i = T.nbchildren - 1
        while C and i >= 0 and symmetric(T.children[i], C):
            i -= 1
            C = C.sibling
        return C == None and i == -1

# with return statement in loop
def symmetric_2(T:tree.Tree, B:treeasbin.TreeAsBin):
    if T.key != B.key:
        return False
    else:
        C = B.child
        for i in range(T.children-1, -1, -1):
            if C == None or not(symmetric_2(T.children[i], C)):
                return False           
            C = C.sibling
        return C == None

Exercise 3.7(Load trees from files) pass

(a) by tuples

"linear representation" -> Tree (int keys)
The string is assumed correct!
also in algo_py/tree|treeasbin.py
"""

def __from_linear(s, i=0): 
        i += 1 # to skip the '('
        key = ""
        while s[i] != '(' and s[i] != ')':  # s[i] not in "()"
            key += s[i]
            i += 1
        T = tree.Tree(int(key), [])
        while s[i] != ')':  # s[i] == '('
            (C, i) = __from_linear(s, i)
            T.children.append(C)
        i += 1 # to skip the ')'
        return (T, i)

def from_linear(s):
    (T, _) = __from_linear(s)
    return T

(b) left child - right sibling

"""
"linear representation" -> TreeAsBin (int keys)
"""

def __from_linear(s, n, i=0): 
    if i < n and s[i] == '(':   
        i = i + 1 # to pass the '('
        key = ""
        while not (s[i] in "()"):
            key = key + s[i]
            i += 1
        B = treeasbin.TreeAsBin(int(key))
        (B.child, i) = __from_linear(s, n, i)
        i = i + 1   # to pass the ')'
        (B.sibling, i) = __from_linear(s, n, i) 
        return (B, i)
    else:
        return (None, i)

def from_linear(s):
    return __from_linear(s, len(s))[0]