实现二叉树的先序、中序、后序遍历,包括递归方式和非递归方式
程序员文章站
2022-05-16 10:09:31
...
class TreeNode:
def __init__(self,x):
self.value = x
self.right = None
self.left = None
def createTree(root):
data = input("input data")
if data == "#"
root = None
else:
root = TreeNode(element)
root.left = createTree(root.left)
root.right = createTree(root.right)
return root
"""
前序遍历
"""
def preOrderRecur(head):
if head == None:
return
print(head.value + ' ')
preOrderRecur(head.left)
preOrderRecur(head.right)
"""
中序遍历
"""
def inOrderRecur(head):
if head == None:
return
inOrderRecur(head.left)
print(head.value + ' ' )
inOrderRecur(head.right)
"""
后序遍历
"""
def posOrderRecur(head):
if head == None:
return
posOrderRecur(head.left)
posOrderRecur(head.right)
print(head.value + ' ')
"""
非递归方式
"""
def preOrderUnRecur(head):
print("pre-order:")
if head!=None:
stack = []
stack.append(head)
while len(stack)!=0:
head = stack.pop()
print(head.value + " ")
if head.right!=None:
stack.push(head.right)
if head.left!=None:
stack.push(head.left)
print(" ")
def inOrderUnRecur(head):
"""
先把所有左子树全都压入栈中
"""
print("in-order:")
if head!=None:
stack = []
while len(stack)!=0 or head!=None:
if head!= None:
stack.push(head)
head = head.left
else:
head = stack.pop()
print(head.value + " ")
head = head.right
print(" ")
def posOrderUnRecur(head):
print("pos-order:")
if head!=None:
s1 = []
s2 = []
s1.push(head)
while len(s1)!=0:
head = s1.pop()
s2.push(head)
if head.left!=None:
s1.push(head.left)
if head.right!=None:
s1.push(head.right)
while s2.isEmpty() is not True:
print(s2.pop().value + " ")
print(" ")
推荐阅读
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
左神算法:分别用递归和非递归方式实现二叉树先序、中序和后序遍历(Java版)
-
二分搜索树 BST 前序\中序\后序(递归和非递归实现)和层序遍历
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Java实现二叉树先序、中序、后序遍历(递归与非递归)及层次遍历
-
JAVA 实现二叉树建立和先序,中序和后序遍历(递归与非递归)
-
非递归实现二叉树先序、中序、后序遍历(栈实现)
-
java实现二叉树的前序、中序、后序、层次遍历,递归与非递归
-
LeetCode 二叉树的中序遍历(递归和非递归算法)