Python算法系列—深度优先遍历算法【二叉树】

深度优先遍历算法之二叉树一、什么是深度优先遍历二、二叉树1. 二叉树简介2.二叉树类型3.二叉树相关术语4. 二叉树的节点代码5. 二叉树遍历顺序6.深度优先遍历和广度优先遍历三、面试题+励志

这不就是二叉树吗？嗯，风景都在提示我该学学二叉树了

一、什么是深度优先遍历

深度优先遍历算法是经典的图论算法。从某个节点v出发开始进行搜索。不断搜索直到该节点所有的边都被遍历完，当节点v所有的边都被遍历完以后，深度优先遍历算法则需要回溯到v以前驱节点来继续搜索这个节点。
注意：深度优先遍历问题一定要按照规则尝试所有的可能才行。

二、二叉树 1. 二叉树简介

二叉树是一种特殊的数据结构，常见的数据结构包含数组，链表，图、队列、散列表和树。二叉树属于树结构，二叉树中的每一个节点都有两个分支称为左子树和于右子树。二叉树每一层最多有(2n−1)(2^n - 1)(2n−1)个节点。和普通树不同，普通树的节点没有分支限制，并且普通树的节点没有左右、子树之分。

2.二叉树类型

二叉树类型：空二叉树、满二叉树、完全二叉树、完美二叉树、平衡二叉树。

空二叉树：有零个节点 完美二叉树：每一层节点都是满的二叉树（如1中举例的图） 满二叉树：每一个节点都有零个或者两个子节点 完全二叉树：出最后一层外，每一层节点都是满的，并且最后一层节点全部从左排列 平衡二叉树：每个节点的两个子树的深度相差不超过1.


注：国内对完美二叉树和满二叉树定义相同 3.二叉树相关术语

术语	解释
度	节点的度为节点的子树个数
叶子节点	度为零的节点
分支节点	度不为零的节点
孩子节点	节点下的两个子节点
双亲节点	节点上一层的源节点
兄弟节点	拥有同一双亲节点的节点
根	二叉树的源头节点
深度	二叉树中节点的层的数量

4. 二叉树的节点代码

因为每个·节点都有两个子节点相连接，所以我们只需要拥有根节点就能找到二叉树上的任意节点，每个节点定义都相同

class Node : #二叉树节点定义 def _init_(self,x): self.val = x #节点值 self.left = None #左侧子节点 self.right = None #右侧子节点 5. 二叉树遍历顺序

二叉树三种遍历形式：

DLR（先序）： LDR（中序）： LRD(后序）：
注意：L代表左子树R代表右子树；D代表根
6.深度优先遍历和广度优先遍历 深度优先遍历：前序、中序和后序都是深度优先遍历
从根节点出发直奔最远节点， 广度优先遍历：首先访问举例根节点最近的节点，按层次递进，以广度优先遍历上图的顺序为：1-2-3-4-5-6-7 三、面试题+励志

企鹅运维面试题：
1.二叉树遍历顺序：看上文
2.用你熟悉的语言说说怎么创建二叉树？ python看上文

作者：f3NWIVKIo@t5

深度优先遍历 遍历 python算法 Python 二叉树