二叉树的遍历python实现

# 二叉树是链表的扩展

#定义节点
class Node(object):
    def __init__(self,elem):
        self.value = elem
        self.lchild = None
        self.rchild = None

class Tree_1(object):
    def __init__(self):
        self.root = None
    #这样建立的树不需要传任何东西,就是一颗空树
    #如下方式要初始化一个根节点
    # def __init__(self,root=None):
    #     self.root = root
    #添加节点的方式是层次遍历(广度优先)
    def add(self,item):
        node = Node(item)
        if self.root == None:
            self.root = node
            return
        queue = [self.root]


        while queue:
            process_node= queue.pop(0)
            if process_node.lchild == None:
                process_node.lchild = node
                return
            else:
                queue.append(process_node.lchild)

            if process_node.rchild == None:
                process_node.rchild = node
                return
            else:
                queue.append(process_node.rchild)

#树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问,即依次对树中每个结点访问一次且仅访问一次,
# 我们把这种对所有节点的访问称为遍历(traversal)。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,
# 深度优先(纵向)一般用递归,广度优先一般用队列(横向)。一般情况下能用递归实现的算法大部分也能用堆栈来实现。
#对于一颗二叉树,深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。 那么深度
# 遍历有重要的三种方法。这三种方式常被用于访问树的节点,它们之间的不同在于访问每个节点的次序不同。这三种遍历分别
# 叫做先序遍历(preorder),中序遍历(inorder)和后序遍历(postorder)。
# 先序,中序,后序都是根据根节点来说的 先序把根节点->左->右 中序 左根右 后序 左右根

# 1 层次遍历 从树的root开始,从上到下从从左到右遍历整个树的节点 与添加元素的过程类似
    def breadth_travel(self):
        #用队列实现层次遍历
        if self.root == None:
            return
        queue = [self.root]
        #直到弹没
        while queue:
            cur_point = queue.pop(0)
            print(cur_point.value,end=' ')
            #这句是遍历的关键
            if  cur_point.lchild is not None:
                queue.append(cur_point.lchild)
            if  cur_point.rchild is not None:
                queue.append(cur_point.rchild)



# 1 先序遍历  在先序遍历中,我们先访问根节点,然后递归使用先序遍历访问左子树,再递归使用先序遍历访问右子树 根节点->左子树->右子树
    def pretravel(self, node):
        if node==None:
            return
        print(node.value,end=' ')
        self.pretravel(node.lchild)
        self.pretravel(node.rchild)
# 2 中序遍历
    def inordertravel(self,node):
        if node==None:
            return
        self.inordertravel(node.lchild)
        print(node.value)
        self.inordertravel(node.rchild)

# 3 后序遍历
    def posttravel(self,node):
        if node==None:
            return
        self.posttravel(node.lchild)
        self.posttravel(node.rchild)
        print(node.value, end=' ')





if __name__ == '__main__':
    tree = Tree_1()
    for i in range(10):
        tree.add(i)
    tree.breadth_travel()
    print(' ')
    tree.pretravel(tree.root)
    print(' ')
    tree.inordertravel(tree.root)
    print(' ')
    tree.posttravel(tree.root)

 

    原文作者:桔梗的眼泪
    原文地址: https://blog.csdn.net/weixin_40274123/article/details/90697553
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