I'm trying to search a node from the following Trisection Tree each node has three children's (must use Recursion)

                        (1,5)
                      /0  |1  \2
                     /    |    \                   
                (2,7)          (1,3)
              /0  |1 \2      /0 |1 \2
                  |   \         |   \
                     (7,5)          (0,-5)
                  

key=(1,5), children=[key=(2,7), children=[None, None, key=(7,5), children=[None, None, None]], None, key=(1,3), children=[None, None, key=(0,-5), children=[None, None, None]]]

Here is my search function contain argument p (p is a node which I want to search e.g. (1,3))

def search(self,p):
        
        if self.key == None:
            return None
        if p == self.key:
            return self
        elif self.child[0]:
                            
            if self.child[0] == None:
                return None
            else:
                return self.child[0].search(p)
        elif self.child[1]:
                            
            if self.child[1] == None:
                return None
            else:
                return self.child[1].search(p)
        elif self.child[2]:
                           
            if self.child[2] == None:
                return None
            else:
                return self.child[2].search(p)

Output can be if p=(1,3)

key=(1,3), children=[None, None, key=(0,-5), children=[None, None, None]]

How to do this..

CodePudding user response：

Some of the issues:

• If you enter the elif self.child[0] block, then the next (nested) if condition (self.child[0] == None) is always going to be false.

• In that same block there will always be a return that executes, i.e. no other child will ever be checked.

Not the problem, but:

• The self.key == None condition seems to assume that... there could be a None key, which makes me think your Tree class is always having at least one node, and that you indicate an empty tree with a None key. That is not the best practice. An empty tree should just have no nodes at all. So you should separate a Node class from a Tree class, where the Tree class has a root attribute that is either None (empty tree) or a Node instance.

Here is the correction of your method:

    def search(self, p):
        if p == self.key:
            return self
        for child in self.child:
            found = child and child.search(p)
            if found:
                return found