python实现二叉树的遍历

绝地灬酷狼 2022-11-13 09:26 161阅读 0赞

遍历二叉树就是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到二叉树节点的各种遍历序列。其实质就是对一个非线性结构进行线性操作，使在这个序列中，除了第一个和最后一个结点，每个结点都有一个直接前驱和直接后继。  
**先序遍历**  
如果二叉树为空，则什么也不做；  
否则：  
1.访问根节点  
2.先序遍历左子树  
3.先序遍历右子树

**中序遍历**  
如果二叉树为空，则什么也不做；  
否则：  
1.中序遍历左子树  
2.访问根节点  
3.中序遍历右子树  
**后序遍历**  
如果二叉树为空，则什么也不做；  
否则：  
1.后序遍历左子树  
2.后序遍历右子树  
3.访问根节点

**层次遍历**：  
要进行层次遍历需要借助一个队列。先将二叉树根结点入队，然后出队，访问该结点，如果它有左子树，则将左子树根结点入队；如果它有右子树，则将右子树根结点入队。然后出队，对出队结点访问，如此反复，直到队列为空。  
![在这里插入图片描述][20210326155147154.png]  
代码如下：

# 二叉树类
    class BTree(object):
        # 初始化
        def __init__(self, data=None, left=None, right=None):
            self.data = data    # 数据域
            self.left = left    # 左子树
            self.right = right  # 右子树
    
    
        # 前序遍历:中->左->右
        def preorder(self):
            if self.data:
                print(self.data, end=' ')
            if self.left:
                self.left.preorder()
            if self.right:
                self.right.preorder()
    
        # 中序遍历：左->中->右
        def inorder(self):
            if self.left :
                self.left.inorder()
            if self.data :
                print(self.data, end=' ')
            if self.right :
                self.right.inorder()
    
        # 后序遍历：左->右->中
        def postorder(self):
            if self.left :
                self.left.postorder()
            if self.right :
                self.right.postorder()
            if self.data :
                print(self.data, end=' ')
    
        # 层序遍历：
        def levelorder(self):
            # 返回某个节点的左孩子
            def LChild_Of_Node(node):
                return node.left if node.left  else None
            # 返回某个节点的右孩子
            def RChild_Of_Node(node):
                return node.right if node.right  else None
    
            # 层序遍历列表
            level_order = []
            # 传入的self为根结点，添加根节点中的数据到level_order,即：二叉树的根节点入队
            if self.data :
                print("self:",self.data)
                level_order.append([self])
    
            # 二叉树的高度
            height = self.height()
            if height >= 1:
                # 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据
                for _ in range(2, height + 1):
                    level = []  # 该层的节点
                    for node in level_order[-1]:
                        # 如果它有左子树，则将左子树节点入队
                        if LChild_Of_Node(node):
                            level.append(LChild_Of_Node(node))
                        # 如果它有右子树，则将右子树结点入队
                        if RChild_Of_Node(node):
                            level.append(RChild_Of_Node(node))
                    if level: # 如果该层非空，则添加该层
                        level_order.append(level)
    
                # 取出每层中的数据
                for i in range(0, height):  # 层数
                    for index in range(len(level_order[i])):
                        level_order[i][index] = level_order[i][index].data
            return level_order
    
    
        # 二叉树的高度
        def height(self):
            # 空的树高度为0, 只有root节点的树高度为1
            if self.data is None:
                return 0
            #左右子树都为空，则当前结点为叶子结点
            elif self.left is None and self.right is None:
                return 1
            elif self.left is None and self.right :
                return 1 + self.right.height()
            elif self.left  and self.right is None:
                return 1 + self.left.height()
            else:
                return 1 + max(self.left.height(), self.right.height())
    
        # 二叉树的叶子节点
        def leaves(self):
            if self.data is None:
                return None
            elif self.left is None and self.right is None:
                print(self.data, end=' ')
            elif self.left is None and self.right :
                self.right.leaves()
            elif self.right is None and self.left :
                self.left.leaves()
            else:
                self.left.leaves()
                self.right.leaves()
    
    
    if __name__ == '__main__':
    
        right_tree = BTree(6)
        right_tree.left = BTree(2)
        right_tree.right = BTree(4)
    
        left_tree = BTree(5)
        left_tree.left = BTree(1)
        left_tree.right = BTree(3)
    
        tree = BTree(11)
        tree.left = left_tree
        tree.right = right_tree
    
        left_tree = BTree(7)
        left_tree.left = BTree(3)
        left_tree.right = BTree(4)
    
        right_tree = tree # 增加新的变量
        tree = BTree(18)
        tree.left = left_tree
        tree.right = right_tree
    
        print('先序遍历为:')
        tree.preorder()
        print()
    
        print('中序遍历为:')
        tree.inorder()
        print()
    
        print('后序遍历为:')
        tree.postorder()
        print()
    
        print('层序遍历为:')
        level_order = tree.levelorder()
        print(level_order)
        print()
    
        height = tree.height()
        print('树的高度为%s.' % height)
    
        print('叶子节点为：')
        tree.leaves()
        print()
    # 先序遍历为:
    # 18 7 3 4 11 5 1 3 6 2 4
    # 中序遍历为:
    # 3 7 4 18 1 5 3 11 2 6 4
    # 后序遍历为:
    # 3 4 7 1 3 5 2 4 6 11 18
    # 层序遍历为:
    # self: 18
    # [[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]]
    #
    # 树的高度为4.
    # 叶子节点为：
    # 3 4 1 3 2 4

也可以换一种方式构造二叉树，利用层序遍历的原理逐层创建，代码如下：

