问题描述： Cartesian tree，笛卡尔树。从一个各数值均不同的序列建一棵笛卡尔树，这棵树的中序遍历与这个序列一致，同时，笛卡尔树符合一个小顶堆的结构（父结点的值均小于子结点）

给出一个各数值均不同的序列，根据此序列建一棵笛卡尔树，并输出它的层序遍历。

问题分析：给定序列与树的中序遍历一致，并且树是个小顶堆。那么大方向是向右加结点，如果初始有1个笛卡尔树，序列的下一个数字比当前树根的值还小，则这下一个数字就是新的根，原树成为其左子结点。如果下个数字比树根的值大，若右子树为空，则直接插入成右子树，右子树不为空则在右子树上找一个合适的位置插入。由于要求中序必须与原序列一致，所以右子树不空的情况下，新插入的必须在最右，新插入位置原有的树是新插入结点的左子树即可。建好了树对此树层序遍历即可出结果。

参考程序

N=int(input())
class Tree:
    def __init__(self,v):
        self.value=v
        self.lChild=None
        self.rChild=None
def transTree(t):
    def __tran(t):
        if t!=None:
            __tran(t.lChild)
            print(t.value,end=" ")
            __tran(t.rChild)
    __tran(t)
    print()
def Enqueue(Q,v):
    Q.append(v)
def Dequeue(Q):
    return Q.pop(0)
def levelOrder(t):
    queue1=[]
    print(t.value,end="")
    if t.lChild!=None:
        Enqueue(queue1,t.lChild)
    if t.rChild!=None:
        Enqueue(queue1,t.rChild)
    while len(queue1)>0:
        print(" ",end="")
        node=Dequeue(queue1)
        if node.lChild!=None:
            Enqueue(queue1,node.lChild)
        if node.rChild!=None:
            Enqueue(queue1,node.rChild)
        print(node.value,end="")
a=map(int,input().split())
t=Tree(a.__next__())
for it in a:
    if it < t.value:
        nt=Tree(it)
        nt.lChild=t
        t=nt
    else:
        # it > t.value
        # if it.rchild is none, insert it
        if t.rChild==None:
            t.rChild=Tree(it)
        # else
        #  go through tha path and find correct position and insert
        else:
            prev=t
            curr=t.rChild
            while curr!=None:
                if prev.value<it and it<curr.value:
                    break
                prev=curr
                curr=curr.rChild
            newNode=Tree(it)
            newNode.lChild=curr
            prev.rChild=newNode
levelOrder(t)