离散数学遍历二叉树遍历二叉树|离散数学

遍历意味着访问树的所有节点。有三种遍历二叉树的标准方法。这些如下：

预购遍历
邮购遍历
有序遍历

1.预遍历：二叉树的预遍历是一个递归过程。一棵树的遍历遍历为

参观树的根。
遍历左子树。
遍历右侧子树。

2.后序遍历：二叉树的后序遍历是一个递归过程。一棵树的后置遍历为

以后置顺序遍历左侧子树。
以后置顺序遍历右边的子树。
参观树的根。

3.有序遍历：二叉树的有序遍历是一个递归过程。树的有序遍历为

按顺序遍历左侧子树。
参观树的根。
按顺序遍历右侧子树。

示例：确定二叉树的前序, 后序和有序遍历, 如图所示：

解决方案：树的预排序, 后排序和有序遍历如下：

Preorder	1	2	3	4	5	6	7	8	9	10	11
Postorder	3	5	4	2	7	10	9	11	8	6	1
Inorder	3	2	5	4	1	7	6	9	10	8	11

演算法（a）给出树的有序和预序遍历时绘制唯一二叉树的算法：

我们知道二叉树的根是其预定顺序中的第一个节点。画出树的根。
要查找根节点的左子节点, 首先, 使用顺序遍历在二叉树的左子树中查找节点。（在顺序遍历中留给根节点的所有节点都是左子树的节点）。之后, 通过选择左子树的预遍历中的第一个节点来获得根的左子节点。画左孩子。
以相同的方式, 使用顺序遍历在二叉树的右子树中查找节点。然后, 通过选择右子树的预遍历中的第一个节点来获得右子级。画一个合适的孩子。
对每个新节点重复步骤2和3, 直到未按预定顺序访问每个节点。最后, 我们获得一棵唯一的树。

示例：当有序遍历和预遍历遍历如下时, 绘制唯一的二叉树：

Inorder	B	A	D	C	F	E	J	H	K	G	I
Preorder	A	B	C	D	E	F	G	H	J	K	I

解决方案：我们知道二叉树的根是预遍历中的第一个节点。现在, 检查A, 在有序遍历中, 左A的所有节点都是左子树的节点, 而右A的所有节点都是右子树的节点。阅读预购中的下一个节点, 并检查其相对于根节点的位置（如果它在根节点的左侧）, 则将其绘制为左子节点, 否则将其绘制为右子节点。对每个新节点重复上述过程, 直到读取了遍历遍历的所有节点, 最后我们得到了二叉树, 如图所示：

（b）在给出树的有序和后序遍历时绘制唯一二叉树的算法：

我们知道二叉树的根是其后序中的最后一个节点。画出树的根。
要找到根节点的右子节点, 首先, 使用顺序遍历在二叉树的右子树中找到节点。（在顺序遍历中, 根节点右边的所有节点都是右边子树的节点）。之后, 通过选择右子树的后序遍历中的最后一个节点来获得根的右子节点。画一个合适的孩子。
以相同的方式, 使用顺序遍历在二叉树的左子树中查找节点。然后, 通过选择左子树的后序遍历中的最后一个节点来获得左孩子。画左孩子。
对每个新节点重复步骤2和3, 直到在后继订购中未访问每个节点为止。访问最后一个节点后, 我们获得了唯一的树。

示例：为给定的Inorder绘制唯一的二叉树, Postorder遍历如下所示：

Inorder	4	6	10	12	8	2	1	5	7	11	13	9	3
Postorder	12	10	8	6	4	2	13	11	9	7	5	3	1

解决方案：我们知道二叉树的根是后遍历中的最后一个节点。因此, 在根节点中一个。
现在, 检查有序遍历, 我们知道根在中心, 因此, 在有序遍历中留在根节点上的所有节点都是左子树的节点, 而在根节点右边的所有节点都是正确的子树。
现在, 从后顺序遍历中从后面访问下一个节点, 并检查其在顺序遍历中的位置, 如果它在根的左侧, 则将其绘制为左子节点, 如果它在右侧, 则将其绘制为右子节点。
对每个新节点重复上述过程, 我们获得如图2所示的二叉树：

【离散数学遍历二叉树】（c）将通用树转换为二叉树的算法