第17讲：树结构及经典考题剖析

本课时我们主要讲解树结构，以及剖析树结构相关的考题。

树结构定义

首先，我们先来看下什么是树结构，树结构的定义是如果有一种数据，它既有自己的核心字段，同时又有指向它的若干个子节点，其中子节点下面又可以嵌套更多的子节点，这样便形成了一定的层级关系，这种结构看起来像是一颗翻转过来的树，所以被称为树结构。

如图所示，在树结构里，A 节点包含了 B 节点和 C 节点，B 节点下面又包含了三个其他的子节点，数据一层一层往下扩展。

在树结构里还有一种特例，就是二叉树。二叉树是指所有的节点最多只能有两个子节点，这种树结构我们便称之为二叉树。二叉树是面试中经常会被问到的考题，但是对普通的树形结构的处理反而是我们测试中经常会用到的。所以二叉树的处理和普通树结构的处理，你都需要掌握。

那么普通的树结构在什么地方会用到呢？比如我们打开一个网站，这个网站有很多页面，这些页面又都是层级逻辑关系，也就是进入一层界面处理一层界面的操作逻辑，然后又进入另外一个界面，所有的界面的层级便构成了一个复杂的树结构。产品经理在设计 App 或网站的时候，也是一个层级结构。除此之外，还有很多我们测试中用到的结构其实也都是树结构。

二叉树

讲完了树结构，我们来了解到底什么是二叉树。

树结构其实是由一个核心的数据和一堆指向节点的链接组成。二叉树则是树结构的一种特例，二叉树每个节点下最多只能有两个子节点，所以我们可以使用 left、right 进行表示。如果有更多的子树，你还可以使用 self.children，把所有子节点放到 children 中进行描述。

class BTree：
    def __init__(self,data=None):
        self.data = data
        self.left = None
        self.right = None
        # slef.children =[]

本课时我们就先以二叉树的例子来给你讲解树结构，以及如何做相关的常见的数据处理。

了解了二叉树的基本定义，接下来我们从零开始创建一个二叉树。

让我们回到 IDE，创建一个 BTree 的类，和链表类似，我们先创建出一个树结构。树结构有一个核心的数据，那这个数据从哪里来呢？当然是需要我们传入进来，所以我们定义一个参数，这里为了简单方便直接给定一个默认值。

二叉树最多有两个节点，所以我们分别使用 left 及 right 作为代表。如果还有更多的子节点则使用 children，在 children 中其实使用了一个结构，如果它里面有节点，我们就可以往里面插入更多的节点，所以说不同的树结构是非常相似的。

class TestBTee:
    def test_create(self)

我们先创建一个测试用例。在这里构建一个二叉树描述我们今天的 demo 数据。

class TestBTee:
    """
    0
    1 2
    3 4 | 5 6
    none none | none none | none none | 7 none|
    """ 
    def test_create(self):

我们先来描述下我们想要的二叉树结构。0 下面有 1、2 两个节点，1 下面又分 3、4 两个节点，2 下面又分 5、6 两个节点，其中 6下面只有一个节点 7。

好，那么这个结构相信你已经理解了，接下来我们去创建这样的一个结构。

def test_create(self):
    tree=BTree(0)
    tree.left=BTree(1)
    tree.right=BTree(2)
    tree.left.left=BTree(3)
    tree.left.right=BTree(4)
    tree.right.left=BTree(5)
    tree.right.right=BTree(6)
    tree.right.right.left=BTree(7)

首先，我们使用一个 tree 变量，让其等于 BTree(0)，你可以从底层开始进行创建，也可以从上层开始创建，我们就先从上层开始构建，过程参考代码。

当然这样创建树形结构打的字比较多，你也可以自己写一个构建函数来模拟这个操作，我这里就先临时这么写，简单构建一个小的二叉树，它一共有 4 层。

def travel(self):
    print(self.data)
    print(self.left)
    print(self.right)

构建完二叉树后，我们第一个操作就是打印这个树形结构，我们使用 travel，那么 travel 怎么对树进行遍历呢？我们先写一个最简单的方法，首先打印根节点，然后再打印它的左节点和右节点。

但是这样打印，我们只能打印出来一层，可是下面还有很多层，它是一个层级关系，每个子节点又是一个新的树。所以你觉不觉得处理起来像递归用法呢？接下来我们就写一个递归的算法遍历树形结构，我们把它改造成一种递归。

def travel(subtree):
    print(subtree.data)
    print(subtree.left)
    print(subtree.right)

首先，self 不可能一直都是根节点，它是需要再找到子树的，所以我们将 self 改为 subTree。但是这样只是完成了第一步，它还可以支持传参。这样就完成了一个递归思路，通过这个办法，我们可以先打印核心的根节点，然后再打印 left 和 right，而在打印 left 的时候，left 可能又有新的子节点，所以又把它传递一次递归，这样就打印了左节点的数据，接着再打印左节点下面的左节点。

def travel(self,subtree):
    if subtree is None:
        return
    print(subtree.data)
    self.travel(subtree.left)

那么，什么时候终止呢？这里我们需要添加一个递归的终止条件，这个终止条件就是 if subtree is none，如果是 none 的话，就直接退出；如果不是的话，就直接打印数据。

