节点类
class Node(object):
def __init__(self,data=None):
self.val = data
self.left = None
self.right = None
二叉树前、中、后、按层遍历
class MyTree(object):
def __init__(self):
self.root = Node()
def add(self,data):
if self.root.val is None:
self.root.val = data
return self.root
tempList = []
tempList.append(self.root)
while len(tempList):
curNode = tempList.pop(0)
if curNode.left is None:
curNode.left = Node(data)
return self.root
if curNode.right is None:
curNode.right = Node(data)
return self.root
tempList.append(curNode.left)
tempList.append(curNode.right)
def per_order_recurise(self,node):
if node is None:
return
print(node.val)
self.per_order_recurise(node.left)
self.per_order_recurise(node.right)
def per_order_stack(self,node):
if node is None:
return
stack = []
nodeTemp = node
while nodeTemp or len(stack):
while nodeTemp:
print(nodeTemp.val)
stack.append(nodeTemp)
nodeTemp = nodeTemp.left
nodeTemp = stack.pop(0)
if nodeTemp:
nodeTemp = nodeTemp.right
def in_order_recurise(self,node):
if node is None:
return
self.in_order_recurise(node.left)
print(node.val)
self.in_order_recurise(node.right)
def post_order_recurise(self,node):
if node is None:
return
self.post_order_recurise(node.left)
self.post_order_recurise(node.right)
print(node.val)
def level_recursion(self,node):
if node is None:
return
tempList = []
tempList.append(node)
tempNode = node
count = 0
while len(tempList):
curNode = tempList.pop(0)
if curNode:
print(curNode.val)
if curNode==tempNode:
count += 1
tempNode = curNode.right
print('level :',count)
if curNode.left is None:
continue
tempList.append(curNode.left)
if curNode.right is None:
continue
tempList.append(curNode.right)
二叉搜索树
class SearchTree():
def __init__(self):
self.root = None
def insert(self, root, val):
'''二叉搜索树插入操作'''
if root == None:
root = TreeNode(val)
elif val < root.val:
root.left = self.insert(root.left, val)
elif val > root.val:
root.right = self.insert(root.right, val)
return root
def query(self, root, val):
'''二叉搜索树查询操作'''
if root == None:
return False
if root.val == val:
return True
elif val < root.val:
return self.query(root.left, val)
elif val > root.val:
return self.query(root.right, val)
def findMin(self, root):
'''查找二叉搜索树中最小值点'''
if root.left:
return self.findMin(root.left)
else:
return root
最大、最小深度
class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root==None:
return 0
if root.left==None or root.right==None:
return 1+ self.maxDepth(root.left)+self.maxDepth(root.right)
return 1+ max(self.maxDepth(root.left),self.maxDepth(root.right))
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
if root.left is None or root.right is None:
return 1 + min(self.minDepth(root.left)+self.minDepth(root.right))
# 只有叶子节点才能用于计算深度,为空不是在叶子,不能用于计算深度。
# 不知道那个为空,所以都加上,反正为0.
else:
return 1 + min(self.minDepth(root.left),self.minDepth(root.right))
# 层遍历
# 建立一个空列表,待遍历 temp_list,建立一个标记节点temp_node
# 将树的根节点放入temp_list,temp_node=root
# while temp_list 不为空,弹出list的0位节点,打印节点值,并将该节点的子节点加入(append)temp_list中。
# 如果弹出节点==temp_node,则层数加一,并将temp_list最后的节点赋值给temp_node
# 非递归的先、中、后序遍历
# 建立一个待遍历temp_list,将根节点放入
# while temp_list 不为空,弹出0位置节点,打印值,将子节点append到temp_list中。
# 递归建二叉搜索树的过程
# 传入根节点,无节点建立节点
# 有节点,比较值,小于则将左节点作为根节点,递归
# 大于则将右节点作为根节点,递归
# 搜索过程
# 与根节点比较,如果小于则递归查找左侧,如果大于则递归查找右侧,直到找到或者,没找到。可以返回最近的叶子节点。
网友评论