Appearance
第18讲（下）：名企算法真题剖析
本课时剖析树结构的经典考题，题目是如何根据特定的顺序创建一个新的树形结构，这个顺序可以是前序、后续和中序，这也是面试中经常会被问到的一道考题，网上的标准答案已经很多了，这里我们更务实一些，使用测试工作中的经典场景来解答问题。
比如我们需要根据 html 或 xml 数据新建一个树形结构，然后计算每个节点的深度，对比新旧版本之间两个节点有什么异同，这些对于测试工作都非常有用，所以本课时就以实际工作中遇到的 html 案例来给你进行剖析。
以测试用例中的结构为例，html 下面有 head 和 body 两个节点，head 和 body 下面还各有自己不同的子节点，在我们做自动化测试时经常会遇到这种数据结构，我们也希望能从这种树形结构中反向构造一个树，以便我们做更多的数据分析。
接下来，我们就看下具体怎么解决这个问题，首先我们创建一个测试用例，这个测试用例给定一个 xml 数据并简单拼装成了 html 结构，我们希望可以通过 create_from_string 方法根据给定的字符串完整的生产一个树形结构，并可以在这个树形结构中可以断言每个节点的深度，比如 html 的深度是 1，head 的深度是 2，以此类推。
接下来，我们进入代码实现，首先需要一个测试用例，然后实现具体的算法。我们创建一个 test_tree 的文件，和前面讲过的二叉树算法不一样的地方在于这次我们需要处理 xml 数据，节点 head 下可能有多个节点，但它们本质上都是一样的，都是一个树结构。
class Tree：
def __init__(self,data):
self.data=data
self.children=[]首先，创建一个叫作 Tree 的类，它有一个初始化方法，在初始化方法中传入了一个数据，并令 self.data=data，把数据存储下来，多叉树与二叉树最大的不同在于二叉树有 left 和 right，而多叉树只需要一个列表来表达就可以了，这时我们使用 slef.children 列表来表达数据，这样我们便有了一个多叉树。
class TestTree:
def test_create_tree(self):
root=Tree("html")
head=Tree("head")
a=Tree("a")
b=Tree("b")
head.children.append(a)
head.children.append(b)
body=Tree("body")
x=Tree("x")
m=Tree("m")
m.children.append(x)
body.children.append(m)
root.children.append(head)
root.children.append(body)有了多叉树之后，我们就需要去构建它，这时需要创建一个 create_tree 的测试用例，然后根据题目要求构建一个 xml 类型的多叉树。
我们令多叉树的根节点等于 html，root节点下面有 head 和 body 两个节点，而 head 与 body 下面还有各自的子节点，我们将它们创建并添加到树中，这样就构建了一个多叉树，你可以看到构建过程还是蛮复杂的，很显然我们在日常工作中不能使用这种方法进行构建。
def travel(self,node):
print(node.data)
for child in self.children:
self.travel(child)构建完树结构之后我们就需要将它打印出来，在前面的测试用例中使用了 travel，它可以打印每个节点及对应的深度，这里我们具体实现这个方法，在 travel 方法中通常需要遍历算法来实现功能，我们先打印出 self.data，然后使用 for 循环对 data 中的每一个 child 进行遍历并打印，打印的过程逻辑都是一样的，我们使用递归算法实现，为了获取每个子节点这里需要传入一个 node 参数。
def travel(self.node=None):
#第一步递归改造
#第二步增加默认参数改造
if node is None:
node=self
print(node.data)
for child in node.children:
sef.travel(child)首先，第一步是递归改造，令传入的 node 等于 None，然后如果 node is None，这时就让 node 等于 self，这样就完成了第一步改造，第二步改造是增加默认参数。再次运行，测试用例没有问题。
但是这样打印效果仍然不是很好，并不能很好的看出层级关系，而且后面的断言也需要层级关系，所以我们接下来增加层级关系的处理逻辑。
def travel(self.node=None,depth=1):
#第一步递归改造
#第二步增加默认参数改造
#第三部改造增加depth
if node is None:
node=self
print(node.data,depth)
depth +=1
for child in node.children:
sef.travel(child,depth)
depth -=1回到递归函数，随着节点每深入一层深度也需要加 1，那么当前节点的深度到底是多少呢，我们假设第一个节点的深度是 1，depth 等于 1，然后随着递归，depth 需要+=1。当每个节点都遍历完之后，depth 再 -=1，而每一次递归深度是不一样的，所以我们需要传参进入，同样 depth 也需要给定一个初始值 1，经过这样的改造，深度的处理逻辑就追加进去了，然后我们运行测试用例，此时深度信息也可以打印出来了。
html 的深度为 1，head 的深度为2，以此类推。虽然这样就可以打印出多叉树的子节点的深度，但是这样仍然不够直观，怎么办呢？后面断言时我们需要将每个节点的深度存储到词典中，所以就需要我们把结果返回给外部函数，此时我们进行第四步改造，使用生成器。
def travel(self.node=None,depth=1):
#第一步递归改造
#第二步增加默认参数改造
#第三部改造增加depth
#第四步改造使用生成器
if node is None:
node=self
print(node.data,depth)
depth +=1
for child in node.children:
sef.travel(child,depth)
depth -= 1因为有的时候需要断言而不需要打印的，所以这时我们将 print 方法改造为 yield 方法，经过这一步改造，原有方法就变成了一个生成器，当外部调用它的时候就会自动生成每一层 node 和它的深度。
for node,depth in root.travel():
print(f"{' '*depth}{node} depth={depth}")然后我们使用 for node，depth in root.travel(): 进行打印，这样改造之后我们再次运行测试用例。
你可以看到现在只是生成了一个节点，为什么会只生成一个节点呢？是因为 yield 调用 travel 时候里面有个递归逻辑。
for child in node.children:
yield from self.travel(child,depth)
depth -=1但是已有的方法在递归中没有跑起来，所以我们需要添加一个 Python 的特殊字符 yield from，我们再次打印。
我们再次运行，一个基本的树结构就已经完全的打印出来了，有了这个树形结构我们自然要检查这个树形结构的层级对不对。
assert tree_dict["x"]==4
assert tree_dict["b"]=3
assert tree_dict["body"]==2
assert tree_dict["html"]==1我们就可以在前面添加一个词典，然后在打印的同时，将词典的 key 也就是节点的 depth 保存下来，然后就可以进行断言了，比如断言 x 的深度是不是等于 4，b 的深度是不是等于 3，等等。这就是多叉树的构建过程。
def test_create_tree_from_string(self):
xml="""
<html>
<head>
<c></c>
<d></d>
</head>
<body>
<m>
<n></n>
</m>
</body>
</html>
"""
root = Tree.create_from_string(xml)
tree_dict={}
for data,depth in root.travel():
tree_dict[data]=depth
assert tree_dict["html"]==1
assert tree_dict["head"]=2
assert tree_dict["d"]==3
assert tree_dict["x"]==4当然根据课时开始时的题目，我们需要根据 html 或 xml 生成一个多叉树而不是自己创建，接下来我们就完成对应测试用例的构建，为了节省时间我们直接将测试用例的代码复制过来，测试用例中我们构建了 html 数据，然后创建了 create_from_string 方法并创建一个词典保存了每个节点的深度，最后进行断言。
def create_from_string(self,content)->'Tree':
#第一步编写基本的字符串处理逻辑框架
#第二步创建节点
#第三步使用stack记录tree的当前父节点
key=""
root:Tree=None
stack=Stack()
for c in content:
if c is "<"
key=""
elif c is ">"
if "/" in key
#节点结束
pass
else:
#新节点
pass
else:
key+=c然后我们去编写 create_from_string 方法，这个方法需要传入一个参数并返回一个树结构，既然传入了数据，就需要遍历这个数据里的每一个字符串，所以需要使用 for c in content 进行遍历。
如果 c 是 < 符号表示这是一个结构层级的开头，说明我们遇到了一个新节点，这时需要将 key 保留下来，然后 elif c is ">" 表示该节点就已经结束了，除此之外的其他内容我就使用 key+=c 逻辑处理，但是这里有两种情况，一种是 < 表示新节点，一种是 </ 表示这时节点已经结束，所以 elif 下还有两个逻辑判断，如果 / 在我们的 key 里面我们需要做后续对应的处理，如果不在就需要创建一个新的节点。
elif c is ">"
if "/" in key
#节点结束
pass
else:
#新节点
tree=Tree(key)
if root is None:
root=tree
else:
pass
pass然后，令 tree 等于 Tree(key)，当这个节点创建完成之后如果第一次遇到 html 的时候它是一个空的，就需要返回 tree；如果不为空，我们就需要实现其他的逻辑。
当你是第一次创建的时候 root 等于 None，表示第一次创建，我需要把 tree 记录下来，然后再往后都是子节点，这时我们就需要使用栈结构来处理多叉树的层级关系，
stack=Stack()
for c in conteng:
if c in content:
key=""
else c is ">"
if "/" in key:
#节点结束
stack.pop()
else:
#新节点
tree=Tree(key)
if root is None:
root=tree
else:
stack.top().children.append(tree)
stack.push(tree)
else:
key+=c
return当根节点出现时我们需要将其进行压栈，通过 stack.push 把当前的节点压入栈，根节点处理完之后，就到了 head 节点，这时就会进入 else 逻辑，它需要在原有 stack 中进行追加，因为 head 是 html 的子节点，所以这里我们使用 stack.top，top 可以获取栈顶的元素，获取到栈顶元素后，我们可以使用 children.append 方法对树的子节点进行添加，经过这样一步方法编写，head 就可以放到 html 里面了，以此类推。
什么时候需要弹栈呢，就是当 key 遇到一个 / 的时候，这时候 if 逻辑下的 pass 就变成了 stack.pop。
整个结构都处理完之后我们需要返回 root 节点，然后跑下测试用例验证逻辑是否正确。
这时报错，我们就需要去查找原因，我们可以看到测试用例需要一个 content，因为 create_from_string 是一个类方法，我已经传入了一个参数但是它提示还缺一个参数，原因在于 tree 结构有两个参数，第一个参数要传入一个类，从目前来看调用的方法里面，它使用的是 Tree 这个数据，也就是说你调用的参数的类型是不对的，那怎么办呢？我们对于使用类而不是实例直接进行调用时，需要将它改造成一个静态方法。
我们使用 classmethod 对 create_tree_string 进行注解，然后再使用一个 cls，我们将它改造成一个类方法。
处理完成之后我们运行 case，整个 case 完全可以通过，然后我们把打印逻辑的代码复制过来并打印下这个结构。
可以发现数据结构完全正确，到这里根据 html 数据生成多叉树的处理逻辑就全部讲完了。