python实现二叉树深度遍历

骑猪看日落 2022-05-14 07:07 123阅读 0赞

## 1、什么是深度优先遍历 ##

其实深度优先遍历你可以把它看成是前序遍历，比如对于如下二叉树：

![70][]

其深度遍历的结果是：1,2,4,8,9,5,3,6,7

## 2、解题思路 ##

一、采用递归的方式进行遍历。

二、利用**栈**，先将根入栈，再将根出栈，并将根的右子树，左子树存入栈，按照**栈**的**先进后出**规则来实现深度优先遍历。

## 3、编程实现 ##

class Node():
        # 节点类
        def __init__(self, data=-1):
            self.data = data
            self.left = None
            self.right = None
    
    
    class Tree():
        # 树类
        def __init__(self):
            self.root = Node()
    
        def add(self, data):
            # 为树加入节点
            node = Node(data)
            if self.root.data == -1:  # 如果树为空，就对根节点赋值
                self.root = node
            else:
                myQueue = []
                treeNode = self.root
                myQueue.append(treeNode)
                while myQueue:  # 对已有的节点进行层次遍历
                    treeNode = myQueue.pop(0)
                    if not treeNode.left:
                        treeNode.left = node
                        return
                    elif not treeNode.right:
                        treeNode.right = node
                        return
                    else:
                        myQueue.append(treeNode.left)
                        myQueue.append(treeNode.right)
        
        def DFS(self,root):     #递归实现深度优先遍历
            if root == None:
                return
            print(root.data)
            self.DFS(root.left)
            self.DFS(root.right)
        def DFS_STACK(self,root):      #基于栈数据结构实现的深度遍历
            if root == None:
                return
            stack = []
            stack.append(root)
            while stack:
                now_node = stack.pop()
                print(now_node.data)
                if now_node.right != None:
                    stack.append(now_node.right)
                if now_node.left != None:
                    stack.append(now_node.left)
    
    if __name__ == '__main__':
        # 主函数
        datas = [1,2, 3, 4, 5, 6, 7, 8, 9]
        tree = Tree()  # 新建一个树对象
        for data in datas:
            tree.add(data)  # 逐个加入树的节点
    
        print('递归实现前序遍历：')
        tree.DFS_STACK(tree.root)

## 4、输出结果 ##

![70 1][]

[70]: /images/20220514/0769c78412ac4ce899c09c64f0c6e1a0.png
[70 1]: /images/20220514/3122a19ba082441c8c32b2b317ba4ef4.png