二叉树查找算法

定义树节点

class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

先序遍历，递归

def preorder(root:TreeNode):
"""递归地，先序遍历二叉树"""
if root == None:
return
else:
print(root.val)
preorder(root.left)
preorder(root.right)

中序遍历，递归

def inorder(root:TreeNode):
"""递归地，中序遍历二叉树"""
if root == None:
return
else:
inorder(root.left)
print(root.val)
inorder(root.right)

后序遍历，递归

def postorder(root:TreeNode):
"""递归地，后序遍历二叉树"""
if root == None:
return
else:
postorder(root.left)
postorder(root.right)
print(root.val)

层序遍历，递归

def levelorder(root:TreeNode):
"""递归，层序遍历二叉树"""
level=0
while printLevel(root,level):
level +=1
def printLevel(root:TreeNode, level):
"""递归，层序遍历二叉树，打印一层"""
if root==None or level<0:
return False
elif level == 0:
print(root.val)
return True
else:
return printLevel(root.left, level-1) + printLevel(root.right, level-1)

先序遍历，非递归

def preorderWithStack(root:TreeNode):
"""非递归，先序遍历二叉树"""
stack = []
pnode = root
while pnode or len(stack)>0:
while pnode:
print(pnode)
stack.append(pnode)
pnode = pnode.left
if len(stack)>0:
pnode = stack.pop().right

中序遍历，非递归

def inorderWithStack(root:TreeNode):
"""非递归，中序遍历二叉树"""
stack =[]
pnode = root
while pnode or len(stack)>0:
while pnode:
stack.append(pnode)
pnode = pnode.left
if len(stack)>0:
top = stack.pop()
print(top.val)
pnode = top.right

后序遍历，非递归，这个略复杂

def postorderWithStack(root:TreeNode):
"""非递归，后序遍历二叉树，需要记录前一个输出的节点"""
stack = []
pnode = root
stack.append(pnode)
while len(stack)>0:
top = stack[:-1]
if (not pnode.right and not pnode.left) 
or (pre and (pre==pnode.left or pre==pnode.right)):
print(top.val)
pre = stack.pop()
if pnode.right:
stack.append(pnode.right)
if pnode.left:
stack.append(pnode.left)

层序遍历，非递归

def levelorderWithStack(root:TreeNode):
"""非递归，层序遍历二叉树"""
stack=[]
stack.append(root)
tempstack = []
while len(stack)>0:
for x in stack:
print(x.val)
if x.left:
tempstack.append(x.left)
if x.right:
tempstack.append(x.right)
stack = tempstack
tempstack=[]

最后

以上就是专注心锁为你收集整理的二叉树查找算法的全部内容，希望文章能够帮你解决二叉树查找算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。