python 实现二叉树相关算法
一、构建与遍历二叉树
基本性质
1）在二叉树的第i层上最多有2i-1 个节点 。（i>=1）
2）二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
3）在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。向下取整就是小数点后面的数字无论多少，都只取前面的整数。
4）二叉树的存储可以顺序存储即数组形式，也可以链式存储。
class Node(object):def __init__(self,item):
self.key=item
self.left=None
self.right=None
class BinaryTree(object):def __init__(self):
self.root=None
def addNode(self,item):
new_node = Node(item)
if self.root is None:
self.root=new_node
else:
stack=[]
stack.append(self.root)
while True:
node=stack.pop(0)
if node.left is None:
node.left=new_node
return
elif node.right is None:
node.right=new_node
return
else:
stack.append(node.left)
stack.append(node.right)
def traverse(self): #层次遍历
if self.root is None:
return None
else:
s=[]
s.append(self.root)
while len(s) > 0:
node = s.pop(0)
print(node.key)
if node.left is not None:
s.append(node.left)
if node.right is not None:
s.append(node.right)
#一层层打印
def Print(self, pRoot):if pRoot is None:
return []
l=[]
s=[]
s.append(pRoot)
while len(s)>0:
length=len(s)
v=[]
for i in range(length):
tmp=s.pop(0)
v.append(tmp.val)
if tmp.left:
s.append(tmp.left)
if tmp.right:
s.append(tmp.right)
l.append(v)
return l
def preOrder(self,root):if root is None:
return None
print(root.key)
self.preOrder(root.left)
self.preOrder(root.right)
def inOrder(self,root):
if root is None:
return None
self.inOrder(root.left)
print(root.key)
self.inOrder(root.right)
def postOrder(self,root):
if root is None:
return None
self.postOrder(root.left)
self.postOrder(root.right)
print(root.key)
之字形打印二叉树
def print(root):if root is None:
return None
s1=[]
s2=[]
s1.append(root)#靠两个栈交替左右压入栈，实现左右交替输出，形成之字形打印
while len(s1)>0 or len(s2)>0:
while len(s1)>0:
tmp=s1.pop()
print(tmp.value)
if tmp.left is not None:
s2.append(tmp.left)
if tmp.right is not None:
s2.append(tmp.right)
while len(s2)>0:
tmp=s2.pop()
print(tmp.value)
if tmp.right is not None:
s1.append(tmp.right)
if tmp.left is not None:
s1.append(tmp.left)
非递归前序遍历：
def PreOrderWithoutRecursion(root):if root is None:
return
s=[]
p=root
while len(s)>0 or p is not None:
if p is not None:
print(p.key)
s.append(p)
p=p.left
else:
p=s.pop()
p=p.right
非递归中序遍历：
def InOrderWithoutRecursion(root):if root is None:
return
s=[]
p=root
while len(s)>0 or p is not None:
if p is not None:
s.append(p)
p=p.left
else:
p=s.pop()
print(p.key)
p=p.right
非递归后序遍历：
def PostOrderWithoutRecursion(root):if root is None:
return
s=[]
p=root
lastVisit=None
while p is not None:
s.append(p)
p=p.left
while len(s)>0:
p=s.pop()
if p.right==None or lastVisit==p.right:
print(p.key)
lastVisit=p
else:
s.append(p)
p=p.right
while p is not None:
s.append(p)
p=p.left
二、二叉树的宽度与深度
def treeDepth(root):if root is None:
return 0
nleft=treeDepth(root.left)+1
nright=treeDepth(root.right)+1
return nleft if nleft > nright else nright
#求解二叉树的宽度，节点数最多的一层的节点数即为二叉树的宽度
def treeWidth(root):
if root is None:
return 0
max_width=0
s=[]
s.append(root)
while len(s)>0:
width=len(s)
if width>max_width:
max_width=width
for i in range(width):
node=s.pop(0)
if node.left is not None:
s.append(node.left)
if node.right is not None:
s.append(node.right)
return max_width
三、判断是否为子树
#如果两个节点值相同，则继续判断下面节点值是否也相等
def isPart(pRoot1,pRoot2):if pRoot2 is None:
return True
if pRoot1 is None:
return False
if pRoot1.val!=pRoot2.val:
return False
return isPart(pRoot1.left,pRoot2.left) and isPart(pRoot1.right,pRoot2.right)
def HasSubtree(pRoot1, pRoot2):
res=False
if pRoot1 is not None and pRoot2 is not None:
if pRoot1.val==pRoot2.val:
res=isPart(pRoot1,pRoot2)
if not res:
res=HasSubtree(pRoot1.left,pRoot2)
if not res:
res=HasSubtree(pRoot1.right,pRoot2)
return res
四、判断是否为平衡二叉树
def TreeDepth(self,root):if root is None:
return 0
nleft=self.TreeDepth(root.left)
nright=self.TreeDepth(root.right)
return nleft+1 if nleft>nright else nright+1
def IsBalanced_Solution(self, pRoot):
isBalance=True
if pRoot is None:
return isBalance
leftDepth=self.TreeDepth(pRoot.left)
rightDepth=self.TreeDepth(pRoot.right)
if abs(leftDepth-rightDepth)>1:
isBalance=False
return isBalance and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
五、判断是否为对称二叉树
def isSame(self,left,right):if left and right :
if left.val==right.val:
return self.isSame(left.left,right.right) and self.isSame(left.right,right.left)
else:
return False
elif not left and not right:
return True
else:
return False
def isSymmetrical(self, pRoot):
if pRoot is None:
return True
return self.isSame(pRoot.left,pRoot.right)
六、序列化与反序列化
def Serialize(self, root):if root is None:
return '#'
return str(root.val)+self.Serialize(root.left)+self.Serialize(root.right)
def Deserialize(self, s):if len(s)<=0:
return None
root=None
val=s.pop(0)
if val!='#':
root=TreeNode(int(val))
root.left=self.Deserialize(s)
root.right=self.Deserialize(s)
return root
七、查找二叉树某个值的路径（先根方式）
def findval(root,val):if root is None:
return None
s=[]
p=root
path=[] #利用先根遍历的方式进行查找，path保存那些右子树不为空的根节点，进入path说明遍历过了，以便后续判断何时出栈。
while len(s)>0 or p is not None:
if p is not None:
if p in path:
s.pop()#如果在path中了，说明之前遍历过来，就直接出栈吧，不用再向下子树遍历了
else:
s.append(p)
if p.key==val:
return s
p=p.left
else:
p=s[len(s)-1]#暂时先不出栈，看看右子树是否为空，右子树不为空，就暂时不出栈
if p.right is None or p in path:#右子树为空的，或者之前遍历过的就直接出栈吧
s.pop()
p=None
else:
path.append(p) #之前没遍历过的且其右子树不为空，那就先不出栈了，放入path中，表示遍历过了。
p=p.right
例如上图中：E的路径就是A,C ,E。 F的路径就是A,C,F.
参考来源：https://www.jianshu.com/p/bf73c8d50dc2
以上是 python 实现二叉树相关算法 的全部内容， 来源链接： utcz.com/z/388926.html
