数据结构 树 – python
树是一种数据结构
树是一种可以递归定义的数据结构
树是由n 个节点组成的集合:
如果 n = 0 , 则是一颗空树；
如果n > 0, 则存在1 个节点作为树的根节点 ，其他节点可以分为m 个集合 ，每个集合本身又是一棵树，
二叉树
二叉树的链式存储：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接.
class BiTreeeNode:
def __int__(self, data):
self.data = data
self.lchild = None # 左孩子
self.rchild = None # 右孩子
二叉树的遍历
# 前序遍历
def pre_order(root):
if root:
print(root.data, end=',')
pre_order(root.lchild)
pre_order(root.rchild)
# 中序遍历
def in_order(root):
if root:
in_order(root.lchild)
print(root.data, end=',')
in_order(root.rchild)
# 后序遍历
def post_order(root):
if root:
post_order(root.lchild)
post_order(root.rchild)
print(root.data, end=',')
# 层级遍历
此处还需要导入队列
def level_order(root):
queue = deque()
queue.append(root)
while len(queue) > 0: 只要队不空
node = queue.popleft()
print(node.data, end=",")
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
二叉树搜索树
二叉搜搜索书是一颗二叉树满足性质：
设x的是二叉树的一个节点。如果y是x左子树的一个节点 ，
那么y.key<=x.key; 如果y 是x右子树的一个节点，
那么y.key>=x.key。
AVL 树 是一个自平衡的二叉搜索树
AVL 树 具有以下性质:
根据左右子树的高度之差的绝对值不能超过1
根的左右子树都是平衡二叉树
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/77135.html
