class BinaryTreeNode:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root = None
def maketree(self, data, left, right):
self.root = BinaryTreeNode(data, left, right)
def create(self):
#data = input()
data = testdata.pop()
if data == 0:
return None
else:
self.maketree(data, BinaryTree(), BinaryTree())
if not self.root.left.create():
self.root.left = None
if not self.root.right.create():
self.root.right = None
return True
def is_empty(self):
if self.root is None:
return True
else:
return False
def pre_order(self, r):
if r.root is not None:
print r.root.data
if r.root.left is not None:
self.pre_order(r.root.left)
if r.root.right is not None:
self.pre_order(r.root.right)
def pre_order_nonrecursion(self):
stack = []
# initialize stack
stack.append(self.root)
while len(stack) != 0:
p = stack.pop()
print p.data
if p.right is not None:
stack.append(p.right.root)
if p.left is not None:
stack.append(p.left.root)
def in_order(self, r):
if r.root is not None:
if r.root.left is not None:
self.in_order(r.root.left)
print r.root.data
if r.root.right is not None:
self.in_order(r.root.right)
def in_order_nonrecursion(self):
stack = []
# initialize stack
stack.append(self.root)
p = self.root
while p.left is not None:
stack.append(p.left.root)
p = p.left.root
while len(stack) != 0:
p = stack.pop()
print p.data
if p.right is not None:
stack.append(p.right.root)
p = p.right.root
while p.left is not None:
stack.append(p.left.root)
p = p.left.root
def post_order(self, r):
if r.root is not None:
if r.root.left is not None:
self.post_order(r.root.left)
if r.root.right is not None:
self.post_order(r.root.right)
print r.root.data
def post_order_nonrecursion(self):
stack = []
# initialize stack
stack.append(self.root)
p = self.root
while p.left is not None or p.right is not None:
if p.right is not None and p.left is not None:
stack.append(p.right.root)
stack.append(p.left.root)
p = p.left.root
if p.right is not None and p.left is None:
stack.append(p.right.root)
p = p.right.root
if p.right is None and p.left is not None:
stack.append(p.left.root)
p = p.left.root
poplist = []
while len(stack) != 0:
tobepoped = stack[-1]
flag = True
if tobepoped.left is None and tobepoped.right is None:
p = stack.pop()
poplist.append(p)
print p.data
elif tobepoped.left is not None and tobepoped.left.root in poplist:
p = stack.pop()
poplist.append(p)
print p.data
flag = False
elif flag and tobepoped.right is not None and tobepoped.right.root in poplist:
p = stack.pop()
poplist.append(p)
print p.data
else:
p = stack[-1]
while p.left is not None or p.right is not None:
if p.right is not None and p.left is not None:
stack.append(p.right.root)
stack.append(p.left.root)
p = p.left.root
if p.right is not None and p.left is None:
stack.append(p.right.root)
p = p.right.root
if p.right is None and p.left is not None:
stack.append(p.left.root)
p = p.left.root
def post_order_nonrecursion_v1(self):
stack_1 = []
stack_2 = []
stack_1.append(self.root)
while len(stack_1) != 0:
p = stack_1.pop()
stack_2.append(p.data)
if p.left is not None:
stack_1.append(p.left.root)
if p.right is not None:
stack_1.append(p.right.root)
stack_2.reverse()
print stack_2
def level_order(self):
q = []
p = self.root
print p.data
while p is not None:
if p.left is not None:
q.append(p.left.root)
if p.right is not None:
q.append(p.right.root)
if len(q) == 0:
p = None
else:
p = q.pop(0)
print p.data
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