# 二叉树类
    class BTree(object):
        # 初始化
        def __init__(self, data=None, left=None, right=None):
            self.data = data    # 数据域
            self.left = left    # 左子树
            self.right = right  # 右子树
    
    
        # 前序遍历:中->左->右
        def preorder(self):
            if self.data:
                print(self.data, end=' ')
            if self.left:
                self.left.preorder()
            if self.right:
                self.right.preorder()
    
        # 中序遍历：左->中->右
        def inorder(self):
            if self.left :
                self.left.inorder()
            if self.data :
                print(self.data, end=' ')
            if self.right :
                self.right.inorder()
    
        # 后序遍历：左->右->中
        def postorder(self):
            if self.left :
                self.left.postorder()
            if self.right :
                self.right.postorder()
            if self.data :
                print(self.data, end=' ')
    
        # 层序遍历：
        def levelorder(self):
            # 返回某个节点的左孩子
            def LChild_Of_Node(node):
                return node.left if node.left  else None
            # 返回某个节点的右孩子
            def RChild_Of_Node(node):
                return node.right if node.right  else None
    
            # 层序遍历列表
            level_order = []
            # 传入的self为根结点，添加根节点中的数据到level_order,即：二叉树的根节点入队
            if self.data :
                print("self:",self.data)
                level_order.append([self])
    
            # 二叉树的高度
            height = self.height()
            if height >= 1:
                # 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据
                for _ in range(2, height + 1):
                    level = []  # 该层的节点
                    for node in level_order[-1]:
                        # 如果它有左子树，则将左子树节点入队
                        if LChild_Of_Node(node):
                            level.append(LChild_Of_Node(node))
                        # 如果它有右子树，则将右子树结点入队
                        if RChild_Of_Node(node):
                            level.append(RChild_Of_Node(node))
                    if level: # 如果该层非空，则添加该层
                        level_order.append(level)
    
                # 取出每层中的数据
                for i in range(0, height):  # 层数
                    for index in range(len(level_order[i])):
                        level_order[i][index] = level_order[i][index].data
            return level_order
    
    
        # 二叉树的高度
        def height(self):
            # 空的树高度为0, 只有root节点的树高度为1
            if self.data is None:
                return 0
            #左右子树都为空，则当前结点为叶子结点
            elif self.left is None and self.right is None:
                return 1
            elif self.left is None and self.right :
                return 1 + self.right.height()
            elif self.left  and self.right is None:
                return 1 + self.left.height()
            else:
                return 1 + max(self.left.height(), self.right.height())
    
        # 二叉树的叶子节点
        def leaves(self):
            if self.data is None:
                return None
            elif self.left is None and self.right is None:
                print(self.data, end=' ')
            elif self.left is None and self.right :
                self.right.leaves()
            elif self.right is None and self.left :
                self.left.leaves()
            else:
                self.left.leaves()
                self.right.leaves()
    
    
    
    
    
    
    
    # 利用列表构造二叉树
    # 列表中至少有一个元素
    def create_BTree_By_List(array):
    
        i = 1
        # 将原数组拆成层次遍历的数组，每一项都储存这一层所有的节点的数据
        level_order = []
        sum = 1
        #二叉树每层元素数目为pow(2,n-1),索引为i-1:i*2-1
        while sum < len(array):
            level_order.append(array[i-1:2*i-1])
            i *= 2
            sum += i
        level_order.append(array[i-1:])#如果不是满二叉树，则剩余的放到最后一层
    
        # BTree_list: 这一层所有的节点组成的列表
        # forword_level: 上一层节点的数据组成的列表
        def Create_BTree_One_Step_Up(BTree_list, forword_level):
            new_BTree_list = []#最终得到一层有左右子树的结点
            i = 0
            for elem in forword_level:#这是父节点的集合，给结点分配左右子树
                root = BTree(elem)
                if 2*i < len(BTree_list):#左子树
                    root.left = BTree_list[2*i]
                if 2*i+1 < len(BTree_list):#右子树
                    root.right = BTree_list[2*i+1]
                new_BTree_list.append(root)
                i += 1
            return new_BTree_list
    
        # 只有一层：即只有一个节点
        if len(level_order) == 1:
            return BTree(level_order[0][0])
        else: # 二叉树的层数大于1
            # 创建最后一层的节点列表
            BTree_list = [BTree(elem) for elem in level_order[-1]]
            # 从下往上，逐层创建二叉树:BTree_list是每一层的节点集合
            for i in range(len(level_order)-2, -1, -1):
                BTree_list = Create_BTree_One_Step_Up(BTree_list, level_order[i])
            return BTree_list[0]
    
    
    
    if __name__ == '__main__':
    
        array = [chr(x) for x in range(65,91)]
        tree = create_BTree_By_List(array)
    
        print('先序遍历为:')
        tree.preorder()
        height = tree.height()
        print('树的高度为%s.'%height)
        print('层序遍历为:')
        level_order = tree.levelorder()
        print(level_order)
        print('叶子节点为：')
        tree.leaves()
    
    # 先序遍历为:
    # A B D H P Q I R S E J T U K V W C F L X Y M Z G N O 树的高度为5.
    # 层序遍历为:
    # self: A
    # [['A'], ['B', 'C'], ['D', 'E', 'F', 'G'], ['H', 'I', 'J', 'K', 'L', 'M', 'N', 'O'], ['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']]
    # 叶子节点为：
    # P Q R S T U V W X Y Z N O

[20210326155147154.png]: /images/20221022/ce45ce6b82ed4881b39ce0cab4654e4e.png