Python代码实现了树的深度优先遍历和广度优先（递归和非递归），

树是数据结构中非常重要的一部分。树的用途很多，树的种类也很多。今天我们将把它创建为第一棵公共树。

首先，树的形状类似于这样：

顶点称为树的根节点。一棵树只能有一个根节点，该节点下可以有多个子节点。这里我们不要求节点的数量，没有子节点的节点称为叶子节点。

好了，关于树的基本概念就介绍到这里了。说一千遍不如做一次。接下来，让我们边做边学。我们来创建一棵树：

Tree

# 定义一个普通的树类
class Tree:
    def __init__(self, data):
        self.data = data
        self.children = []

    def get(self):
        return self.data
    
    def set(self):
        return self.data

    def addChild(self, child):
        self.children.append(child)

    def getChildren(self):
        return self.children

这就是我们定义的树类，并在树中添加了三个方法，分别是获取节点数据、设置节点数据、添加子节点和获取子节点。

这里的树类实际上是一个节点类。许多这样的节点可以形成一棵树，我们用根节点来表示这棵树。

接下来，我们实例化树：

# 初始化一个树
tree = Tree(0)
# 添加三个子节点
tree.addChild(Tree(1))
tree.addChild(Tree(2))
tree.addChild(Tree(3))
children = tree.getChildren()
# 每个子节点添加两个子节点
children[0].addChild(Tree(4))
children[0].addChild(Tree(5))
children[1].addChild(Tree(6))
children[1].addChild(Tree(7))
children[2].addChild(Tree(8))
children[2].addChild(Tree(9))

我们创建的树大概是这样的：

OK，我们的树已经创建好了，我们先进行拆分 使用递归和非递归遍历方法：

广度遍历

广度遍历是指从上到下、一层一层、从左到右遍历树。

以非递归方式进行宽度优先转换时，需要用到前面介绍的队列类型，因此我们定义一个队列类：

# 用以实现广度优先遍历
class Queue():
    def __init__(self):
        self.__list = list()

    def isEmpty(self):
        return self.__list == []

    def push(self, data):
        self.__list.append(data)
    
    def pop(self):
        if self.isEmpty():
            return False
        return self.__list.pop(0)

使用队列实现宽度优先转换

我们使用队列只是当节点出队时，让该节点的子节点加入队列。

# 广度优先遍历
def breadthFirst(tree):
    queue = Queue()
    queue.push(tree)
    result = []
    while not queue.isEmpty():
        node = queue.pop()
        result.append(node.data)
        for c in node.getChildren():
            queue.push(c)
    return result

我们称之为：

print(breadthFirst(tree))

输出：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

递归实现所有面包

print(breadthFirstByRecursion(tree))

输出： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

深度优先遍历-优先，即深度，深度向下，从左到右，遍历子节点第一个节点，然后是该节点的兄弟节点。

如果我们想以非递归的方式实现深度遍历，就需要用到前面介绍的栈结构，所以现在我们来定义一个栈类：

# 用以实现深度优先遍历
class Stack():
    def __init__(self):
        self.__list = list()

    def isEmpty(self):
        return self.__list == []

    def push(self, data):
        self.__list.append(data)
    
    def pop(self):
        if self.isEmpty():
            return False
        return self.__list.pop()

使用栈来实现深度遍历

来实现深度遍历，我们只需在节点出栈时将节点的子节点从左向右压入栈即可。

# 深度优先遍历
def depthFirst(tree):
    stack = Stack()
    stack.push(tree)
    result = []
    while not stack.isEmpty():
        node = stack.pop()
        result.append(node.data)
        children = node.getChildren()
        children = reversed(children)
        for c in children:
            stack.push(c)
    return result

称之为：

# 深度优先遍历
print(depthFirst(tree))

输出：[0, 1, 4, 5, 2, 6, 7, 3, 8, 9]

st。递归实现的深度

print(depthFirstByRecursion(tree))

输出：[0, 1, 4, 5, 2, 6, 7, 3, 8, 9]

好了，今天我们的递归实现树就介绍到这里了，你有更好的方式？