1，二叉树的基本概念

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。

二叉树是n个有限元素的
集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。

2，对于如何实现一棵二叉树，这里只提一种较为通用简单理解的方法，由于树的一对多的关系，我们希望定义结点类来存储，定义类似于链表结点，

class Node():
    def __init__(self,elem):
        self.elem = elem
        self.lchild = None
        self.rchild = None

3，定义好结点之后我们来实现一下树的基本功能，比如常见的增加元素，BFS和DFS，

（1）先实现增加元素

         对于二叉树元素的增加，在这里只实现尾增，也就是增加到叶子结点，其余插入结点式增加元素的方法类似于链表元素的增加与叶子结点的增加的方法结合，这里不再赘述，对于叶子结点，我们可以知到有两个位置可以选择，分别是该根节点的左右孩子结点，因此我们需要先定位到我们需要增加元素的位置，这里推荐使用列表及其操作函数:pop(),append()，pop()函数可以根据下标删除指定下标元素并返回该元素，append()函数可以实现在列表尾部增加元素，以此来模拟队列，

插入部分代码如下：

def add(self,val):
        node = Node(val) # 将传入的元素构造成一个新的结点
        if self.root is None: # 判断根元素是否为空，若为空，则将传入的第一个元素作为根节点
            self.root = node
            return 
        queue = [self.root] # 列表模拟队列
# 循环退出条件，队列为空，表示树的元素已经全部遍历完
        while queue:
            cur_node = queue.pop(0) # 队首出队
# 判断根节点的左右孩子是否为空：
# 如果是空，则表示找到了最底层的叶子结点，直接添加到该叶子结点，添加完之后注意直接return直接退出
# 如果非空，说明还没有到达最底层的叶子结点，这里直接将该结点追加到列表中，继续循环
            if cur_node.lchild is None:
                cur_node.lchild  = node
                return 
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return 
            else:
                queue.append(cur_node.rchild)

（2）实现对二叉树元素的遍历

这里分别使用BFS和DFS来操作，对于BFS，操作类似于上述的增加元素的方法，这里只是多了一行print而已，将不再赘述，直接上代码：

    def breadth_travel(self,root):
        if root is None: # 根结点为空，直接退出遍历
            return "ERROR!"
        queue = [root]
        while queue:
# 结点或结点左右孩子非空，直接入队，参与循环遍历
            cur_node = queue.pop(0)
            print(cur_node.elem,end= ' ')
# 输出根节点对应的元素后进入左右孩子结点判空操作，非空入队
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

对于DFS，有二叉树知识基础的同学应该都知道，其遍历方式分为三种，先序遍历，中序遍历，后序遍历，需要提一下的是，这几种遍历都是相对于根节点来说的，分不清楚的童鞋可以简单粗暴的认为就是遍历过程中描述的根节点的位置，由于遍历的时候需要频繁地转换根节点，这里将使用递归的方式来实现，由于详细的步骤过程上述都提到过了，这里也不在赘述，这里以先序遍历为例，代码如下：

    def pre_travel(self,root):
        print(root.elem,end = ' ')
        if root.lchild is not None:
            self.pre_travel(root.lchild)
        if root.rchild is not None:
            self.pre_travel(root.rchild)

 如果需要做到中序和后续，只需要调整以上几行代码的顺序即可，例如中序遍历只需要将print语句提到第一个if与第二个if中间即可。一下是完整的代码以及简单的实例：

class Node():
    def __init__(self,elem):
        self.elem = elem
        self.lchild = None
        self.rchild = None


class Bio_tree():
    def __init__(self):
        self.root = None

    
    def add(self,val):
        node = Node(val)
        if self.root is None:
            self.root = node
            return 
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild  = node
                return 
            else:
                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,root):
        if root is None:
            return "ERROR!"
        queue = [root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem,end= ' ')
            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 pre_travel(self,root):
        print(root.elem,end = ' ')
        if root.lchild is not None:
            self.pre_travel(root.lchild)
        if root.rchild is not None:
            self.pre_travel(root.rchild)


if __name__=="__main__":
    import os
    os.system("cls")
    tree = Bio_tree()
    for i in range(10):
        tree.add(i)
    tree.breadth_travel(tree.root)
    print()
    tree.pre_travel(tree.root)

以上就是二叉树简单的python实现，如有意见，欢迎评论区指正！