python 实现二叉树(有序)的遍历

心已赠人 2022-10-02 01:51 140阅读 0赞

### 前序遍历 ###

前序遍历主要是顺序是  根 -----> 左子树 -----> 右子树

### 中序遍历 ###

中序遍历的主要顺序是 左子树 -----> 根 -----> 右子树

### 后序遍历 ###

后序遍历的主要顺序是 左子树 -----> 右子树 -----> 根

class Node(object):
    
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None
    
    
    class Tree(object):
        """
        python实现有序二叉树
        """
        def __init__(self):
            self.root = None
    
        def add(self, data):
            """
            添加元素,需要考虑添加在哪里
            :return:
            """
            queue = []
            node = Node(data)
            if not self.root:
                self.root = node
                return
            else:
                queue.append(self.root)
                while queue:
                    cur = queue.pop(0)
                    # 往右子树添加
                    if data > cur.data:
                        if cur.right is None:
                            cur.right = node
                            return
                        else:
                            queue.append(cur.right)
                    # 往左子树添加
                    else:
                        if cur.left is None:
                            cur.left = node
                            return
                        else:
                            queue.append(cur.left)
    
        def breadthTraverse(self):
            """
            广度遍历
            :return:
            """
            queue = list()
            if self.root is None:
                return
            else:
                queue.append(self.root)
                while queue:
                    cur = queue.pop(0)
                    print(cur.data, end=" ")
                    if cur.left is not None:
                        queue.append(cur.left)
                    if cur.right is not None:
                        queue.append(cur.right)
    
        def preorderTraverse(self, node):
            """
            前序遍历
            根 ----> 左 ----->右
            :return:
            """
            if node is None:
                return
            else:
                print(node.data, end=" ")
                self.preorderTraverse(node.left)
                self.preorderTraverse(node.right)
    
        def inorder(self, root):
            """
            中序遍历
            左 ----> 根 ---->右
            :return:
            """
            if root is None:
                return
            else:
                self.inorder(root.left)
                print(root.data, end=" ")
                self.inorder(root.right)
    
        def postorder(self, root):
            """
            后序遍历
            左 ----> 右 ----> 根
            :param root:
            :return:
            """
            if root is None:
                return
            else:
                self.postorder(root.left)
                self.postorder(root.right)
                print(root.data, end=" ")
    
    
    if __name__ == "__main__":
        tree = Tree()
        tree.add(50)
        tree.add(45)
        tree.add(40)
        tree.add(48)
        tree.add(51)
        tree.add(61)
        tree.add(71)
        print("广度遍历")
        tree.breadthTraverse()
        print("")
        print("前序遍历")
        tree.preorderTraverse(tree.root)
        print("")
        print("中序遍历")
        tree.inorder(tree.root)
        print("")
        print("后序遍历")
        tree.postorder(tree.root)

### 输出结果 ###

广度遍历  
50 45 51 40 48 61 71  
前序遍历  
50 45 40 48 51 61 71  
中序遍历  
40 45 48 50 51 61 71  
后序遍历  
40 48 45 71 61 51 50