难度：★★★☆☆
类型：二叉树
我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。树的根结点代表整个网络。对于每个结点, 它将被分等成四个孩子结点直到这个区域内的值都是相同的.
每个结点还有另外两个布尔变量: isLeaf 和 val。isLeaf 当这个节点是一个叶子结点时为真。val 变量储存叶子结点所代表的区域的值。
你的任务是使用一个四叉树表示给定的网络。下面的例子将有助于你理解这个问题：
给定下面这个8 x 8 网络，我们将这样建立一个对应的四叉树：
由上文的定义，它能被这样分割：
对应的四叉树应该像下面这样，每个结点由一对 (isLeaf, val) 所代表.
对于非叶子结点，val 可以是任意的，所以使用 * 代替。
题目中四叉树的构建是为了表示一个布尔方阵，我们的构建遵循构建法则，我们定义一个构建函数，实现构建指定区域四叉树的功能，通过递归调用本函数实现所有四叉树结点的构建。这里重点介绍使用函数递归调用实现四叉树构建的思路：
1. 函数的功能
实现指定范围的四叉树构建。
2. 函数的输入和输出
我们设计的四叉树，需要只需要输入要构建网格中四叉树的网格即可。不过我们这里为了便于递归，把整个网格作为每次递归函数的输入，并且指定要构建四叉树的范围，这里的范围用左上角坐标和区域边长来表示。
函数的输出是根据指定网格构建而成的四叉树，换句话说，这个四叉树是输入网格的唯一表示。
3. 函数的实现
如有疑问或建议，欢迎评论区留言~
用python构造一个n层的完全二叉树的代码如下：typedef
struct
{int
weightint
parent,
lchild,
rchild
}
htnode
,*huffmantree
//
动态分配数组存储huffman树
算法设计void
createhuffmantree(){
ht=(huffmantree)malloc(m+1)*sizeof(htnode.
几个有限元素的集合，该集合为空或者由一个根（Root）的元素及两不相交的（左子树和右子树）的二叉树组成，是有序树，当集合为空时，称为空二叉树，在二叉树中，一个元素也称为一个结点。
前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树
中序遍历：若树为空，则空操作返回，否则从根结点开始（不是先访问根结点），中序遍历根结点的左子树，然后访问根节点，最后中序遍历右子树。
后序遍历：若树为空，则空操作返回，否则从左到右先访问叶子结点后结点的方式遍历左右子树，最后访问根节点。
层序遍历：若树为空，则空操作返回，否则从树的每一层，即从根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
假设已知后序遍历和中序遍历结果，从后序遍历的结果可以等到最后一个访问的结点是根节点，对于最简单的二叉树，此时在中序遍历中找到根节点之后，可以分辨出左右子树，这样就可以重建出这个最简单的二叉树了。而对于更为复杂的二叉树，重建得到根结点和暂时混乱的左右结点，通过递归将左右结点依次重建为子二叉树，即可完成整个二叉树的重建。（在得到根结点之后，需要在中序遍历序列中寻找根结点的位置，并将中序序列拆分为左右部分，所以要求序列中不能有相同的数字，这是序列重建为二叉树的前提。）
Root =None
strs="abc##d##e##" #前序遍历扩展的二叉树序列
vals =list(strs)
Roots=Create_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。
print(Roots)
inorderSearch = inOrderTraverse2(Roots)
print(inorderSearch)
