[PYTHON] Programmierung für den Kampf in der Welt - Kapitel 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)
                

Prüfung Ich habe nicht alle vier Kapitel gemacht. Ich mache es, aber es ist einfach nicht aufgeführt (zitternd) Ich bin nicht sicher, ob der Matchbaum richtig funktioniert