python实现二叉树
2020-07-26 本文已影响0人
于饼喵
概念：二叉树是指模拟的树状结构，每个节点最多有两个子树的树结构，即左子树和右子树的数据集合【可以看成是对链表的一个扩充】
1.1 python实现二叉树
1.1.1 构造节点
- 类似链表节点的构造方法
- 初始时左右节点分别为None
- elem属性等于传入的item值
class Node(object):
def __init__(self,item):
"""定义当前节点和左右子节点"""
self.elem = item
self.lchild = None # 左节点
self.rchild = None # 右节点
1.1.2 构造方法
- 构造根节点，初始值设置为None
- 区别于链表的构造方法，不需要设置为私有属性，构造时不传入参数【即创建空树】 tree = Tree()
class Tree(object):
def __init__(self):
# 区别于链表的私有属性
# 构造时使用tree = Tree()即可
self.root = None
1.1.3 add方法
- 使用队列的思想进行添加，在队列中不断地添加和取出需要遍历的节点，逐个判断，将新节点添加到遍历到的空节点上
- 当根节点为None时，直接将需要添加的节点作为根节点
当根节点不为None时，对其左右节点进行判断，存在空节点时则将新添加节点赋在空节点位置，然后结束函数；否则将左右节点添加到队列，继续进行遍历判断。
def add(self,item):
"""始终在尾部添加"""
# 使用队列的思想进行遍历
node = Node(item)
if self.root is None:
self.root = node
return
queue = [self.root] # 先添加根节点
while queue:
# 从队列左边取元素，右边添加元素
cur_node = queue.pop(0)
# 左节点为空时，则直接添加node到左节点
if cur_node.lchild is None:
cur_node.lchile = node
return
else:
queue.append(cur_node.lchild)
# 右节点为空时，则添加node到右节点
if cur_node.rchild is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.rchild)
1.1.4 遍历
- 层次遍历：一层一层进行遍历，与add思路相同
- 先序遍历：按 根 --> 左节点 --> 右节点 进行遍历，使用递归思想【node代表传入的根节点】
- 中序遍历：左节点 --> 根 --> 右节点
- 后序遍历：左 --> 右 --> 根
def breadth_travel(self):
"""广度遍历 -- 层次遍历，与add思路相同"""
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.elem)
if cur_node.lchild is not None:
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append(cur_node.rchild)
def preorder(self,node):
# 先序遍历 根 -> 左 -> 右
# 这里的node代表根节点
if node is None:
return
print(node.elem)
self.preorder(node.lchild) # 遍历左节点
self.preorder(node.rchild) # 遍历右节点
def inorder(self,node):
# 中序遍历 左 -> 根 -> 右
if node is None:
return
self.inorder(node.lchild)
print(node.elem)
self.inorder(node.rchild)
def postorder(self,node):
# 后序遍历 左 -> 右 -> 根
if node is None:
return
self.postorder(node.lchild)
self.postorder(node.rchild)
print(node.elem)
1.2 完整代码
class Node(object):
def __init__(self,item):
"""定义当前节点和左右子节点"""
self.elem = item
self.lchild = None # 左节点
self.rchild = None # 右节点
class Tree(object):
def __init__(self):
# 区别于链表的私有属性
# 构造时使用tree = Tree()即可
self.root = None
def add(self,item):
"""始终在尾部添加"""
# 使用队列的思想进行遍历
node = Node(item)
if self.root is None:
self.root = node
return
queue = [self.root] # 先添加根节点
while queue:
# 从队列左边取元素，右边添加元素
cur_node = queue.pop(0)
# 左节点为空时，则直接添加node到左节点
if cur_node.lchild is None:
cur_node.lchile = node
return
else:
queue.append(cur_node.lchild)
# 右节点为空时，则添加node到右节点
if cur_node.rchild is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.rchild)
def breadth_travel(self):
"""广度遍历 -- 层次遍历，与add思路相同"""
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.elem)
if cur_node.lchild is not None:
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append(cur_node.rchild)
def preorder(self,node):
# 先序遍历 根 -> 左 -> 右
# 这里的node代表根节点
if node is None:
return
print(node.elem)
self.preorder(node.lchild) # 遍历左节点
self.preorder(node.rchild) # 遍历右节点
def inorder(self,node):
# 中序遍历 左 -> 根 -> 右
if node is None:
return
self.inorder(node.lchild)
print(node.elem)
self.inorder(node.rchild)
def postorder(self,node):
# 后序遍历 左 -> 右 -> 根
if node is None:
return
self.postorder(node.lchild)
self.postorder(node.rchild)
print(node.elem)
