用对象的思想创建二叉树并实现四种遍历-python版

直接上代码:

#coding:utf-8

class Node(object):
    """二叉树节点"""

    def __init__(self, item):
        super(Node, self).__init__()
        self.item = item
        self.lchild = None
        self.rchild = None


class Tree(object):
    """二叉树类"""

    def __init__(self):
        super(Tree, self).__init__()
        self.root = None

    def add(self, item):
        """添加节点"""
        node = Node(item)
        # 判断当前树是否为空
        if self.root is None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            # 采用队列存放, 先将根节点放入队列中,取出,看是否有左子树和右子树,有就放入并且循环回来看子树的子树,没有则添加
            while queue:
                temp = queue.pop(0)
                # 看做节点是否为空
                if temp.lchild is None:
                    temp.lchild = node
                    break
                # 看右节点是否为空
                elif temp.rchild is None:
                    temp.rchild = node
                    break
                # 都不为空,将左节点和右节点放入队列
                else:
                    queue.append(temp.lchild)
                    queue.append(temp.rchild)

    def wide_travel(self):
        """广度优先遍历(广序遍历):从上到下,从左到右.利用队列"""
        if self.root is None:
            return
        else:
            queue = []
            queue.append(self.root)
            while queue:
                temp = queue.pop(0)
                print(temp.item, end=" ")
                # 如果有左孩子则放入队列
                if temp.lchild is not None:
                    queue.append(temp.lchild)
                # 如果有右孩子则放入队列
                if temp.rchild is not None:
                    queue.append(temp.rchild)
            print()

    # 深度遍历采用了递归
    def preorder(self, node):
        """深度遍历-先序遍历(根节点-左子树-右子树)"""
        if node is None:
            return
        print(node.item, end=" ")
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self, node):
        """深度遍历-中序遍历(左子树-根节点-右子树)"""
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.item, end=" ")
        self.inorder(node.rchild)

    def posorder(self, node):
        """深度遍历-后序遍历(左子树-右子树-根节点)"""
        if node is None:
            return
        self.posorder(node.lchild)
        self.posorder(node.rchild)
        print(node.item, end=" ")


if __name__ == '__main__':
    tree = Tree()
    for char in "ABCDEFG":
        tree.add(char)
    print("先序遍历:")
    tree.preorder(tree.root)
    print("\n中序遍历:")
    tree.inorder(tree.root)
    print("\n后序遍历:")
    tree.posorder(tree.root)
    print("\n广度遍历:")
    tree.wide_travel()

欢迎一起分享和交流python---->q群:556993881