普通树转化为二叉树的条件

普通树（n-ary tree）指的是除二叉树之外的树形结构，其中每个节点可以有任意数量的子节点。然而，在一些应用中，我们希望将普通树转化为二叉树（binary tree），即每个节点最多只有两个子节点的树形结构。本文将介绍普通树转化为二叉树的条件及其应用。

转化条件

1. 根据深度优先遍历序列（preorder traversal）转化

将普通树按照一定顺序遍历，可以得到一组序列，一般将其称为深度优先遍历序列。例如，对于下图所示的普通树，若以先根后子节点的顺序进行深度优先遍历，则得到序列1,2,4,5,6,7,3。


将该序列中相邻、但不在同一子树中的第一个节点和第二个节点的连线转化为二叉树的父子关系即可得到二叉树，如下图所示。


如果某个节点有多个子节点，则剩余子节点依次作为当前节点的右子节点的左子树进行处理。例如，在上图中，节点4有两个子节点5,6，则将5作为4的右子节点，将6作为5的左子树。类似地，节点2有两个子节点4,7，则将7作为2的右子节点，将4作为7的左子树。

2. 根据层次遍历顺序转化

另一种方式是按照层次遍历（level order traversal）的顺序对节点进行编号，将该编号作为二叉树节点的键（key），同时将每个节点所在的层数作为二叉树节点的权值（value）。然后，将普通树中每个节点的父节点于其子节点之间添加一条虚边，如下图所示。


得到的图形即为转化后的二叉树。

应用

将普通树转化为二叉树的主要应用是在搜索、排序和遍历等算法中。由于二叉树的某些性质在实际实现中十分有效，将普通树转化为二叉树可以使代码更加简洁、直观。

1. 搜索

在普通树中，搜索某个元素需要遍历所有可能的子树。转化为二叉树之后，可以直接运用二叉搜索树的性质进行查找，从而大大缩短搜索时间。

2. 排序

经过转化后，普通树中的元素可以直接通过二叉树进行排序。例如，在对普通树中元素进行快速排序时，可以将其转化为二叉树，通过中序遍历得到排序后的元素序列。

3. 遍历

与搜索类似，普通树转化为二叉树后，可以使用二叉树的遍历方式进行遍历。例如，先序遍历转化后的二叉树可以得到与深度优先遍历相同的节点序列。