[PYTHON] Programmation pour combattre dans le monde - Chapitre 4

tree.py

# -*- coding:utf-8 -*-
import math

    
class TreeNode:
    def __init__(self,data=None,left=None,right=None):
        self.data = data
        self.left = left
        self.right = right
        self.adjacent = [self.left,self.right]
        self.visited = False
        self.next =None
        

class Treeutils:
    def __init__(self):
        self.classes = 0
    def treeappend(self,node,x):
        if node == None:
            return TreeNode(x)
        elif x == node.data:
            return node
        elif x < node.data:
            node.left = self.treeappend(node.left,x)
        else:
            node.right = self.treeappend(node.right,x)
            
        return node
        

    def treecheck(self,node):
        if node == None:
            return 0
        leftheight = self.treecheck(node.left)
        if leftheight == -1:
            return -1
        
        rightheight = self.treecheck(node.right)
        if rightheight == -1:
            return -1
        
        heightdiff = leftheight - rightheight
        
        if math.fabs(heightdiff) > 1:
            return -1
        else:
            return max(leftheight,rightheight) + 1
        
    def isBalanced(self,node):
        if self.treecheck(node) == -1:
            return None
        else:
            return True
        
    def createMinBST(self,arr =[],start = 0,end = 0):
        if end < start:
            return None
        mid = (start + end) / 2
        
        n = TreeNode(arr[int(mid)])
        n.left = self.createMinBST(arr,start,mid -1)
        n.right = self.createMinBST(arr,mid+1,end)
        return n
    
    def create(self,x):
        return self.createMinBST(range(x),0,len(range(x))-1)
    
    def covers(self,root,p):
        if root == None:
            return False
        if root == p:
            return True
        return self.covers(root.left,p) or self.covers(root.right,p)
    
    def commonAncestorHelper(self,root,p,q):
        if root == None:
            return None
        if root == p or root == q:
            return root
        is_p_on_left = self.covers(root.left,p)
        is_q_on_right = self.covers(root.right,q)
        
        if is_p_on_left != is_q_on_right:
            return root
        
        child = is_p_on_left if root.left else root.right
        
        return self.commonAncestorHelper(child,p,q)
    
    def commonAncestor(self,root,p,q):
        if self.covers(root,p) != True or self.covers(root,q) != True:
            return None
        return self.commonAncestorHelper(root,p,q)
            
        
    def containsTree(self,node1,node2):
        if node2 == None:return True
        return self.subTree(node1,node2)
    
    def subTree(self,node1,node2):
        if node1 == None:
            return False
        
        if node1.data ==node2.data:
            if self.matchTree(node1,node2):
                return True
        
        return self.subTree(node1.left,node2) or self.subTree(node1.right,node2)
    
    def matchTree(self,node1,node2):
        if node1 == None and node2 == None:
            return True
        
        if node1 or node2 == None:return False
        
        if node1.data != node2.data:return False
        
        return self.matchTree(node1.left,node2.left) and self.matchTree(node1.right,node2.right)
                

tester Je n'ai pas fait les quatre chapitres. Je le fais, mais ce n'est tout simplement pas répertorié (tremblant) Je ne sais pas si l'arborescence des correspondances fonctionne correctement