数据结构_二叉树
2023-09-11 14:21:27 时间
二叉树的创建
class Node(object):
"""节点类"""
def __init__(self, elem=-1, lchild=None, rchild=None):
self.elem = elem
self.lchild = lchild
self.rchild = rchild
class Tree(object):
"""树类"""
def __init__(self, root=None):
self.root = root
def add(self, elem):
"""为树添加节点"""
node = Node(elem)
#如果树是空的,则对根节点赋值
if self.root == None:
self.root = node
else:
queue = []
queue.append(self.root)
#对已有的节点进行层次遍历
while queue:
#弹出队列的第一个元素
cur = queue.pop(0)
if cur.lchild == None:
cur.lchild = node
return
elif cur.rchild == None:
cur.rchild = node
return
else:
#如果左右子树都不为空,加入队列继续判断
queue.append(cur.lchild)
queue.append(cur.rchild)
二叉树的层次遍历
def breadth_travel(self, root):
"""利用队列实现树的层次遍历"""
if root == None:
return
queue = []
queue.append(root)
while queue:
node = queue.pop(0)
print(node.elem,)
if node.lchild != None:
queue.append(node.lchild)
if node.rchild != None:
queue.append(node.rchild)
二叉树的深度遍历
def preorder(self, root):
"""递归实现先序遍历"""
if root == None:
return
print(root.elem)
self.preorder(root.lchild)
self.preorder(root.rchild)
def inorder(self, root):
"""递归实现中序遍历"""
if root == None:
return
self.inorder(root.lchild)
print(root.elem)
self.inorder(root.rchild)
def postorder(self, root):
"""递归实现后序遍历"""
if root == None:
return
self.postorder(root.lchild)
self.postorder(root.rchild)
print(root.elem)
2020-05-07
相关文章
- 【关于封装的那些事】 缺失封装 【关于封装的那些事】 泄露的封装 【关于封装的那些事】 不充分的封装 【图解数据结构】二叉查找树 【图解数据结构】 二叉树遍历
- 【BZOJ1864】三色二叉树(动态规划)
- 简单构建一个二叉树而且产生镜像
- 判断二叉树是否为满二叉树
- 数据结构之二叉树
- 数据结构 有序树转二叉树 (树的遍历)
- 基于C++实现(控制台)二叉树和赫夫曼树的建立存储表示及其基本操作【100010610】
- 【数据结构】二叉树
- 【数据结构】二叉树知识点详解
- 数据结构之二叉树
- 剑指offer编程题解法汇总39-平衡二叉树
- 剑指offer编程题解法汇总24-二叉树中和为某一值的路径
- 求二叉树的高度
- 数据结构 | 有关树和二叉树的详解【内附考点精析】
- LeetCode114之二叉树展开为链表(相关话题:二叉树,递归)
- 【数据结构/二叉树/公共祖先问题】题解+详细备注(共2题)
- 【数据结构/二叉树/二叉树遍历】题解+详细备注(共14题)
- 数据结构——二叉树前序、中序、后序及层次四种遍历(java语言版)
- 《数据结构》树和二叉树代码整理(C语言实现)
- 数据结构——二叉树的遍历
- [LeetCode] Second Minimum Node In a Binary Tree 二叉树中第二小的结点
- [LeetCode] Average of Levels in Binary Tree 二叉树的层平均值
- [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历
- [LeetCode] Balanced Binary Tree 平衡二叉树
- leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 从中序与后序遍历序列构造二叉树(中等)