Python 实现列表与二叉树相互转换并打印二叉树封装类-详细注释+完美对齐

?

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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156

# Python 实现列表与二叉树相互转换并打印二叉树封装类-详细注释+完美对齐 from binarytree import build import random     # https://www.cnblogs.com/liw66/p/12133451.html   class MyBinaryTree:     lst = []       def __init__(self, lst=[]):         MyBinaryTree.lst = lst       class TreeNode:         def __init__(self, val=0, left=None, right=None):             self.val = val             self.left = left             self.right = right       def getTreeFromList(self, _list=None):         if _list is None: _list = MyBinaryTree.lst         if _list is None: return []           len_all = len(_list)  # 整个列表的长度         lay = 0  # 层数         loc = 0  # 结果列表位置         lay_list = []  # 层列表         node_list = []  # 节点列表         while len_all > 0:             len_lay = pow(2, lay)  # 层列表的长度，每层的长度为 2^lay，2^0、2^1、2^2、2^3、...             lay_list.append(_list[loc:(loc + len_lay)])  # 从 _list 切片得到该层的元素列表，添加到 lay_list 中             tail = len(lay_list) - 1  # lay_list 的尾节点索引             # 对 lay_list 的尾节点（每个节点元素都为列表）进行循环遍历，用列表中的每个元素构建TreeNode添加到node_list中             for j in range(len(lay_list[tail])):                 # 转换层列表为：[[5], [2, 9], [10, 1, 10, 5], [0, 9, 1]]                 node_list.append(MyBinaryTree.TreeNode(lay_list[tail][j]))  # 将列表索引 j 元素构建TreeNode添加到node_list中                   # 为上一层的父节点 TreeNode 元素添加 left、或right 值                 # if lay_list[tail][j] and lay > 0:  # 在 python 中0、空都为假，非零为真，所以这样将导致 lay_list[tail][j] 为 0 时没能填充                 if lay_list[tail][j] is not None and lay > 0:  # 必须改为这样，才能避免 lay_list[tail][j] 为 0 时没能填充                     if j % 2 == 0:                         node_list[pow(2, lay - 1) - 1 + j // 2].left = node_list[-1]                     else:                         node_list[pow(2, lay - 1) - 1 + j // 2].right = node_list[-1]               loc += len_lay             len_all -= len_lay             lay += 1           return node_list, lay_list       def getListFromTree(self, root=None):         node_list = []         if root is None:             node_list = self.getTreeFromList()[0]           root = node_list[0]           def treeRecursion(root, i, _list):             if root is None:                 return               len1 = len(_list)             if len1 <= i:                 for j in range(i - len1 + 1):                     _list.append(None)               _list[i] = root.val             treeRecursion(root.left, 2 * i, _list)             treeRecursion(root.right, 2 * i + 1, _list)           _list = []         treeRecursion(root, 1, _list)         while _list and _list[0] is None:             del (_list[0])         return _list       def printTree(self, node_list=[]):         if node_list is None:             node_list, _ = self.getTreeFromList()           def getNodeName(node, name="Node"):             return "None" if node is None or node.val is None else name + "{:0>2d}".format(node.val)           print("node:".ljust(7), "val".ljust(5), "left".ljust(7), "right")         for node in range(len(node_list)):             print(getNodeName(node_list[node]).ljust(6), end=": ")             print((getNodeName(node_list[node], "") + ", ").ljust(6),                   (getNodeName(node_list[node].left) + ", ").ljust(8),                   getNodeName(node_list[node].right), sep='')     def test_binarytree(list1):     mytree = MyBinaryTree(list1)       list2 = mytree.getListFromTree()     print("转换后列表为：{}".format(list2))     print("原来的列表为：{}".format(list1))     print("转换层列表为：{}".format(mytree.getTreeFromList()[1]))     print("转换前后的的列表是否相等：{}".format(list1 == list2))       print()     print("原来的列表转换为二叉树：{}".format(build(list1)))     print("转换的列表转换为二叉树：{}".format(build(list2)))       print("二叉树节点列表为（完美对齐）：")     mytree.printTree(mytree.getTreeFromList()[0])     list1 = [0, 1, 2, 3, 4, 5, 6, None, 7, None, 9, None, None, 10, ] # list1 = [i for i in range(100)] # list1 = [random.randint(0, 99) for i in range(20)] test_binarytree(list1)   # S:\PythonProject\pyTest01\venv\Scripts\python.exe S:/PythonProject/pyTest01/main.py # 转换后列表为：[0, 1, 2, 3, 4, 5, 6, None, 7, None, 9, None, None, 10] # 原来的列表为：[0, 1, 2, 3, 4, 5, 6, None, 7, None, 9, None, None, 10] # 转换层列表为：[[0], [1, 2], [3, 4, 5, 6], [None, 7, None, 9, None, None, 10]] # 转换前后的的列表是否相等：True # # 原来的列表转换为二叉树： #       ____0__ #      /       \ #   __1         2___ #  /   \       /    \ # 3     4     5     _6 #  \     \         / #   7     9       10 # # 转换的列表转换为二叉树： #       ____0__ #      /       \ #   __1         2___ #  /   \       /    \ # 3     4     5     _6 #  \     \         / #   7     9       10 # # 二叉树节点列表为（完美对齐）： # node:   val   left    right # Node00: 00,   Node01, Node02 # Node01: 01,   Node03, Node04 # Node02: 02,   Node05, Node06 # Node03: 03,   None,   Node07 # Node04: 04,   None,   Node09 # Node05: 05,   None,   None # Node06: 06,   Node10, None # None  : None, None,   None # Node07: 07,   None,   None # None  : None, None,   None # Node09: 09,   None,   None # None  : None, None,   None # None  : None, None,   None # Node10: 10,   None,   None # # 进程已结束,退出代码0