『二叉树』详解「广度遍历・深度遍历」的Python实现
hokyo
发布于 4 年, 7 ヶ月 之前
2278
1. 整体概念
本来只是想写个堆排序的，谁知道因为种种原因有很多不懂的，越写越长。
所以就在这里整理出来，分为二叉树和堆，2篇文章。
先把结构理顺一下。
想知道什么是堆排序就要按照这个顺序依次向下了解有个全局意识。
树→二叉树→完全二叉树→堆→堆化→堆排序
2. 关于树
2-1 什么是树
树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。
树，是节点（node）的集合（A tree is a collection of nodes）。
它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
- 每个节点有零个或多个子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树；
简言之，就是现实生活中的树倒过来而已！
2-1-1 树的几个重要概念
- 根节点root 。不用说了，一个数只有一个跟，操作系统只有1个根目录，唯一性！
- 子节点child・父节点parent。 有爸爸的节点就是子节点，有儿子的节点就是父节点。
- 树叶leaves 。最后一层，没有任何子节点的就是树叶。
- 深度(高度)。就是层次。金字塔一样，看到顶尖有几层就多少度
※有一种说法是分开高度很深度，深度相对于节点而言，高度针对于整个树而言。
18 # Root 根节点 ---第一层 / \ 15 30 # parent/child 父节点/子节点 ---第二层 / \ / \ 40 50 100 40 # leaves 叶子 ---第三层
2-1-2 树的应用场景
1.xml，html等，那么编写这些东西的解析器的时候，不可避免用到树
2.路由协议就是使用了树的算法
3.mysql数据库索引
4.文件系统的目录结构
5.所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构
※ 给个小建议，学习数据结构或者计算机一定要学好专用名词的英语。原因不外乎有这几个，1就是有些名词翻译过来会有多个版本，容易引起混淆，但是英文只有一个。2 在遇到中文资源无法解决的问题时，可以通过专用名词来查找外网。（这真的跟你英文能力无关，就是个单词而已）
2-2 树的分类
树有很多种类，下面有个图，但我们重点讨论的是其中的1个种类。二叉树。
此处应该有个图
目前还没。。。
2-2 什么是二叉树 Binary Tree
二叉树是每个节点最多有两个子树的树结构。通常子树被称作「左子树」（left subtree）和「右子树」（right subtree）。就是只能有2个分叉！
2-2-1 二叉树特性
a. 第i层的结点最多有2i>个
b. 高度为k的二叉树最多有2(k+1)-1个结点 （空树的高度为-1）
c. 对于任意一颗二叉树。其叶子结点树定为m，所有度为2的结点定位n 那么 m-n = 1
2-3 什么是完全二叉树 Complete Binary Tree
这个就是二叉树的进一步分类得来的，其实就是按照从上到下从左到右的顺序进行排列的二叉树。
以下都是二叉树。
18 / \ 15 30 / \ / \ 40 50 100 40 18 / \ 15 30 / \ / \ 40 50 100 40 / \ / 8 7 9
其中容易跟完全二叉树混淆的有几个概念。
- Full Binary Tree 满二叉树
- Perfect Binary Tree 完美二叉树
- Balanced Binary Tree 平衡二叉树
3.代码实现二叉树遍历
3-1 二叉树&添加节点
# 节点类 class Node(object): def __init__(self, elem): # 初始化 root节点，左子节点，右子节点 self.elem = elem self.lchild = None self.rchild = None # 树类 class Tree(object): # 初始化一个空节点 def __init__(self): self.root = None # 增加节点 def add(self, elem): node = Node(elem) if self.root is None: self.root = node return # 这里很重要的地方在于用一个队列来存放节点 queue = [self.root] # 只要队列不为空就继续遍历 while queue: # pop出来最后的节点 current_node = queue.pop(0) if current_node.lchild is None: current_node.lchild = node return else: queue.append(current_node.lchild) if current_node.rchild is None: current_node.rchild = node return else: queue.append(current_node.rchild)
3-2 广度遍历
DFS => Depth First Search 深度优先
BFS => Breadth First Search 广度优先
# 广度遍历 def breath_travle(self): if self.root is None: return queue = [self.root] # 只要队列不为空就继续遍历 while queue: current_node = queue.pop(0) print(current_node.elem, end=' ') if current_node.lchild is not None: queue.append(current_node.lchild) if current_node.rchild is not None: queue.append(current_node.rchild)
3-3 深度遍历(先序・中序・后序)
# 深度遍历（先序) def preorder(self, node): if node is None: return print(node.elem, end=' ') self.preorder(node.lchild) self.preorder(node.rchild) # 深度遍历（中序) def inorder(self, node): if node is None: return self.inorder(node.lchild) print(node.elem, end=' ') self.inorder(node.rchild) # 深度遍历（后序) def postorder(self, node): if node is None: return self.postorder(node.lchild) self.postorder(node.rchild) print(node.elem, end=' ')
3-4 验证合体
# 节点类 class Node(object): def __init__(self, elem): self.elem = elem self.lchild = None self.rchild = None # 树类 class Tree(object): def __init__(self): self.root = None # 增加节点 def add(self, elem): node = Node(elem) if self.root is None: self.root = node return # 这里很重要的地方在于用一个队列来存放节点 queue = [self.root] # 只要队列不为空就继续遍历 while queue: # pop出来最后的节点 current_node = queue.pop(0) if current_node.lchild is None: current_node.lchild = node return else: queue.append(current_node.lchild) if current_node.rchild is None: current_node.rchild = node return else: queue.append(current_node.rchild) # 广度遍历 def breath_travle(self): if self.root is None: return queue = [self.root] # 只要队列不为空就继续遍历 while queue: current_node = queue.pop(0) print(current_node.elem, end=' ') if current_node.lchild is not None: queue.append(current_node.lchild) if current_node.rchild is not None: queue.append(current_node.rchild) # 深度遍历（先序) def preorder(self, node): if node is None: return print(node.elem, end=' ') self.preorder(node.lchild) self.preorder(node.rchild) # 深度遍历（中序) def inorder(self, node): if node is None: return self.inorder(node.lchild) print(node.elem, end=' ') self.inorder(node.rchild) # 深度遍历（后序) def postorder(self, node): if node is None: return self.postorder(node.lchild) self.postorder(node.rchild) print(node.elem, end=' ') if __name__ == "__main__": tree = Tree() tree.add(0) tree.add(1) tree.add(2) tree.add(3) tree.add(4) tree.add(5) tree.add(6) tree.add(7) tree.add(8) tree.add(9) print('---广度遍历---') tree.breath_travle() print("") print('---深度遍历（先序)---') tree.preorder(tree.root) print("") print('---深度遍历（中序---') tree.inorder(tree.root) print("") print('---深度遍历（后序---') tree.postorder(tree.root) print("") # result # ---广度遍历--- # 0 1 2 3 4 5 6 7 8 9 # ---深度遍历（先序)--- # 0 1 3 7 8 4 9 2 5 6 # ---深度遍历（中序--- # 7 3 8 1 9 4 0 5 2 6 # ---深度遍历（后序--- # 7 8 3 9 4 1 5 6 2 0
最后
如果你看完了全部，那么恭喜你！！！
接下来这是我写的堆排序的理解，希望能对你有所帮助。
共有评论(0)