tree.travel(tree)

我们写完这个算法之后就需要检查数据到底对不对，所以这里写一个 tree.travel，因为它是参数化的，所以需要传参，这里传入的是二叉树自身。

这个函数看起来有点啰嗦，我们可以再写一个新的函数，把整个调用封装起来，把它改造成内部的函数。

@classmethod
def travel(cls,subtree):
    if subtree is None:
        return
    print(subtree.data)
    cls.travel(subtree.left)
    cls.travel(subtree.right)

classTestBTee:
    """
    0
    1 2
    3 4 | 5 6
    none none | none none | none none | 7 none|
    """ 
    def test_create(self):
        tree=BTree(0)
        tree.left=BTree(1)
        tree.right=BTree(2)
        tree.left.left=BTree(3)
        tree.left.right=BTree(4)
        tree.right.left=BTree(5)
        tree.right.right=BTree(6)
        tree.right.right.left=BTree(7)
        
        BTree.travel(tree)

或者，你也可以在这儿加一个 @classmethod，把 self 换成 cls，这样效果也是一样的。这样就可以使用 BTree 方法打印了。

整个遍历的过程需要我们注意，它根据根节点打印的先后顺序，分为前序、中序和后序。前序指的是核心数据节点先打印出来，而核心数据如果放在左右节点的中间就叫作中序，其次是后序。

我们来看下打印的结果值，因为是按照前序遍历打印数据，所以第一个打印的是根节点 0，其次是左节点 1，然后是左节点的左节点 3，以此类推，结果按照0、 1、2、4、5、6、7 全部打印出来。

@classmethod
def travel(cls,subtree):
    if subtree is None:
        return
        
    cls.travel(subtree.left)
    print(subtree.data)
    cls.travle(subtree.right)

如果现在我们把这个节点放到中间呢？再次执行你会注意到这个时候变成了 3、1、4、0、5、2、7、6。这是因为我们此时是按照中序在遍历。

打印的过程中先去寻找左节点，第一个左节点是 3，3 打印完是 1，然后再寻找右节点，接着是 4，最后的结果便是 3、1、4。4 打印完后是 0，以此类推，你可以课后自己推导结果，这里就不再一一介绍了。

树形结构考题

一个简单的树的遍历，差不多就是这样一个写法，接下来我们剖析一个经典的树结构面试考题。

怎样获取一个树结构的最大深度？其实我们在一些测试工作中有时候也经常会用到这个算法。比如计算某个控件在当前界面中它属于多大的一个深度。接下来我们看下具体怎么解答这个问题。

首先，我们写一个叫作 max depth 的函数，然后我们用递归算法来计算深度。这个深度是这样子的，首先如果它即有左节点，又有右节点，那么每进去一层深度其实是要加 1 的。最后完成之后，我们计算加 1 的值最后能加到多少？你可以看到它的算法本质和遍历是一样的。我们看下它的写法是什么？

def max_depth(self,subtree,depth):
    if subtree is None:
        return depth
    
    self.max_depth(subtree.left,depth+1)
    self.max_depth(subtree.right,depth+1)
    return max_left if max_left > max_right else max_right

我们梳理下思路，首先是通过递归，因为每一次递归都会查找一个子树，所以我们需要有个树的节点传递给函数。left 或 right 就是这时被传入函数的，在传入的过程中，因为深度加 1 了，所以 depth 也需要加 1。然后通过一个终止条件，判断返回的时机，如果 left 或 right 为空就直接返回，如果不为空就进行上面说的逻辑处理，直到找到最后一层子树并返回结果。

def setup(self):
    self.tree=BTree(0)
    self.tree.left=BTree(1)
    self.tree.right=BTree(2)
    self.tree.left.left=BTree(3)
    self.tree.left.right=BTree(4)
    self.tree.right.left=BTree(5)
    self.tree.right.right=BTree(6)
    self.tree.right.right.left=BTree(7)

然后，我们验证下这个 case。

def test_travel(self):
    BTree.travel(self.tree)
    
def test_max_depth(self):
    print(self.tree.max_depth(self.tree,0))

我们再创建一个测试用例和树来测试它的深度，首先 self.tree 前面已经创建好了，这个 tree 的 max_depth 也需要传入一个子树，这里传入 self.tree。下面是获取深度的逻辑，一开始的初始值是 0，每进一层它就加 1，最后打印下最后的值是多少。

def test_max_depth(self):
    assert self.tree.max_depth(self.tree,0) == 4
    self.tree.right.right.left.left = BTree(8)
    assert self.tree.max_depth(self.tree,0) == 5

我看深度好像是 4，那么接下来我们开始写断言来证明它的值到底是不是 4。

所以通过这个办法，我们可以看到，我们就写出来一个关于 BTree 二叉树的一个经典的遍历算法，当然你觉得这个调用特别烦琐的话，你还可以创建一个新的函数，比如说：

def get_max_depth(self):
    self.max_depth(self,0)

这样使得调用变得更简单。

本课时的内容就讲到这里了，其实核心就是一个树形结构，它的遍历跟链表很相似，子节点跟父节点是类似的算法处理，所以我们可以使用递归算法计算树形的深度。