python实现把一个有序整数数组放到二叉树中

微软面试题
分析与解答:
如果要把一个有序的整数数组放到二叉树中，那么所构造出来的二叉树必定也是一棵有
序的二叉树。鉴于此，实现思路为 : 取数组的中间元素作为根结点 ， 将数组分成左右两部分， 对数组的两部分用递归的方法分别构建左右子树。如下图所示。

如上图所示，首先取数组的中间结点 6 作为 二叉树的根结点，把数组分成左右两部分， 然后对于数组的左右两部分子数组分别运用同样的方法进行 二 叉树的构建，例如，对于左半 部分子数组，取中间结点 3 作为树的根结点，再把子数组分成左右两部分。依此类推，就可以完成二叉树的构建，实现代码如下 :

class BiTNode:
    def __init__(self):
        self.data=None
        self.lchild=None
        self.rchild=None
def arraytotree(arr,start,end):
    root=None
    if end>=start:
        root=BiTNode()
        mid=(start+end+1)//2
        root.data=arr[mid]
        root.lchild=arraytotree(arr,start,mid-1)
        root.rchild=arraytotree(arr,mid+1,end)
    else:
        root=None
    return root
def printTreeMidOrder(root):
    if root==None:
        return 
    if root.lchild!=None:
        printTreeMidOrder(root.lchild)
    print(root.data)
    if root.rchild!=None:
        printTreeMidOrder(root.rchild)

测试：

if __name__=='__main__':
    arr=[1,2,3,4,5,6,7,8,9,10]
    print('数组')
    i=0
    while i<len(arr):
        print(arr[i])
        i+=1
    print('\n')
    root=arraytotree(arr,0,len(arr)-1)
    print('转换成数的中序遍历为：')
    printTreeMidOrder(root)
    print('\n')

输出：
数组
1
2
3
4
5
6
7
8
9
10


转换成数的中序遍历为：
1
2
3
4
5
6
7
8
9
10

本文地址：https://blog.csdn.net/weixin_42813521/article/details/107648974