Python数据结构 二叉树的遍历

moonandflower

先定义二叉树的class

[Python] 纯文本查看 复制代码

#二叉树
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

定义方法

[Python] 纯文本查看 复制代码

# 添加左节点
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）

[Python] 纯文本查看 复制代码

# 递归
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）

[Python] 纯文本查看 复制代码

# 中序遍历
# 递归
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）

[Python] 纯文本查看 复制代码

# 后序遍历（后根）
# 递归
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())