python实现二叉树和二叉树遍历可以拆分为以下几步:

一 构建结点Node:

我们知道二叉树的结点Node,可以有数据域,左孩子,和右孩子,三部分,那么我们就建结点类(如果基本概念不明白,可以先百度一下树和二叉树的一些定义,快速理解下)

class Node(object):
    def __init__(self,item):
        """
        param: self.elem 是结点的数据域
                self.lchild 是结点的左孩子
                self.rchild 是结点的右孩子
        """
        self.elem = item
        self.lchild = None
        self.rchild = None

二 利用上面的结点构建一个树类

class Tree(object):
    def __init__(self):
        self.root = None

好,完了

开什么玩笑,打你喔,空数也是一棵树嘛

树添加结点的方法

 def add(self,item):
        """
        param: item 是传进来来的数据,我们要实例化一个结点取接收他,但是他的位置要放在树梢,不能乱插入
                queue 我们创建一个队列来接收和弹出结点,这样我们找到结点需要接收的位置
        """
        node = Node(item)
        if self.root is None:
            """如果根结点是None,是一颗空数,我们就把node赋值给root,那么下面的while循环是不会受影响的,因为是队列[None]的bool值是True"""
            self.root = node
            return 
        queue = [self.root]
        while queue:
            """队列的弹出要加0,与栈相仿"""
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                """这里有空位,我们插入结点,如果能插入,就完事了"""
                cur_node.lchild = node
                return
            else:
                """cur_node的左孩子我们放进队列中,下次循环左子结点"""
                queue.append(cur_node.lchild)
            
            """同理对右边的操作一样,还是手敲下吧"""
            
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

广度遍历(又叫层次遍历,是一层一层从左到右的数下去)

def breadth_travel(self):
        """广度遍历与结点的添加非常相似,广度遍历不用插入结点了,在循环里面的条件和添加的相仿"""
        if self.root is None:
            return 
        queue = [self.root]
 
        while queue:
            cur_node = queue.pop(0)
            # 我们打印看看结点的遍历顺序对不对
            print(cur_node.elem)
            if cur_node.lchild is not None:
                # 扔进队列循环
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

深度遍历:前序 中序 后序遍历

这些最好画图去理解下,代码用递归的非常简单

  # 前序遍历
    def preorder(self,node):
        if node is None:
            return 
        
        # 下面三行代码顺序,深度先序遍历是先根结点,再左孩子,再右孩子
        print(node.elem)
        self.preorder(node.lchild)
        self.preorder(node.rchild)
        
        # 中序遍历
    def inorder(self,node):
        if node is None:
            return 
        
        # 下面三行代码顺序,
        self.preorder(node.lchild)
        print(node.elem)
        self.preorder(node.rchild)
    
            
        # 后序遍历
    def portorder(self,node):
        if node is None:
            return 
        
        # 下面三行代码顺序,
        self.preorder(node.lchild)
        self.preorder(node.rchild)
        print(node.elem)