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
Recommended Posts