Python 二叉树的创建和遍历、重建

Python012

Python 二叉树的创建和遍历、重建,第1张

几个有限元素的集合，该集合为空或者由一个根（Root）的元素及两不相交的（左子树和右子树）的二叉树组成，是有序树，当集合为空时，称为空二叉树，在二叉树中，一个元素也称为一个结点。

前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

中序遍历：若树为空，则空操作返回，否则从根结点开始（不是先访问根结点），中序遍历根结点的左子树，然后访问根节点，最后中序遍历右子树。

后序遍历：若树为空，则空操作返回，否则从左到右先访问叶子结点后结点的方式遍历左右子树，最后访问根节点。

层序遍历：若树为空，则空操作返回，否则从树的每一层，即从根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

假设已知后序遍历和中序遍历结果，从后序遍历的结果可以等到最后一个访问的结点是根节点，对于最简单的二叉树，此时在中序遍历中找到根节点之后，可以分辨出左右子树，这样就可以重建出这个最简单的二叉树了。而对于更为复杂的二叉树，重建得到根结点和暂时混乱的左右结点，通过递归将左右结点依次重建为子二叉树，即可完成整个二叉树的重建。（在得到根结点之后，需要在中序遍历序列中寻找根结点的位置，并将中序序列拆分为左右部分，所以要求序列中不能有相同的数字，这是序列重建为二叉树的前提。）

Root =None

strs="abc##d##e##"   #前序遍历扩展的二叉树序列

vals =list(strs)

Roots=Create_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。

print(Roots)

inorderSearch = inOrderTraverse2(Roots)

print(inorderSearch)

那么如何做到溯源，要求docker file中From 或者Label字段上记录该image的上游。如果能保证按照这条规则执行，那么我们会得到类似于这样的信息：

继续思考：观察数据会发现好多image会有同样的base image，那么针对这些image，我们需要将他们归并到一条分支上。或者说要找出他们的祖先，将他们归并道对应的祖先分支上。那么思想和树很像了，决定用树形结构来处理。

简化抽象需求，画出简图如下：

使用python treelib模块构造多叉树：

将每一层的树节点的id，编为child1，child11...child2，child22...同一层后缀数字一样，个数不一样，不同层数字不一样，以此类推。这样的好处就是我能根据节点ID，就知道它属于第几层。

一、什么是深度优先遍历

深度优先遍历算法是经典的图论算法。从某个节点v出发开始进行搜索。不断搜索直到该节点所有的边都被遍历完，当节点v所有的边都被遍历完以后，深度优先遍历算法则需要回溯到v以前驱节点来继续搜索这个节点。

注意：深度优先遍历问题一定要按照规则尝试所有的可能才行。

二、二叉树

2.二叉树类型

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

空二叉树：有零个节点

完美二叉树：每一层节点都是满的二叉树（如1中举例的图）

满二叉树：每一个节点都有零个或者两个子节点

完全二叉树：出最后一层外，每一层节点都是满的，并且最后一层节点全部从左排列

平衡二叉树：每个节点的两个子树的深度相差不超过1.

注：国内对完美二叉树和满二叉树定义相同

3.二叉树相关术语

术语 解释

度 节点的度为节点的子树个数

叶子节点度为零的节点

分支节点度不为零的节点

孩子节点节点下的两个子节点

双亲节点节点上一层的源节点

兄弟节点拥有同一双亲节点的节点

根 二叉树的源头节点

深度 二叉树中节点的层的数量

DLR（先序）：

LDR（中序）：

LRD(后序）：

注意：L代表左子树R代表右子树；D代表根

6.深度优先遍历和广度优先遍历

深度优先遍历：前序、中序和后序都是深度优先遍历

从根节点出发直奔最远节点，

广度优先遍历：首先访问举例根节点最近的节点，按层次递进，以广度优先遍历上图的顺序为：1-2-3-4-5-6-7

三、面试题+励志

企鹅运维面试题：

1.二叉树遍历顺序：看上文

2.用你熟悉的语言说说怎么创建二叉树？ python看上文