1/Что такое древовидная структура

树型结构是一种重要的`非线性`数据结构，其中以树和二叉树最为常用，是以分支关系定义的层次结构。
树型结构在客观世界中广泛存在：
   <1>如人类社会的族谱和各种社会组织机构，以及公司里的组织架构。
    在计算机领域中也有广泛应用，如在编译程序中，可用树来表示源程序的语法结构；
    在数据库系统中，树型结构也是信息的重要组织形式之一；
    在机器学习中，决策树，随机森林，GBDT等是常见的树模型。

在树型结构中，有3种节点，分别是：
   根节点root node，
   中间节点decision node，
   叶子节点 terminor node。
   
在一棵树中，只有一个根节点，没有左右孩子节点的就是叶子节点。
一棵树有多少层，及这棵树的深度(或者高度)是多少。
根据树的高度，我们可以知道这棵树最多有多少节点。及2的k次方-1个节点

2/ Что такое бинарное дерево

二叉树（Binary Tree）是树型结构的一种
之所以称为二叉，而不是三叉，是因为每个节点的出度最大是2，当然也可以是1。

它的特点是每个节点最多有两棵子树（即二叉树中不存在度大于2的节点），，最多分2个叉
且二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。

 Согласно определению бинарного дерева, оно обладает следующими важными свойствами, как показано ниже:

3/ Что такое полное бинарное дерево

满二叉树是完全填满的二叉树，没一层都是填满的，最后一层也是填满的。
满二叉树，及除了叶子节点，其他的每个节点都有2个孩子节点。
对于满二叉树，你再也添加不进去一个新的节点了。

我们如何判断一棵树是满二叉树呢？
    如果一棵树的深度是k，且有2的k次方-1个节点，则为满二叉树。

4/ Что такое полное бинарное дерево

完全二叉树，是除最后一层以外都是填满的，最后一层外也必须从左到右依次填入。
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

5/ Обход бинарного дерева

所谓二叉树的遍历，指的是如何按某种搜索路径巡防树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。
对于二叉树，常见的遍历方法有：先序遍历，中序遍历，后序遍历，层序遍历。
这些遍历方法一般使用递归算法实现。

先序遍历的操作定义为：
    若二叉树为空，为空操作；
    否则（1）访问根节点；
       （2）遍历左子树；
       （3）遍历右子树。

中序遍历的操作定义为：
    若二叉树为空，为空操作；
    否则（1）遍历左子树；
        （2）访问根结点；
        （3）遍历右子树。
    
后序遍历的操作定义为：
    若二叉树为空，为空操作；
    否则（1）遍历左子树；
       （2）遍历右子树；
       （3）访问根结点。

层序遍历的操作定义为：
    若二叉树为空，为空操作；
    否则从上到下、从左到右按层次进行访问。

比如下图：
    先序遍历为:
       18 7 3 4 11 5 1 3 6 2 4 
    中序遍历为:
       3 7 4 18 1 5 3 11 2 6 4 
    后序遍历为:
       3 4 7 1 3 5 2 4 6 11 18 
    层序遍历为:
       [[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]]

6/ Реализация кода Python для двоичного дерева

from graphviz import Digraph
import uuid
from random import sample

# 二叉树类
class BTree(object):

    # 初始化
    # 构建二叉树
    def __init__(self, data=None, left=None, right=None):
        #对于一个节点来说，由3部分构成，及数据，左孩子，右孩子
        self.data = data    # 数据域
        self.left = left    # 左子树
        self.right = right  # 右子树
        self.dot = Digraph(comment='Binary Tree')

    # 前序遍历
    def preorder(self):
    
        if self.data is not None:
            print(self.data, end=' ')
        if self.left is not None:
            self.left.preorder()
        if self.right is not None:
            self.right.preorder()

    # 中序遍历
    def inorder(self):
    
        if self.left is not None:
            self.left.inorder()
        if self.data is not None:
            print(self.data, end=' ')
        if self.right is not None:
            self.right.inorder()

    # 后序遍历
    def postorder(self):
    
        if self.left is not None:
            self.left.postorder()
        if self.right is not None:
            self.right.postorder()
        if self.data is not None:
            print(self.data, end=' ')

    # 层序遍历
    def levelorder(self):
    
        # 返回某个节点的左孩子
        def LChild_Of_Node(node):
            return node.left if node.left is not None else None
        # 返回某个节点的右孩子
        def RChild_Of_Node(node):
            return node.right if node.right is not None else None

        # 层序遍历列表
        level_order = []
        # 是否添加根节点中的数据
        if self.data is not None:
            level_order.append([self])

        # 二叉树的高度
        height = self.height()
        if height >= 1:
            # 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据
            for _ in range(2, height + 1):
                level = []  # 该层的节点
                for node in level_order[-1]:
                    # 如果左孩子非空，则添加左孩子
                    if LChild_Of_Node(node):
                        level.append(LChild_Of_Node(node))
                    # 如果右孩子非空，则添加右孩子
                    if RChild_Of_Node(node):
                        level.append(RChild_Of_Node(node))
                # 如果该层非空，则添加该层
                if level:
                    level_order.append(level)

            # 取出每层中的数据
            for i in range(0, height):  # 层数
                for index in range(len(level_order[i])):
                    level_order[i][index] = level_order[i][index].data

        return level_order


    # 二叉树的高度
    def height(self):
        # 空的树高度为0, 
        if self.data is None:
            return 0
            
        # 只有root节点的树高度为1
        elif self.left is None and self.right is None:
            return 1
        
        # 只要有一个不是None，则进行递归
        elif self.left is None and self.right is not None:
            return 1 + self.right.height()
            
        elif self.left is not None and self.right is None:
            return 1 + self.left.height()
        
        # 最后返回一个最大的值，作为树的深度
        else:
            return 1 + max(self.left.height(), self.right.height())


    # 二叉树的叶子节点
    def leaves(self):
        # 如果连数据域都没有，则直接返回None
        if self.data is None:
            return None
        
        # 既没有左孩子，也没有右孩子，这样的节点才是叶子节点，打印出来
        elif self.left is None and self.right is None:
            print(self.data, end=' ')
        
        # 如果有右孩子，则递归
        elif self.left is None and self.right is not None:
            self.right.leaves()
        
        # 如果有左孩子，则递归
        elif self.right is None and self.left is not None:
            self.left.leaves()
        
        # 如果左右孩子都有，则2边都递归
        else:
            self.left.leaves()
            self.right.leaves()

在上述代码中，创建了二叉树类BTree，实现了如下方法：
1. 初始化方法：该树存放的数据为data,左子树，右子树为left和right，默认均为None;
1. preorder()方法：递归实现二叉树的先序遍历；
1. inorder()方法：递归实现二叉树的中序遍历；
1. postorder()方法：递归实现二叉树的后序遍历；
1. levelorder()方法：递归实现二叉树的层序遍历；
1. height()方法：计算二叉树的高度；
1. leaves()方法：计算二叉树的叶子结点；
1. print_tree()方法：利用Graphviz实现二叉树的可视化，需要设置的参数为save_path和label，save_path为文件保存路径，默认的保存路径为当前路径下的Binary_Tree.gv,可以用户自己设置；label为是否在Graphviz文件中添加二叉树的左右子树的标签，用于分清哪棵是左子树，哪棵是右子树，可以用用户自己设置。