38CBST.1同时满足二叉搜索树和完全二叉树

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
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
'''
回顾一下 ，二叉搜索树（左小中中右大）、完全二叉树。
二叉搜索树可能很歪，完全二叉树一定是比较平衡的。

题意
把一串数 输入， 要求构建的树，同时满足二叉搜索树和完全二叉树的定义。
最后输出 这颗新构建的树的 层序遍历结果。

输入 1234567890

输出 6381579024

'''
'''
树的表示可以是   链表 vs 数组

什么时候选链表呢？
    树左斜 或者 右斜 严重时，如果用数组 要预留很多 空位置，所以此时使用链表。

本题中 ，要求是完全二叉树，不会浪费空间，而且要层序遍历输出，数组就会有优势一些（不用搞个什么队列啊之类的）。

所以，本题确定存储方式为  数组。

'''
'''
解题的思路一般都是从  
解决样例 的过程中 总结 规律，形成算法。

思路：
    根据二叉搜索树，如果我们知道 左子树的 结点 数量，就能知道根结点的那个数字（因为是按照小到大的顺序排的）；
    又根据完全二叉树，我们可以算出来左子树的 结点数量。（因为给定了总结点数量以后，完全二叉树的结构是固定的，左边几个结点都是确定的）。
    所以根结点可以确定下来，左右分支也能分别确定。
    我们可以观察到，都是先确定根结点，再左右，类似于先序遍历。
总结步骤：
    1、根据总结点数与完全二叉树性质，判断左子树结点数。
    2、根据左子树结点数与搜索二叉树性质，确定根结点、及其左子树、右子树。
    以上步骤 可以进行递归，直到新的树构建完毕。
    
从排序后的输入序列A _ _ _ _ _ _   选出root，存入  结果树T _ _ _ _ _ _ 
'''
def solve(ALeft,ARight,TRoot): # TRoot 指的是 T 上根结点的 位置。
    n = ARight - ALeft + 1
    if n == 0:
        return
    L = GetLeftLength(n) # 计算出n个结点的完全二叉树左子树又多少个结点。
    root = A[ ALeft + L ]
    T[TRoot] = root

    LeftTRoot = TRoot * 2 + 1  # 因为这没有在前面存"哨兵"，左孩子和之前的表示差一位。
    RightTRoot = LeftTRoot + 1
    solve(ALeft ,ALeft+L-1 ,LeftTRoot)
    solve(ALeft+L+1 ,ARight ,RightTRoot)

# 对于完美二叉树，定义根为第1层的话，每层2**(H-1)个结点，有H 层，总结点数 = 2**H - 1。

# T 相当于一个完美二叉树 加上一个最下层 的 X 个结点。

# 2**H - 1 + X = n

# H = log2(N+1-X) ≈ log2(N+1)的向下取整。

# 将 H = log2(N+1)」 反代回 2**H - 1 + X = N，求出 X 。

# 完美二叉树的左子树中的完美二叉树结点数 = 2**(H-1) - 1。

# 则（X不超过左一半的情况下，画图很好理解）

# 此情况下，左子树的结点数 L = 2**(H-1) - 1 + X ，X属于[0,2**(H-1)]。

# 综上所述此情况下，X = min{X,2**(H-1)}，因为目的只是求出左子树的总结点数，其它情况不用考虑。

#

# 总结步骤：

# 1、 H = log2(N+1)」

# 2、 X = 1 + N -2**H

# 3、 X = min{X,2**(H-1)}

# 4、 L = 2**(H-1) - 1 + X

import math
def GetLeftLength(n):
    h = int(math.log((n+1),2))
    x = 1 + n - 2**h
    x = min(x,2**(h-1))
    L = 2**(h-1) -1 + x
    return L

L = GetLeftLength(9)
print(L,'\n' )
A = sorted([1,3,4,2,9,6,7,5,8])
T = [None for _ in range(9)]
solve(0,len(A)-1,0)
print('层序遍历输出为：')
print(T)     # 数组的正常输出顺序就是 这个完全二叉树的层序遍历输出。