树的遍历于常见算法 - 基于 Python 实现

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

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

树的定义

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

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

节选自 树(数据结构)

定义数据结构

class TreeNode(object):
    """
    一个树节点
    """

    def __init__(self, value, children: list = None):
        """

        :param value: 节点的值
        :param children: 节点的子节点，一个 TreeNode 的列表
        """

        self.value = value

        if not children:
            self.children = []
        elif not self.value:
            self.children = []
        else:
            self.children = children

class Tree(object):
    """
    树：基本树的数据结构
    """

    def __init__(self, root: TreeNode or None):
        """
        传入根节点
        :param root: 如果为 TreeNode 为根节点， 如果为 None 为空书
        """
        if not (root is None or isinstance(root, TreeNode)):
            raise AttributeError('illegal root')
        self.root = root

前序遍历

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

循环版

    def preorder_traversal_while(self):
        """
        树的前序遍历
        :return: list of tree node value
        """
        res = []
        if not self.root:
            return res
        stack = [self.root]

        while len(stack):
            node = stack.pop()
            if not node.value:
                continue
            for sub_node in node.children[::-1]:
                stack.append(sub_node)
            res.append(node.value)

        return res

递归版

def preorder_traversal_recursion(self):
        """
        树的前序遍历
        :return: list of tree node value
        """
        res = []
        if not self.root:
            return res

        def _inner(root):
            inner_res = []
            if root.value:
                inner_res.append(root.value)
                for sub_node in root.children:
                    inner_res += _inner(sub_node)
            return inner_res
        return _inner(self.root)

后序遍历

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

循环版

def postorder_traversal_while(self):
        """
        树的后序遍历
        :return: list of tree node value
        """
        res = []

        if not self.root:
            return res

        stack = [self.root]

        while len(stack):
            node = stack.pop()
            if not node.value:
                continue
            for sub_node in node.children:
                stack.append(sub_node)
            res.append(node.value)

        return res[::-1]

递归版

   def postorder_traversal_recursion(self):
        """
        树的后序遍历
        :return: list of tree node value
        """
        res = []
        if not self.root:
            return res

        def _inner(root):
            inner_res = []
            if root.value:
                for sub_node in root.children:
                    inner_res += _inner(sub_node)
                inner_res.append(root.value)
            return inner_res

        return _inner(self.root)

层次遍历

按层遍历节点。

循环版

def layer_while(self):
        """
        树的层序遍历
        :return: list of tree node value
        """
        res = []
        if not self.root:
            return res

        queue = Queue()
        queue.put(self.root)

        while queue.qsize():
            node = queue.get()
            if not node.value:
                continue
            res.append(node.value)
            for sub_node in node.children:
                queue.put(sub_node)
        return res

求树的深度

计算树的最大深度。

 def depth_recursion(self):

        def _inner(root, depth=1):
            if not root.children:
                return depth
            return max([_inner(sub_node, depth+1) for sub_node in root.children])

        return _inner(self.root)

求树的结点数

计算树一共有多少节点。

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

求树的叶子数

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

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

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

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

def lowest_ancestor_node(self, node1, node2):
        stack = [self.root]
        stack1 = None
        stack2 = None

        while len(stack) and not (stack1 and stack2):
            node = stack.pop()

            if node is node1:
                stack1 = stack[:]
            if node is node2:
                stack2 = stack[:]
            if not node.value:
                continue
            for sub_node in node.children:
                stack.append(sub_node)

        res = self.root
        for i in range(len(stack1)):
            if stack1[i] == stack2[i]:
                res = stack1[i]
            else:
                return res.value

        return res.value

求任意两结点距离

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

def two_node_distence(self, node1, node2):
        stack = [self.root]
        stack1 = None
        stack2 = None

        while len(stack) and not (stack1 and stack2):
            node = stack.pop()

            if node is node1:
                stack1 = stack[:]
            if node is node2:
                stack2 = stack[:]
            if not node.value:
                continue
            for sub_node in node.children:
                stack.append(sub_node)

        res = self.root
        for i in range(len(stack1)):
            if stack1[i] == stack2[i]:
                res = stack1[i]
            else:
                return len(stack1) + len(stack2) - 2*i

        return len(stack1) + len(stack2) - 2*i

综述

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

更新

• 修复图片的 Bug