Python数据结构 二叉树的遍历
本帖最后由 moonandflower 于 2021-8-23 10:56 编辑先定义二叉树的class
#二叉树
class BiTree:
def __init__(self, data, lchild=None,rchild=None,root=None):
self.__data=data
# 左节点
if isinstance(lchild, BiTree):
self.lchild = lchild
else:
self.lchild = None
# 右节点
if isinstance(rchild, BiTree):
self.rchild = rchild
else:
self.rchild = None
# 根节点
if isinstance(root, BiTree):
self.root = root
else:
self.root = None
定义方法
# 添加左节点
def addl(self, bt):
if isinstance(bt, BiTree):
if self.lchild == None:
self.lchild = bt
elif bt.root == None:
bt.root = self
# 添加右节点
def addr(self, bt):
if isinstance(bt, BiTree):
if self.rchild == None:
self.rchild = bt
elif bt.root == None:
bt.root = self
def add(self,lbt,rbt):
if lbt:
self.addl(lbt)
if rbt:
self.addr(rbt)
# 获取数据
def get(self):
return self.__data
遍历的方法
先根遍历（DLR）
# 递归
def first_order0(self):
print(self.get())
if self.lchild:
self.lchild.first_order0()
if self.rchild:
self.rchild.first_order0()
# 非递归
def first_order(self):
stack = []
stack.append(self)
while len(stack)>0:
btemp = stack.pop()
print(btemp.get())
if btemp.rchild:
stack.append(btemp.rchild)
if btemp.lchild:
stack.append(btemp.lchild)
中序遍历（LDR）
# 中序遍历
# 递归
def mesoorder0(self):
if self.lchild:
self.lchild.mesoorder0()
print(self.get())
if self.rchild:
self.rchild.mesoorder0()
# 非递归
# 解法1 由于要判断整个temp列表，所以耗时慢
def mesoorder(self):
stack = []
temp = []
stack.append(self)
while len(stack)>0:
if stack[-1].lchild and stack[-1].lchild not in temp:
stack.append(stack[-1].lchild)
# print(stack)
else:
btemp = stack.pop()
temp.append(btemp)
print(btemp.get())
if btemp.rchild:
stack.append(btemp.rchild)
pass
# 解法2 推荐
def mesoorder2(self):
b = self
stack = []
while len(stack)>0 or b:
while b:
stack.append(b)
b = b.lchild
if len(stack)>0:
btemp = stack.pop()
print(btemp.get())
b = btemp.rchild
# 解法3 推荐
def mesoorder3(self):
b = self
stack = []
while len(stack)>0 or b:
if b:
stack.append(b)
b = b.lchild
else:
btemp = stack.pop()
print(btemp.get())
b = btemp.rchild
后根遍历（LRD）
# 后序遍历（后根）
# 递归
def posterior_order0(self):
if self.lchild:
self.lchild.posterior_order0()
if self.rchild:
self.rchild.posterior_order0()
print(self.get())
# 非递归
# 解法1 由于要判断整个temp列表，所以耗时慢
def posterior_order(self):
stack = []
temp = []
stack.append(self)
while len(stack)>0:
b = stack[-1]
if b.rchild and b.rchild not in temp:
stack.append(b.rchild)
if b.lchild and b.lchild not in temp:
stack.append(b.lchild)
else:
btemp = stack.pop()
temp.append(btemp)
print(btemp.get())
# 解法2 推荐
def posterior_order2(self):
stack = []
temp = []
stack.append(self)
while len(stack)>0:
btemp = stack.pop()
temp.append(btemp)
if btemp.lchild:
stack.append(btemp.lchild)
if btemp.rchild:
stack.append(btemp.rchild)
while len(temp):
b = temp.pop()
print(b.get())
页:
[1]