# 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