Tree in Python

Python

树是计算机科学中常用的数据结构之一,常见的地方有，Java 的继承树等。 还有一些基于树的特殊数据结构，比如二叉树，B 树，等等。

本篇会讲述一些关于简单关于树的操作。

树的定义

树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

  • 每个节点有零个或多个子节点
  • 没有父节点的节点称为根节点
  • 每一个非根节点有且只有一个父节点
  • 除了根节点外，每个子节点可以分为多个不相交的子树

节选自 树(数据结构)

定义数据结构

1class TreeNode(object):
2    """
3    一个树节点
4    """
5
6    def __init__(self, value, children: list = None):
7        """
8
9        :param value: 节点的值
10        :param children: 节点的子节点，一个 TreeNode 的列表
11        """
12
13        self.value = value
14
15        if not children:
16            self.children = []
17        elif not self.value:
18            self.children = []
19        else:
20            self.children = children
21
22class Tree(object):
23    """
24    树：基本树的数据结构
25    """
26
27    def __init__(self, root: TreeNode or None):
28        """
29        传入根节点
30        :param root: 如果为 TreeNode 为根节点， 如果为 None 为空书
31        """
32        if not (root is None or isinstance(root, TreeNode)):
33            raise AttributeError('illegal root')
34        self.root = root
1class TreeNode(object):
2    """
3    一个树节点
4    """
5
6    def __init__(self, value, children: list = None):
7        """
8
9        :param value: 节点的值
10        :param children: 节点的子节点，一个 TreeNode 的列表
11        """
12
13        self.value = value
14
15        if not children:
16            self.children = []
17        elif not self.value:
18            self.children = []
19        else:
20            self.children = children
21
22class Tree(object):
23    """
24    树：基本树的数据结构
25    """
26
27    def __init__(self, root: TreeNode or None):
28        """
29        传入根节点
30        :param root: 如果为 TreeNode 为根节点， 如果为 None 为空书
31        """
32        if not (root is None or isinstance(root, TreeNode)):
33            raise AttributeError('illegal root')
34        self.root = root

前序遍历

先遍历根节点。在遍历孩子节点。 前序遍历

循环版

1def preorder_traversal_while(self):
2        """
3        树的前序遍历
4        :return: list of tree node value
5        """
6        res = []
7        if not self.root:
8            return res
9        stack = [self.root]
10
11        while len(stack):
12            node = stack.pop()
13            if not node.value:
14                continue
15            for sub_node in node.children[::-1]:
16                stack.append(sub_node)
17            res.append(node.value)
18
19        return res
1def preorder_traversal_while(self):
2        """
3        树的前序遍历
4        :return: list of tree node value
5        """
6        res = []
7        if not self.root:
8            return res
9        stack = [self.root]
10
11        while len(stack):
12            node = stack.pop()
13            if not node.value:
14                continue
15            for sub_node in node.children[::-1]:
16                stack.append(sub_node)
17            res.append(node.value)
18
19        return res

递归版

1def preorder_traversal_recursion(self):
2        """
3        树的前序遍历
4        :return: list of tree node value
5        """
6        res = []
7        if not self.root:
8            return res
9
10        def _inner(root):
11            inner_res = []
12            if root.value:
13                inner_res.append(root.value)
14                for sub_node in root.children:
15                    inner_res += _inner(sub_node)
16            return inner_res
17        return _inner(self.root)
1def preorder_traversal_recursion(self):
2        """
3        树的前序遍历
4        :return: list of tree node value
5        """
6        res = []
7        if not self.root:
8            return res
9
10        def _inner(root):
11            inner_res = []
12            if root.value:
13                inner_res.append(root.value)
14                for sub_node in root.children:
15                    inner_res += _inner(sub_node)
16            return inner_res
17        return _inner(self.root)

后序遍历

先遍历孩子节点，最后遍历根节点。

后序遍历

循环版

1def postorder_traversal_while(self):
2        """
3        树的后序遍历
4        :return: list of tree node value
5        """
6        res = []
7
8        if not self.root:
9            return res
10
11        stack = [self.root]
12
13        while len(stack):
14            node = stack.pop()
15            if not node.value:
16                continue
17            for sub_node in node.children:
18                stack.append(sub_node)
19            res.append(node.value)
20
21        return res[::-1]
1def postorder_traversal_while(self):
2        """
3        树的后序遍历
4        :return: list of tree node value
5        """
6        res = []
7
8        if not self.root:
9            return res
10
11        stack = [self.root]
12
13        while len(stack):
14            node = stack.pop()
15            if not node.value:
16                continue
17            for sub_node in node.children:
18                stack.append(sub_node)
19            res.append(node.value)
20
21        return res[::-1]

递归版

1def postorder_traversal_recursion(self):
2        """
3        树的后序遍历
4        :return: list of tree node value
5        """
6        res = []
7        if not self.root:
8            return res
9
10        def _inner(root):
11            inner_res = []
12            if root.value:
13                for sub_node in root.children:
14                    inner_res += _inner(sub_node)
15                inner_res.append(root.value)
16            return inner_res
17
18        return _inner(self.root)
1def postorder_traversal_recursion(self):
2        """
3        树的后序遍历
4        :return: list of tree node value
5        """
6        res = []
7        if not self.root:
8            return res
9
10        def _inner(root):
11            inner_res = []
12            if root.value:
13                for sub_node in root.children:
14                    inner_res += _inner(sub_node)
15                inner_res.append(root.value)
16            return inner_res
17
18        return _inner(self.root)

