Python初识二叉树续之实战binarytree_python_

第三方库 binarytree

其使用环境、安装方法及二叉树的相关知识，请见：《Python 初识二叉树，新手也秒懂！》

不能导入的请安装：pip install binarytree

安装好了就导入库：import binarytree

主要的函数方法如下：

>>> import binarytree as bt >>> >>> bt.__all__ ['Node', 'tree', 'bst', 'heap', 'build', 'build2', 'get_parent', '__version__'] >>> >>> bt.__version__ '6.3.0' >>>

目前最新版本 V6.3.0，挑其中几个来探究一下二叉树的世界吧：

二叉树节点函数 Node()

函数原型：Node(NodeValue, LeftChildNode=None, LeftChildNode=None)

三个参数：NodeValue节点数值，必须为实数，int或float

　　　　　LeftChildNode, LeftChildNode 左右子树节点

通过创建节点，生成一棵3层的满二叉树：

>>> from binarytree import Node >>> >>> bt = Node(1) >>> >>> bt.left = Node(2) >>> bt.right = Node(3) >>> >>> bt.left.left = Node(4) >>> bt.left.right = Node(5) >>> bt.right.left = Node(6) >>> bt.right.right = Node(7) >>> >>> bt.pprint() __1__ / \ 2 3 / \ / \ 4 5 6 7 >>>

如果要建很多层的满二叉树，用Node()逐个赋值有点麻烦。比如到第四层要给8个叶子赋值：

>>> bt.left.left.left = Node(8)
>>> bt.left.right.left = Node(10)
>>> bt.right.left.left = Node(12)
>>> bt.right.right.left = Node(14)
>>> bt.left.left.right = Node(9)
>>> bt.left.right.right = Node(11)
>>> bt.right.left.right = Node(13)
>>> bt.right.right.right = Node(15)

每多一层叶子数就翻一倍，为了方便我想到用exec()函数把字符串转成变量操作赋值的方法予以简化代码。自定义函数 createPerfectTree(intTreeLevels, listTreeData)，参数为需要指定的层数和节点赋值数据，分别是整数和列表类型；函数返回值为一个满二叉树。代码如下：

from binarytree import Node def createPerfectTree(intTreeLevels, listTreeData): if len(listTreeData)+1<2**intTreeLevels or intTreeLevels<1: return None t,tmp = ['root'],[] data = listTreeData[::-1] root = Node(data[-1]) data.pop() for j in range(intTreeLevels-1): for i in t: exec(i + f'.left=Node({data[-1]})') data.pop() exec(i + f'.right=Node({data[-1]})') data.pop() tmp.append(i + '.left') tmp.append(i + '.right') t=tmp[:] tmp=[] return root # 打印各节点值为整数序列的满二叉树（0~6层） for i in range(7): data = [*range(1,2**i)] print(createPerfectTree(i, data)) # 用指定列表的数据，创建满二叉树 data = [15,0,7,2,6,4,3,1,5,6,7,9,34,23,8] print(createPerfectTree(3, data)) print(createPerfectTree(4, data)) print(createPerfectTree(5, data)) # data长度不够返回:None # 赋值后列印 root = createPerfectTree(4, [*range(1,2**4)]) print(root)

运行结果：

None
 
1
 
 
  1
 / \
2   3
 
 
    __1__
   /     \
  2       3
 / \     / \
4   5   6   7
 
 
        ________1________
       /                 \
    __2___             ___3___
   /      \           /       \
  4       _5        _6        _7
 / \     /  \      /  \      /  \
8   9   10   11   12   13   14   15
 
 
                    ____________________1____________________
                   /                                         \
          ________2_________                         _________3_________
         /                  \                       /                   \
     ___4___             ____5___              ____6___              ____7___
    /       \           /        \            /        \            /        \
  _8        _9        _10        _11        _12        _13        _14        _15
 /  \      /  \      /   \      /   \      /   \      /   \      /   \      /   \
16   17   18   19   20    21   22    23   24    25   26    27   28    29   30    31
 
 
                                            ____________________________________________1____________________________________________
                                           /                                                                                         \
                      ____________________2_____________________                                                 _____________________3_____________________
                     /                                          \                                               /                                           \
           _________4_________                         __________5_________                          __________6_________                          __________7_________
          /                   \                       /                    \                        /                    \                        /                    \
     ____8___              ____9___              ____10___              ____11___              ____12___              ____13___              ____14___              ____15___
    /        \            /        \            /         \            /         \            /         \            /         \            /         \            /         \
  _16        _17        _18        _19        _20         _21        _22         _23        _24         _25        _26         _27        _28         _29        _30         _31
 /   \      /   \      /   \      /   \      /   \       /   \      /   \       /   \      /   \       /   \      /   \       /   \      /   \       /   \      /   \       /   \
32    33   34    35   36    37   38    39   40    41    42    43   44    45    46    47   48    49    50    51   52    53    54    55   56    57    58    59   60    61    62    63
 
 
    __15__
   /      \
  0        7
 / \      / \
