427. 建立四叉树（Python）

Python010

427. 建立四叉树（Python）,第1张

难度：★★★☆☆

类型：二叉树

我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。树的根结点代表整个网络。对于每个结点, 它将被分等成四个孩子结点直到这个区域内的值都是相同的.

每个结点还有另外两个布尔变量: isLeaf 和 val。isLeaf 当这个节点是一个叶子结点时为真。val 变量储存叶子结点所代表的区域的值。

你的任务是使用一个四叉树表示给定的网络。下面的例子将有助于你理解这个问题：

给定下面这个8 x 8 网络，我们将这样建立一个对应的四叉树：

由上文的定义，它能被这样分割：

对应的四叉树应该像下面这样，每个结点由一对 (isLeaf, val) 所代表.

对于非叶子结点，val 可以是任意的，所以使用 * 代替。

题目中四叉树的构建是为了表示一个布尔方阵，我们的构建遵循构建法则，我们定义一个构建函数，实现构建指定区域四叉树的功能，通过递归调用本函数实现所有四叉树结点的构建。这里重点介绍使用函数递归调用实现四叉树构建的思路：

1. 函数的功能

实现指定范围的四叉树构建。

2. 函数的输入和输出

我们设计的四叉树，需要只需要输入要构建网格中四叉树的网格即可。不过我们这里为了便于递归，把整个网格作为每次递归函数的输入，并且指定要构建四叉树的范围，这里的范围用左上角坐标和区域边长来表示。

函数的输出是根据指定网格构建而成的四叉树，换句话说，这个四叉树是输入网格的唯一表示。

3. 函数的实现

如有疑问或建议，欢迎评论区留言~

# 这里有一个示例，你可以看一下。

# http://scikit-learn.org/stable/modules/tree.html

>>> from IPython.display import Image  

>>> dot_data = tree.export_graphviz(clf, out_file=None, 

                        feature_names=iris.feature_names,  

                        class_names=iris.target_names,  

                        filled=True, rounded=True,  

                        special_characters=True)  

>>> graph = pydotplus.graph_from_dot_data(dot_data)  

>>> Image(graph.create_png())