Why this method returns me 2?

1

I have a code to parse and I can not really understand why this method in my Binary Tree returns me 2.

Code:

class No:
def __init__(self, dado):
    self.esq = None
    self.dir = None
    self.dado = dado 

class Arvore:
def __init__(self):
    self.raiz = None
def pegarRaiz(self):
    return self.raiz

def inserir(self, val):
    if self.raiz == None:
        self.raiz = No(val)
    else:
        self._inserir(val, self.raiz)

def _inserir(self, val, node):
    if val < node.dado:
        if(node.esq != None):
            self._inserir(val, node.esq)
            node.esq.pai = node
        else:
            node.esq = No(val)
    else:
        if node.dir != None:
            self._inserir(val, node.dir)
            node.dir.pai = node
        else:
            node.dir = No(val)

def resp(self):
    if(self.raiz != None):
        return self._resp(self.raiz)
def _resp(self,node):
    aux_esq = 0
    aux_dir = 0
    if node.esq != None:
        aux_esq = self._resp(node.esq)
    if node.dir != None:
        aux_dir = self._resp(node.dir)
    if (node.esq != None) or (node.dir != None):
        return 1 + aux_esq + aux_dir
    else:
        return 0
 T = Arvore()
 T.inserir(15)
 T.inserir(9)
 T.inserir(5)
 T.inserir(12)
 T.inserir(20)
 T.resp()

After the program runs it returns me 2, why?

    
asked by anonymous 05.01.2018 / 23:00

1 answer

2

First, we'll sort the indentation and visualize the formed tree (by adding __str__ methods):

class No:
    def __init__(self, dado):
        self.esq = None
        self.dir = None
        self.dado = dado

    def __str__(self):
        s = '(' + str(self.dado) + ','
        if self.esq != None:
            s += str(self.esq) + ','
        else:
            s += 'X,'
        if self.dir != None:
            s += str(self.dir) + ')'
        else:
            s += 'X)'
        return s

class Arvore:
    def __init__(self):
        self.raiz = None
    def pegarRaiz(self):
        return self.raiz

    def inserir(self, val):
        if self.raiz == None:
            self.raiz = No(val)
        else:
            self._inserir(val, self.raiz)

    def _inserir(self, val, node):
        if val < node.dado:
            if node.esq != None:
                self._inserir(val, node.esq)
                node.esq.pai = node
            else:
                node.esq = No(val)
        else:
            if node.dir != None:
                self._inserir(val, node.dir)
                node.dir.pai = node
            else:
                node.dir = No(val)

    def resp(self):
        if self.raiz != None:
            return self._resp(self.raiz)

    def _resp(self, node):
        aux_esq = 0
        aux_dir = 0
        if node.esq != None:
            aux_esq = self._resp(node.esq)
        if node.dir != None:
            aux_dir = self._resp(node.dir)
        if (node.esq != None) or (node.dir != None):
            return 1 + aux_esq + aux_dir
        else:
            return 0

    def __str__(self):
        if self.raiz != None:
            return str(self.raiz)
        else:
            return 'X'

T = Arvore()
T.inserir(15)
T.inserir(9)
T.inserir(5)
T.inserir(12)
T.inserir(20)
print(T.resp())
print(T)

Here's the output:

2
(15,(9,(5,X,X),(12,X,X)),(20,X,X))

See here working on ideone.

Looking at the tree we have this:

    15
   /  \
  9    20
 / \
5   12

Looking at resp , it does this:

  • On pages (5, 12, and 20), aux_esq and aux_dir are zero, none of if s enters and arrives at return 0

  • In the intermediate node (9), the three if s enters. However, the first two do not change the values of aux_esq and aux_dir which will remain zero. The third evaluates the 1 + aux_esq + aux_dir as 1 + 0 + 0 and returns 1.

  • In the root node (15), the three if s enters. In the first one, we will have 1 assigned to aux_esq . In the second we will have 0 assigned to aux_dir . In the third, the 1 + aux_esq + aux_dir will be evaluated as 1 + 1 + 0 and will return 2.

My conclusion is that this method is counting the number of nodes (non-leaves) in the tree. In the case of the given tree, the inner nodes are 9 and 15. This makes sense, since the if (node.esq != None) or (node.dir != None): will only enter non-sheets (internal) nodes, which means that for nodes, 0 will always be returned. As for the inner nodes, we have return 1 + aux_esq + aux_dir , which will return the number of inner nodes of each daughter subtree plus one to consider itself.

    
05.01.2018 / 23:58