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)
test I haven't made all four chapters. I'm making it, but it's just not listed (quivering voice) I'm not sure if the match tree is working properly