I need to know how in a tree I can search for the deepest leaf of the tree. If there were two sheets with the same depth it wouldn't matter which one it was on.
It is assumed that I already have the Tree class created, and also the function that creates a tree from a list. I put such a function in the following code. I will also put the function that allows me to know if a node is a leaf or not.
def profundidad (arbol):
profundidad = 0
izdo = 0
dcho = 0
if Es_hoja(arbol):
profundidad = 1
info = arbol.info
return profundidad , info
else:
if not arbol.izdo.esvacio:
izdo,infoi = profundidad(arbol.izdo)
elif not arbol.dcho.esvacio:
dcho,infod = profundidad(arbol.dcho)
if (izdo > dcho):
return izdo+1,infoi
else:
return dcho+1, infod
With this code I try to obtain the depth of the tree and the information it has, however it gives me an error.
You have a couple of big bugs in the
profundidad()
.The first is that you initialize a variable with the same name as the function,
profundidad=0
, so when you later try to recursively call that same function withprofundidad(arbol.izdo)
, for example, it will fail because at that moment the identifierprofundidad
is no longer the function, but the whole.You didn't really need the integer
profundidad
at all, so we can remove it as you'll see in the implementation I propose later.The second error is logical. He
eilf not arbol.dcho.esvacio:
should just beif not arbol.dcho.esvacio:
. Think that you have to examine both branches, both the left and the right. As you have it, if the left wasn't empty, then you wouldn't examine the right anymore.So my suggestion would be:
Additional improvements
Your role
Es_hoja()
is a bit redundant. It could be left like this:The program might be easier to debug if the trees included an
__repr__()
appropriate method, which returns a representation of the tree as a string. I propose the following:This will allow you to do a
print(arbol)
, for example:Which is another way of saying that the tree has this structure:
By the way, it
print(profundidad(a))
produces in this case the result(4, 'f')
, which is correct.