层次遍历

按层遍历节点。 层序遍历

循环版

1def layer_while(self):
2        """
3        树的层序遍历
4        :return: list of tree node value
5        """
6        res = []
7        if not self.root:
8            return res
9
10        queue = Queue()
11        queue.put(self.root)
12
13        while queue.qsize():
14            node = queue.get()
15            if not node.value:
16                continue
17            res.append(node.value)
18            for sub_node in node.children:
19                queue.put(sub_node)
20        return res
1def layer_while(self):
2        """
3        树的层序遍历
4        :return: list of tree node value
5        """
6        res = []
7        if not self.root:
8            return res
9
10        queue = Queue()
11        queue.put(self.root)
12
13        while queue.qsize():
14            node = queue.get()
15            if not node.value:
16                continue
17            res.append(node.value)
18            for sub_node in node.children:
19                queue.put(sub_node)
20        return res

求树的深度

计算树的最大深度。

1def depth_recursion(self):
2
3        def _inner(root, depth=1):
4            if not root.children:
5                return depth
6            return max([_inner(sub_node, depth+1) for sub_node in root.children])
7
8        return _inner(self.root)
1def depth_recursion(self):
2
3        def _inner(root, depth=1):
4            if not root.children:
5                return depth
6            return max([_inner(sub_node, depth+1) for sub_node in root.children])
7
8        return _inner(self.root)

求树的结点数

计算树一共有多少节点。

1def node_count(self):
2        def _inner(root):
3            if not root.children:
4                return 1
5            return 1 + sum([_inner(sub_node) for sub_node in root.children])
6        return _inner(self.root)
1def node_count(self):
2        def _inner(root):
3            if not root.children:
4                return 1
5            return 1 + sum([_inner(sub_node) for sub_node in root.children])
6        return _inner(self.root)

求树的叶子数

计算书中有多少没有孩子的节点。

1def leaf_count(self):
2        def _inner(root):
3            if not root.children:
4                return 1
5            return sum([_inner(sub_node) for sub_node in root.children])
6        return _inner(self.root)
1def leaf_count(self):
2        def _inner(root):
3            if not root.children:
4                return 1
5            return sum([_inner(sub_node) for sub_node in root.children])
6        return _inner(self.root)

求两个结点的最低公共祖先结点

首先需要在树中找到两个结点。 保存找到两个节点的链表。 遍历两个链表的最长公共节点，就能找到最低的公共祖先节点。 最低公共祖先节点

1def lowest_ancestor_node(self, node1, node2):
2        stack = [self.root]
3        stack1 = None
4        stack2 = None
5
6        while len(stack) and not (stack1 and stack2):
7            node = stack.pop()
8
9            if node is node1:
10                stack1 = stack[:]
11            if node is node2:
12                stack2 = stack[:]
13            if not node.value:
14                continue
15            for sub_node in node.children:
16                stack.append(sub_node)
17
18        res = self.root
19        for i in range(len(stack1)):
20            if stack1[i] == stack2[i]:
21                res = stack1[i]
22            else:
23                return res.value
24
25        return res.value
1def lowest_ancestor_node(self, node1, node2):
2        stack = [self.root]
3        stack1 = None
4        stack2 = None
5
6        while len(stack) and not (stack1 and stack2):
7            node = stack.pop()
8
9            if node is node1:
10                stack1 = stack[:]
11            if node is node2:
12                stack2 = stack[:]
13            if not node.value:
14                continue
15            for sub_node in node.children:
16                stack.append(sub_node)
17
18        res = self.root
19        for i in range(len(stack1)):
20            if stack1[i] == stack2[i]:
21                res = stack1[i]
22            else:
23                return res.value
24
25        return res.value

求任意两结点距离

首先需要在树中找到两个结点。 保存找到两个节点的链表。 在判断剩余的长度 任意两节点距离

1def two_node_distence(self, node1, node2):
2        stack = [self.root]
3        stack1 = None
4        stack2 = None
5
6        while len(stack) and not (stack1 and stack2):
7            node = stack.pop()
8
9            if node is node1:
10                stack1 = stack[:]
11            if node is node2:
12                stack2 = stack[:]
13            if not node.value:
14                continue
15            for sub_node in node.children:
16                stack.append(sub_node)
17
18        res = self.root
19        for i in range(len(stack1)):
20            if stack1[i] == stack2[i]:
21                res = stack1[i]
22            else:
23                return len(stack1) + len(stack2) - 2*i
24
25        return len(stack1) + len(stack2) - 2*i
1def two_node_distence(self, node1, node2):
2        stack = [self.root]
3        stack1 = None
4        stack2 = None
5
6        while len(stack) and not (stack1 and stack2):
7            node = stack.pop()
8
9            if node is node1:
10                stack1 = stack[:]
11            if node is node2:
12                stack2 = stack[:]
13            if not node.value:
14                continue
15            for sub_node in node.children:
16                stack.append(sub_node)
17
18        res = self.root
19        for i in range(len(stack1)):
20            if stack1[i] == stack2[i]:
21                res = stack1[i]
22            else:
23                return len(stack1) + len(stack2) - 2*i
24
25        return len(stack1) + len(stack2) - 2*i

综述

以上就是和树有关联的简单代码。 以上代码也在 Github 上发布 tree， 如有差错，欢迎提交 Issue 或 PR。

更新

  • 修复图片的 Bug