【数据结构】Python 递归创建二叉树以及遍历二叉树

一，二叉树二，二叉树的创建和遍历三，Binarytree库的使用

杨jun坚

3480人浏览 · 2021-07-05 21:43:08

杨jun坚 · 2021-07-05 21:43:08 发布

一，二叉树

1，定义

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。
在这里插入图片描述

2，二叉树特点

由二叉树定义以及图示分析得出二叉树有以下特点：
1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
2）左子树和右子树是有顺序的，次序不能任意颠倒，图中两棵树是不同的。
在这里插入图片描述
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

3，二叉树性质

1）在二叉树的第i层上最多有2^(i-1)个节点。（i>=1）
2）二叉树中如果深度为k,那么最多有2^k-1个节点。(k>=1）
3）n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
4）在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。
5）若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：
a.若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
b.若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；
c.若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。

4，特殊二叉树

斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
在这里插入图片描述
满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
满二叉树的特点有：
1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2）非叶子结点的度一定是2。
3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
在这里插入图片描述
完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
特点：
1）叶子结点只能出现在最下层和次下层。
2）最下层的叶子结点集中在树的左部。
3）倒数第二层若存在叶子结点，一定在右部连续位置。
4）如果结点度为1，则该结点只有左孩子，即没有右子树。
5）满二叉树一定是完全二叉树，但反过来不一定成立。

在这里插入图片描述

二，二叉树的创建和遍历

实现下图的二叉树
在这里插入图片描述

# 递归实现二叉树


class BiTNode(object):
    def __init__(self, val=None, l=None, r=None):
        self.value = val
        self.leftChild = l
        self.rightChild = r


class BinaryTree(object):
    def __init__(self):
        self.root = None
        self.num = 0

    def create_bitree(self):
        """以前序遍历的方式递归创建二叉树"""
        c = input()
        if '#' == c:
            return
        else:
            node = BiTNode(c)
            if self.num == 0:
                self.root = node
            self.num += 1
            node.leftChild = self.create_bitree()
            node.rightChild = self.create_bitree()
        return node

    def pre_order(self, roots):
        """前序遍历结果"""
        if roots:
            print(roots.value, end=' ')
            self.pre_order(roots.leftChild)
            self.pre_order(roots.rightChild)

    def mid_order(self, roots):
        """中序遍历结果"""
        if roots:
            self.mid_order(roots.leftChild)
            print(roots.value, end=' ')
            self.mid_order(roots.rightChild)

    def pos_order(self, roots):
        """后序遍历结果"""
        if roots:
            self.pos_order(roots.leftChild)
            self.pos_order(roots.rightChild)
            print(roots.value, end=' ')

    def layer_order(self, roots):
        """使用FIFO队列实现层序遍历
           逐层从左到右插入队列，再从头部弹出
        """
        node_queue = list()
        value_list = list()
        node_queue.append(roots)
        while node_queue:
            tree_node = node_queue.pop(0)
            value_list.append(tree_node.value)
            if tree_node.leftChild:
                node_queue.append(tree_node.leftChild)
            if tree_node.rightChild:
                node_queue.append(tree_node.rightChild)
        return ' '.join(value_list)



if __name__ == '__main__':
    BinaryTree = BinaryTree()
    print('以前序遍历的方式输入节点')
    BinaryTree.create_bitree()
    print('前序遍历')
    BinaryTree.pre_order(BinaryTree.root)
    print('')
    print('中序遍历')
    BinaryTree.mid_order(BinaryTree.root)
    print('')
    print('后序遍历')
    BinaryTree.pos_order(BinaryTree.root)
    print('')
    print('层序遍历')
    print(BinaryTree.layer_order(BinaryTree.root))
    print('')

以前序遍历的方式输入节点
A
B
D
G
#
#
H
#
#
E
#
I
#
#
C
F
J
#
#
#
#
前序遍历
A B D G H E I C F J 
中序遍历
G D H B E I A J F C 
后序遍历
G H D I E B J F C A 
层序遍历
A B C D E F G H I J

三，Binarytree库的使用

也许你会觉得自己去构建二叉树太费脑筋了，于是，你又想起某位伟人，曾经说过，人生苦短，我用Python，没错，对于二叉树，Python也有第三方库可以使用。就是下面说到的Binarytree。
简介
Binarytree是一个Python库，它通过一个简单的API生成二叉树，可以进行检查和操作。它让您跳过繁琐的测试数据设置，直接练习算法。还支持堆和BST（二叉搜索树）。

声明
Binarytree已经更新至4.0版。
请访问发布页（链接：https://github.com/joowani/binarytree/releases）查看最近一次更新详情。

运行环境
Python 2.7, 3.4, 3.5 或 3.6。

安装
从PyPi安装稳定版：
先装 dataclasses ，再装 binarytree
~$ pip install dataclasses -i https://pypi.douban.com/simple
~$ pip install binarytree -i https://pypi.douban.com/simple

举个例子

    from binarytree import *

    tree0 = tree()
    print('深度为3，普通二叉树tree0:', tree0)
    tree1 = tree(height=2, is_perfect=True)
    print('深度为2，满二叉树tree1:', tree1)
    tree2 = tree(height=2, is_perfect=False)
    print('深度为2，普通二叉树tree2:', tree2)

不得不佩服，连输出格式都格式化了

深度为3，普通二叉树tree0: 
  ___6____
 /        \
7          13__
 \        /    \
  10     3      14
        /      /  \
       8      5    0

深度为2，满二叉树tree1: 
    __6__
   /     \
  0       1
 / \     / \
2   3   4   5

深度为2，普通二叉树tree2: 
    __5
   /   \
  0     6
 / \
1   4

具体的使用方法请参考官方API文档
https://binarytree.readthedocs.io/en/latest/specs.html#class-binarytree-node
或者参考以下博文：
https://blog.csdn.net/qq7835144/article/details/87951881
https://blog.csdn.net/weixin_43790276/article/details/107993526

最后，如果大家知道如何以中序，后序遍历递归创建二叉树，请评论贴出代码或者私信，谢谢大家