介绍
今天我们将介绍二叉树的理论和实践基础以及遍历它的方法。
树通常是图族的子集，其构建和管理遵循一定的规则。
二叉树
二叉树是一种具体的数据结构，其中每个节点最多有两个子节点。通常每个节点都有 3 个属性：data、leftchild 和 rightchild。
它用于按“标准”对不同类型的二叉树进行分类。
让我们看看那里存在哪些类型（类）：
基于子节点数量的二叉树类型（标准：子节点的节点数量）基于级别完成的二叉树类型（标准：级别的树完成）基于节点值的二叉树类型（标准：节点值）
让我们分别看看每种类型。
基于子节点数量的二叉树类型
完整二叉树退化（或病态）树倾斜二叉树
基于级别完成的二叉树类型
完全二叉树完美二叉树平衡二叉树
基于节点值的二叉树类型
二叉搜索树avl 树红黑树b树b+树线段树
如果您想更深入地了解其中每一个，这里有完整的概述。
很好，现在我们从概念上了解什么是二叉树以及可能的类型。
现在，让我们编写代码。回想一下，二叉树由节点组成，每个节点都有数据、leftchild 和 rightchild 属性。
from typing import anyclass treenode: def __init__(self, data: any): self.data = data self.left = none self.right = none# define all the nodes we needroot = treenode('r')nodea = treenode('a')nodeb = treenode('b')nodec = treenode('c')noded = treenode('d')# connect all the nodes between each otherroot.left = nodearoot.right = nodebnodea.left = nodecnodea.right = noded# what we've got r / a b / c d
接下来至关重要的就是如何遍历二叉树。
遍历二叉树
通常来说，遍历二叉树主要有2种方式（类型），广度优先搜索（bfs）和深度优先搜索（dfs）。
bfs 表示在进入树中的下一层之前访问同一级别的节点。这意味着树是在更侧面的方向上探索的。
dfs 代表当遍历树一直向下移动到叶节点时，向下逐枝探索树。
此外，dfs 遍历还有三种类型：
预购下单后按顺序
dfs及其遍历类型
"""preorder - is done by visiting the root node first, then recursively do a pre-order traversal of the left subtree, followed by a recursive pre-order traversal of the right subtree.this traversal is "pre" order because the node is visited "before" the recursive pre-order traversal of the left and right subtrees."""def pre_order(node): if node: print(node.value) pre_order(node.left) pre_order(node.right)
"""postorder - works by recursively doing a post-order traversal of the left subtree and the right subtree, followed by a visit to the root node.what makes this traversal "post" is that visiting a node is done "after" the left and right child nodes are called recursively."""def post_order(node): if node: post_order(node.left) post_order(node.right) print(node.value)
"""inOrder - does a recursive In-order Traversal of the left subtree, visits the root node, and finally, does a recursive In-order Traversal of the right subtree.What makes this traversal "in" order, is that the node is visited in between the recursive function calls. The node is visited after the In-order Traversal of the left subtree, and before the In-order Traversal of the right subtree."""def in_order(node): if node: in_order(node.left) print(node.value) in_order(node.right)
今天就这样。总结一下，我们修改了什么是二叉树，它的类型按标准划分，以及遍历它的方法是什么。
以上就是与你交谈系列#3的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1348378.html
微信扫一扫 
支付宝扫一扫 