2   6    4   3
 
 
        ______15_______
       /               \
    __0__            ___7___
   /     \          /       \
  2       6        4        _3
 / \     / \      / \      /  \
1   5   6   7    9   34   23   8
 
None
 
        ________1________
       /                 \
    __2___             ___3___
   /      \           /       \
  4       _5        _6        _7
 / \     /  \      /  \      /  \
8   9   10   11   12   13   14   15

嵌套创建节点，顺便判断对称性。得到一个结论：属性.is_symmetric判断的对称是指镜像对称，不是根节点的左右子树要完全相等，而是要镜面反向才返回 True。

>>> from binarytree import Node >>> a=Node(1,Node(2,Node(3),Node(4)),Node(2,Node(3),Node(4))) >>> a.pprint() __1__ / \ 2 2 / \ / \ 3 4 3 4 >>> b=Node(1,Node(2,Node(3),Node(4)),Node(2,Node(4),Node(3))) >>> b.pprint() __1__ / \ 2 2 / \ / \ 3 4 4 3 >>> a.is_symmetric False >>> b.is_symmetric True >>>

二叉树的方法与属性

1. 列印方法bt.pprint() 等同于print(bt)

# 以下所有举例皆用上面代码中的 root 满二叉树： >>> root Node(1) >>> root.pprint() ________1________ / \ __2___ ___3___ / \ / \ 4 _5 _6 _7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 # 等同于 print(root) >>> root.right.pprint() ___3___ / \ _6 _7 / \ / \ 12 13 14 15 >>> root.left.right.pprint() _5 / \ 10 11 >>> print(root.left.left) 4 / \ 8 9 >>>

2. 判断类属性，判断二叉树是否平衡、严格、对称、完全、完美，是否为最大(小)堆、搜索树等

对称是指根节点的左右子树呈镜像对称；严格是指除叶子外所有节点都有左右两个节点。

>>> root.is_balanced True >>> root.is_bst False >>> root.is_complete True >>> root.is_max_heap False >>> root.is_min_heap True >>> root.is_perfect True >>> root.is_strict True >>> root.is_symmetric False >>>

3. 数量数值类属性

>>> root.left Node(2) >>> root.right Node(3) >>> root.val 1 >>> root.value 1 >>> root.values [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] >>> root.values2 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] >>> root.left.value 2 >>> root.right.left.value 6 >>> root.max_node_value 15 >>> root.min_node_value 1 >>> root.max_leaf_depth 3 >>> root.min_leaf_depth 3 >>> root.levels [[Node(1)], [Node(2), Node(3)], [Node(4), Node(5), Node(6), Node(7)], [Node(8), Node(9), Node(10), Node(11), Node(12), Node(13), Node(14), Node(15)]] >>> len(root.levels) # == height + 1 4 >>> root.height 3 >>> root.leaves [Node(8), Node(9), Node(10), Node(11), Node(12), Node(13), Node(14), Node(15)] >>> len(root.leaves) 8 >>> root.leaf_count 8 >>>

注： val和value等价，values和values2差别在于如有多个连续空节点时后者只返回一个None 

4. 属性字典，打包了上面两大类属性中的一部分放在一个字典里

>>> root.properties {'height': 3, 'size': 15, 'is_max_heap': False, 'is_min_heap': True, 'is_perfect': True, 'is_strict': True, 'is_complete': True, 'leaf_count': 8, 'min_node_value': 1, 'max_node_value': 15, 'min_leaf_depth': 3, 'max_leaf_depth': 3, 'is_balanced': True, 'is_bst': False, 'is_symmetric': False }

5. 遍历类

>>> root.preorder [Node(1), Node(2), Node(4), Node(8), Node(9), Node(5), Node(10), Node(11), Node(3), Node(6), Node(12), Node(13), Node(7), Node(14), Node(15)] >>> root.inorder [Node(8), Node(4), Node(9), Node(2), Node(10), Node(5), Node(11), Node(1), Node(12), Node(6), Node(13), Node(3), Node(14), Node(7), Node(15)] >>> root.postorder [Node(8), Node(9), Node(4), Node(10), Node(11), Node(5), Node(2), Node(12), Node(13), Node(6), Node(14), Node(15), Node(7), Node(3), Node(1)] >>> root.levelorder [Node(1), Node(2), Node(3), Node(4), Node(5), Node(6), Node(7), Node(8), Node(9), Node(10), Node(11), Node(12), Node(13), Node(14)
                
提示：
                    本文由神整理自网络，如有侵权请联系本站删除！
                    

                    本站声明： 

                    1、本站所有资源均来源于互联网，不保证100%完整、不提供任何技术支持； 

                    2、本站所发布的文章以及附件仅限用于学习和研究目的;不得将用于商业或者非法用途；否则由此产生的法律后果，本站概不负责！
                
                

                

                                            
上一篇：python切割图片的实现示例_python_
                                                                
下一篇：Python自动化办公之定时发送邮件的实现_python_